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

How to implement an efficient bidirectional hash table?

提问by Juanjo Conti

Python dictis a very useful data-structure:

Pythondict是一个非常有用的数据结构：

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

d['a'] # get 1

Sometimes you'd also like to index by values.

有时您还想按值进行索引。

d[1] # get 'a'

Which is the most efficient way to implement this data-structure? Any official recommend way to do it?

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

回答by miku

A poor man's bidirectional hash table would be to use just two dictionaries (these are highly tuned datastructures already).

一个穷人的双向哈希表将只使用两个字典（这些已经是高度调整的数据结构）。

There is also a bidictpackage on the index:

索引上还有一个bidict包：

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

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

The source for bidict can be found on github:

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

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

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

回答by Matt Anderson

Something like this, maybe:

像这样的事情，也许：

import itertools

class BidirDict(dict):
    def __init__(self, iterable=(), **kwargs):
        self.update(iterable, **kwargs)
    def update(self, iterable=(), **kwargs):
        if hasattr(iterable, 'iteritems'):
            iterable = iterable.iteritems()
        for (key, value) in itertools.chain(iterable, kwargs.iteritems()):
            self[key] = value
    def __setitem__(self, key, value):
        if key in self:
            del self[key]
        if value in self:
            del self[value]
        dict.__setitem__(self, key, value)
        dict.__setitem__(self, value, key)
    def __delitem__(self, key):
        value = self[key]
        dict.__delitem__(self, key)
        dict.__delitem__(self, value)
    def __repr__(self):
        return '%s(%s)' % (type(self).__name__, dict.__repr__(self))

You have to decide what you want to happen if more than one key has a given value; the bidirectionality of a given pair could easily be clobbered by some later pair you inserted. I implemented one possible choice.

如果多个键具有给定值，您必须决定要发生什么；给定对的双向性很容易被您稍后插入的某些对破坏。我实现了一种可能的选择。

---

---

Example :

例子 ：

bd = BidirDict({'a': 'myvalue1', 'b': 'myvalue2', 'c': 'myvalue2'})
print bd['myvalue1']   # a
print bd['myvalue2']   # b        

回答by Emil

You can use the same dict itself by adding key,value pair in reverse order.

您可以通过以相反的顺序添加键值对来使用相同的字典本身。

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

回答by Basj

Here is a class for a bidirectional dict, inspired by Finding key from value in Python dictionaryand modified to allow the following 2) and 3).

这是一个双向的类dict，受到从 Python 字典中的值中查找键的启发，并修改为允许以下 2) 和 3)。

Note that :

注意 ：

• 1) The inverse directorybd.inverseauto-updates itself when the standard dict bdis modified.
• 2) The inverse directorybd.inverse[value]is always a listof keysuch that bd[key] == value.
• 3) Unlike the bidictmodule from https://pypi.python.org/pypi/bidict, here we can have 2 keys having same value, this is very important.

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

Code:

代码：

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)

Usage example:

用法示例：

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

回答by jme

The below snippet of code implements an invertible (bijective) map:

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

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)

The advantage of this implementation is that the inverseattribute of a BijectiveMapis again a BijectiveMap. Therefore you can do things like:

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

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

回答by NeoWang

First, you have to make sure the key to value mapping is one to one, otherwise, it is not possible to build a bidirectional map.

首先，您必须确保键值映射是一对一的，否则无法构建双向映射。

Second, how large is the dataset? If there is not much data, just use 2 separate maps, and update both of them when updating. Or better, use an existing solution like Bidict, which is just a wrapper of 2 dicts, with updating/deletion built in.

其次，数据集有多大？如果数据不多，就用2个独立的map，更新的时候两个都更新。或者更好的是，使用像Bidict这样的现有解决方案，它只是 2 个dict的包装器，内置了更新/删除功能。

But if the dataset is large, and maintaining 2 dicts is not desirable:

但是如果数据集很大，并且不希望维护 2 个字典：

• If both key and value are numeric, consider the possibility of using Interpolation to approximate the mapping. If the vast majority of the key-value pairs can be covered by the mapping function (and its
  reverse function), then you only need to record the outliers in maps.

• If most of access is uni-directional (key->value), then it is totally ok to build the reverse map incrementally, to trade time for
  space.

• 如果键和值都是数字，请考虑使用插值来近似映射的可能性。如果映射函数（及其
  反向函数）可以覆盖绝大多数键值对，那么您只需要在映射中记录异常值即可。

• 如果大多数访问是单向的（键->值），那么增量地构建反向映射是完全可以的，以时间换
  空间。

Code:

代码：

d = {1: "one", 2: "two" }
reverse = {}

def get_key_by_value(v):
    if v not in reverse:
        for _k, _v in d.items():
           if _v == v:
               reverse[_v] = _k
               break
    return reverse[v]