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

Question

Python dict是一个非常有用的数据结构:

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

d['a'] # get 1

有时你也想按值索引.

d[1] # get 'a'

哪种方法是实现此数据结构的最有效方法？有官方推荐的方法吗？

Answer 1

这是一个双向类dict,受Python字典中的值的Finding键的启发,并修改为允许以下2)和3).

注意 :

• 1)当修改标准字典时,反向目录 bd.inverse自动更新bd.
• 2)逆目录 bd.inverse[value]始终是一个列表的key,使得bd[key] == value.
• 3)与https://pypi.python.org/pypi/bidict中的bidict模块不同,这里我们可以有2个具有相同值的键,这非常重要.

码:

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']}

Answer 2

您可以通过以相反顺序添加键,值对来使用相同的dict本身.

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

Answer 3

穷人的双向哈希表只使用两个词典(这些词典已经是高度调整的数据结构).

索引上还有一个bidict包:

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

bidict的来源可以在github上找到:

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

Answer 4

下面的代码片段实现了一个可逆（双射）映射：

class BijectionError(Exception):
    """Must set a unique value in a BijectiveMap."""

    def __init__(self, value):
        self.value = value
        msg = 'The value "{}" is already in the mapping.'
        super().__init__(msg.format(value))


class BijectiveMap(dict):
    """Invertible map."""

    def __init__(self, inverse=None):
        if inverse is None:
            inverse = self.__class__(inverse=self)
        self.inverse = inverse

    def __setitem__(self, key, value):
        if value in self.inverse:
            raise BijectionError(value)

        self.inverse._set_item(value, key)
        self._set_item(key, value)

    def __delitem__(self, key):
        self.inverse._del_item(self[key])
        self._del_item(key)

    def _del_item(self, key):
        super().__delitem__(key)

    def _set_item(self, key, value):
        super().__setitem__(key, value)

这种实现的优点是inversea的属性BijectiveMap又是 a BijectiveMap。因此，您可以执行以下操作：

>>> foo = BijectiveMap()
>>> foo['steve'] = 42
>>> foo.inverse
{42: 'steve'}
>>> foo.inverse.inverse
{'steve': 42}
>>> foo.inverse.inverse is foo
True