存储支持添加、删除元组和比较(在A或B上)的2元组(A、B)的最佳数据结构是什么?

我将使用2个数据结构,一个从键到值的哈希表,以及一个按值然后按键排序的搜索树。插入时,将对插入到两个结构中,按键删除时,从哈希中查找值,然后从树中删除对。更新基本上是删除+插入。插入、删除和更新是O(日志N)。要获取小于某个值的所有键,请在搜索树中查找该值并向后迭代。这是O(日志N+K)。

好的哈希表和搜索树实现的选择很大程度上取决于数据和操作的特定分布。这就是说,一个好的、通用的两个目的的实施都应该是充分的。

对于二进制搜索,树插入平均为O(logn)操作,最坏情况为O(n)。查找操作相同。所以我相信这应该是你的选择。

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

• 平衡树(保证O(log n)查找)。
• 基于哈希(最佳情况是O(1),但数据的哈希函数不佳可能导致O(n)查找)。

任何有关算法的书都应该详细地介绍这两方面。

为了在键和值上提供操作,还存在基于多个索引的集合(具有所有额外的复杂性),这些集合维护多个结构(就像RDBMS表可以有多个索引一样)。除非您对一个大型集合进行了大量查找,否则额外的开销可能比一些线性查找成本更高。

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

即 哈希表来自 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]

输出:

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

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

1

['c', 'd']

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