什么是存储2元组（a，b）的最好的数据结构，它支持添加，删除元组并比较（在a或b上）

Question

所以这是我的问题。我想存储的2元组（键，VAL）并要执行以下操作：

• 键是字符串和值是整数
  
• 多个键可以有相同的值
• 增加新的元组
  
• 用新值更新任何键（任何新值或更新值大于前一个值，如时间戳）
  
• 获取值小于或大于给定值的所有键
  
• 删除元组。

哈希似乎是更新密钥值的明显选择，但通过值查找需要更长的时间（O（n））。另一种选择是平衡二叉搜索树，其中键和值交换。所以现在通过值查找将会很快（O（lg（n））），但更新密钥将需要（O（n））。那么是否有可用于解决这些问题的数据结构？

谢谢。

Answer 1

我会使用2数据结构，哈希表从键到值和搜索树按值排序，然后按键。插入时，将这对插入两个结构中，当用键删除时，从哈希中查找值，然后从树中删除该对。更新基本上是删除+插入。插入，删除和更新是O（log n）。为了获取所有小于值的键值，查找搜索树中的值并向后迭代。这是O（log n + k）。

好的散列表和搜索树实现的选择很大程度上取决于您特定的数据和操作分布。也就是说，两者的一个好的通用目标应该是足够的。

Answer 2

对于二进制搜索树插入是O（logN）操作平均和O（n）在最坏的情况下。查找操作相同。所以这应该是你的选择，我相信。

Answer 3

字典或地图类型倾向于基于两种结构之一。

• 平衡树（保证O（log n）查找）。
• 基于哈希（最好的情况是O（1），但数据的散列函数可能会导致O（n）查找）。

任何有关算法的书都应该涵盖很多细节。为了提供对键和值的操作，还有基于多索引的集合（具有所有额外的复杂性），它们维护多个结构（很像RDBMS表可以有多个索引）。除非您在大型集合上进行大量查找，否则额外的开销可能比几个线性查找的成本更高。

Answer 4

您可以创建一个包含两个字典的自定义数据结构。

例如 来自keys->values的散列表和来自values->lists of keys的另一散列表。

class Foo: 
    def __init__(self): 
     self.keys = {} # (KEY=key,VALUE=value) 
     self.values = {} # (KEY=value,VALUE=list of keys) 

    def add_tuple(self,kd,vd): 
     self.keys[kd] = vd 
     if self.values.has_key(vd): 
      self.values[vd].append(kd) 
     else: 
      self.values[vd] = [kd] 

f = Foo() 
f.add_tuple('a',1) 
f.add_tuple('b',2) 
f.add_tuple('c',3) 
f.add_tuple('d',3) 

print f.keys 
print f.values 

print f.keys['a'] 
print f.values[3] 

print [f.values[v] for v in f.values.keys() if v > 1] 

OUTPUT：

{'a': 1, 'c': 3, 'b': 2, 'd': 3} 

{1: ['a'], 2: ['b'], 3: ['c', 'd']} 

1 

['c', 'd'] 

[['b'], ['c', 'd']]