Python中的高效双向哈希表？
Python字典是一个非常有用的数据结构：
d = {'a': 1, 'b': 2} d['a'] # get 1 有时候你也想用值来索引。
d[1] # get 'a'
哪个是实现这个数据结构的最有效的方法？ 任何官方build议的方式来做到这一点？
谢谢！
这是一个双向dict的类，灵感来源于在Python字典中查找键值，并修改为允许以下2）和3）。
注意 ：
- 1） 反向目录
bd.inverse在标准字典bd被修改时自动更新自身 - 2） 逆向目录
bd.inverse[value]始终是一个key列表 ，使bd[key] == value - 3）与https://pypi.python.org/pypi/bidict的;
bidict模块不同，在这里我们可以有两个具有相同值的键，这是非常重要的 。
码：
class bidict(dict): def __init__(self, *args, **kwargs): super(bidict, self).__init__(*args, **kwargs) self.inverse = {} for key, value in self.iteritems(): 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']}
一个穷人的双向哈希表将只使用两个字典（这些是高度调整的数据结构已经）。
该指数还有一个bidict包：
bidict的来源可以在github上find：
您可以通过以相反顺序添加键值对来使用相同的字典。
d = { 'A'：1， 'B'：2}
revd = dict（[在d.items（）中反转（i）为我）
d.update（revd）
像这样的东西，也许：
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))
如果一个以上的密钥有一个给定的值，你必须决定你想要发生什么; 给定对的双向性可能很容易被你插入的一对后来的对破坏。 我实现了一个可能的select。
例如：
bd = BidirDict({'a': 'myvalue1', 'b': 'myvalue2', 'c': 'myvalue2'}) print bd['myvalue1'] # a print bd['myvalue2'] # b
下面的代码片段实现了可逆（双射）映射：
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)
这种实现的优点是，一个BijectiveMap的inverse属性BijectiveMap是一个BijectiveMap 。 所以你可以做这样的事情：
>>> foo = BijectiveMap() >>> foo['steve'] = 42 >>> foo.inverse {42: 'steve'} >>> foo.inverse.inverse {'steve': 42} >>> foo.inverse.inverse is foo True
首先，你必须确保值映射的关键是一对一的，否则，不可能build立一个双向映射。
其次，数据集有多大？ 如果数据不多，只需使用2个独立的地图，并在更新时更新它们。 或者更好的是，使用像Bidict这样的现有解决scheme，它只是2个字节的包装，内置更新/删除。
但是，如果数据集很大，并且保持2个字节是不可取的：
-
如果键和值都是数字，考虑使用插值近似映射的可能性。 如果绝大多数键值对可以被映射函数（及其映射函数）覆盖，
反函数），那么你只需要在地图上loggingexception值。 -
如果大部分访问是单向的（key-> value），那么增量地构build反向映射是完全可以的，
空间。
码：
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]
