How to implement an efficient bidirectional hash table?

Python dict is a very useful data-structure:

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?

53428 次浏览
小开

一个穷人的双向散列表将只使用两个字典(这些已经是高度优化的数据结构)。

该指数还有一个 比迪克特软件包:

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

小开

大概是这样:

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))

如果不止一个键具有给定的值，那么您必须决定希望发生什么; 给定对的双向性很容易被后面插入的一些对所破坏。我做了一个可能的选择。

例如:

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

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

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

下面是一个双向 dict的类，它受到 Finding key from value in Python dictionary的启发，并进行了修改以允许以下2)和3)。

请注意:

    1. 当标准 dictbd被修改时，反向目录反向目录bd.inverse会自动更新。
    1. 反向目录反向目录的 bd.inverse[value]始终是 key的 list，因此 bd[key] == value。
    1. 与 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.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']}
小开

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 inverse attribute of a BijectiveMap is again a BijectiveMap. Therefore you can do things like:

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

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.

第二，数据集有多大？如果没有太多的数据，只需使用2个独立的映射，并在更新时同时更新这两个映射。或者更好的方法是使用现有的解决方案，比如 比迪克特，它只是一个包含2个字母的包装器，内置了更新/删除功能。

但是如果数据集很大，并且维护两个字母是不可取的:

  • 如果键和值都是数值，请考虑使用 插值近似映射。如果绝大多数 键值对可以被映射函数(及其
    反向函数) ，那么您只需要记录映射中的异常值

  • 如果大多数访问是单向的(key-> value) ，那么它完全是 可以逐步构建反向映射，用时间交换
    空间

密码:

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]
小开

不幸的是，评分最高的答案是 bidict不起作用。

有三种选择:

  1. 子类 dict : 您可以创建 dict的子类，但要注意。您需要编写 update、 pop、 initializer、 setdefault的自定义实现。dict实现不调用 __setitem__。这就是为什么评分最高的答案有问题。

  2. 从 UserDect 继承 : 这就像一个 dict，只不过所有例程都被正确调用。它在引擎盖下使用了一个叫做 data的项目。你可以读取 Python 文档或 use a simple implementation of a by directional list that works in Python 3。很抱歉没有逐字包括它: 我不确定它的版权。

  3. 从抽象基类继承 : 从 收藏品继承将帮助您获得新类的所有正确协议和实现。这对于双向字典来说有点过了，除非它还可以加密并缓存到数据库中。

DR ——代码使用 这个。详细信息请阅读 Trey Hunner的 文章。

小开

更好的方法是将字典转换为元组列表，然后在特定的元组字段上进行排序

def convert_to_list(dictionary):
list_of_tuples = []
for key, value in dictionary.items():
list_of_tuples.append((key, value))
return list_of_tuples


def sort_list(list_of_tuples, field):
return sorted(list_of_tuples, key=lambda x: x[field])


dictionary = {'a': 9, 'b': 2, 'c': 3, 'd': 4, 'e': 5}
list_of_tuples = convert_to_list(dictionary)
print(sort_list(list_of_tuples, 1))

输出

[('b', 2), ('c', 3), ('d', 4), ('e', 5), ('a', 9)]

提交答案