如何实现高效的双向哈希表？-IT科技

摘要：问题描述：Pythondict有一个非常有用的数据结构：d = {'a': 1, 'b': 2} d['a'] # get 1 有时您还想按值进行索引。d[1] # get 'a' 实现此数据结构的最有效方法是什么？有没有官方推荐的方法？解决方案 1：这是一个双向的类dict，受到在 Python 字典中从...

问题描述：

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

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

d['a'] # get 1

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

d[1] # get 'a'

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

解决方案 1：

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

注意：

1. 当标准字典被修改时，逆目录 会bd.inverse自动更新。bd
1. 逆目录 始终bd.inverse[value]是这样的列表。key`bd[key] == value`
1. 与https://pypi.python.org/pypi/bidictbidict中的模块不同，这里我们可以有 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']}

解决方案 2：

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

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

解决方案 3：

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

索引上还有一个bidict包：

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

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

https://github.com/jab/bidict

解决方案 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

解决方案 5：

也许是这样的：

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

解决方案 6：

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

其次，数据集有多大？如果数据不多，只需使用 2 个单独的映射，并在更新时同时更新它们。或者更好的是，使用现有的解决方案，如Bidict，它只是 2 个字典的包装器，内置了更新/删除功能。

但是如果数据集很大，并且维护 2 个字典是不合需要的：

如果 key 和 value 都是数字，可以考虑使用 Interpolation 来近似映射。如果绝大多数 key-value 对都能被映射函数（及其

逆函数）覆盖，那么只需要在 map 中记录异常值即可。

如果大多数访问都是单向的（键->值），那么逐步构建反向映射是完全可以的，以时间换取

空间。

代码：

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]

解决方案 7：

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

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

解决方案 8：

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

有三个选项：

子类字典：您可以创建的子类dict，但要小心。您需要编写update、pop、initializer、的自定义实现setdefault。这些dict实现不会调用__setitem__。这就是评分最高的答案有问题的原因。
从 UserDict 继承：这就像一个字典，除了所有例程都正确调用。它在底层使用一个字典，在名为的项目中data。您可以阅读Python 文档，或者使用在 Python 3 中工作的按方向列表的简单实现。很抱歉没有逐字逐句地包括它：我不确定它的版权。
从抽象基类继承：从collections.abc继承将帮助您获得新类的所有正确协议和实现。这对于双向字典来说有点过头了，除非它也可以加密并缓存到数据库。