如何实现高效的双向哈希表？

Question

Python中的dict（字典）是一种非常有用的数据结构：

d = {'a': 1, 'b': 2}

d['a'] # get 1

有时候你可能也想根据值来索引。

d[1] # get 'a'

实现这种数据结构的最有效方法是什么？有没有官方推荐的方式？

Answer 1

一种简单的双向哈希表可以用两个字典来实现（字典本身就是经过优化的数据结构）。

另外，还有一个叫做 bidict 的包可以使用：

• https://pypi.python.org/pypi/bidict

你可以在github上找到bidict的源代码：

• https://github.com/jab/bidict

Answer 2

你可以通过反向添加键值对来使用同一个字典。

d={'a':1,'b':2}
revd=dict([reversed(i) for i in d.items()])
d.update(revd)

Answer 3

这里有一个双向 dict 的类，灵感来自于 在Python字典中根据值查找键，并进行了修改，以支持以下的功能 2) 和 3)。

需要注意的是：

• 1. 当标准字典 bd 被修改时，反向目录 bd.inverse 会自动更新。
• 2. 反向目录 bd.inverse[value] 总是一个 列表，这个列表里的 key 满足 bd[key] == value。
• 3. 与 bidict 模块不同，来自 https://pypi.python.org/pypi/bidict，在这里我们可以有两个键对应同一个值，这一点 非常重要。

代码：

class bidict(dict):
    def __init__(self, *args, **kwargs):
        super(bidict, self).__init__(*args, **kwargs)
        self.inverse = {}
        for key, value in self.items():
            self.inverse.setdefault(value, []).append(key) 

    def __setitem__(self, key, value):
        if key in self:
            self.inverse[self[key]].remove(key) 
        super(bidict, self).__setitem__(key, value)
        self.inverse.setdefault(value, []).append(key)        

    def __delitem__(self, key):
        self.inverse.setdefault(self[key], []).remove(key)
        if self[key] in self.inverse and not self.inverse[self[key]]: 
            del self.inverse[self[key]]
        super(bidict, self).__delitem__(key)

使用示例：

bd = bidict({'a': 1, 'b': 2})  
print(bd)                     # {'a': 1, 'b': 2}                 
print(bd.inverse)             # {1: ['a'], 2: ['b']}
bd['c'] = 1                   # Now two keys have the same value (= 1)
print(bd)                     # {'a': 1, 'c': 1, 'b': 2}
print(bd.inverse)             # {1: ['a', 'c'], 2: ['b']}
del bd['c']
print(bd)                     # {'a': 1, 'b': 2}
print(bd.inverse)             # {1: ['a'], 2: ['b']}
del bd['a']
print(bd)                     # {'b': 2}
print(bd.inverse)             # {2: ['b']}
bd['b'] = 3
print(bd)                     # {'b': 3}
print(bd.inverse)             # {2: [], 3: ['b']}