Python 可哈希字典

问题描述：

作为一项练习，也主要是为了我自己的娱乐，我正在实现一个回溯式 Packrat 解析器。这样做的灵感是我想更好地了解 Hygenic 宏如何在类似 Algol 的语言中工作（与您通常在其中找到它们的语法自由的 Lisp 方言相反）。因此，通过输入的不同传递可能会看到不同的语法，因此缓存的解析结果无效，除非我还将语法的当前版本与缓存的解析结果一起存储。（编辑：使用键值集合的结果是它们应该是不可变的，但我不打算公开接口以允许更改它们，因此可变或不可变集合都可以）

问题是 Python 字典不能作为其他字典的键出现。即使使用元组（我无论如何都会这样做）也无济于事。

>>> cache = {}
>>> rule = {"foo":"bar"}
>>> cache[(rule, "baz")] = "quux"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>> 

我猜它必须一直都是元组。现在 Python 标准库提供了我所需要的东西，collections.namedtuple语法非常不同，但可以用作键。继续上面的会话：

>>> from collections import namedtuple
>>> Rule = namedtuple("Rule",rule.keys())
>>> cache[(Rule(**rule), "baz")] = "quux"
>>> cache
{(Rule(foo='bar'), 'baz'): 'quux'}

好的。但是我必须为规则中我想要使用的每种可能的键组合创建一个类，这也不是那么糟糕，因为每个解析规则都确切地知道它使用了哪些参数，因此可以同时定义该类和解析规则的函数。

编辑：s 的另一个问题namedtuple是它们严格依赖于位置。两个看起来应该不同的元组实际上可能是相同的：

>>> you = namedtuple("foo",["bar","baz"])
>>> me = namedtuple("foo",["bar","quux"])
>>> you(bar=1,baz=2) == me(bar=1,quux=2)
True
>>> bob = namedtuple("foo",["baz","bar"])
>>> you(bar=1,baz=2) == bob(bar=1,baz=2)
False

tl'dr：如何获取dict可以用作其他dicts 的键的 s？

在对答案进行了一些修改后，下面是我使用的更完整的解决方案。请注意，这需要做一些额外的工作，以使生成的字典在实际用途上几乎不可变。当然，通过调用来解决这个问题仍然相当容易，dict.__setitem__(instance, key, value)但我们都是成年人。

class hashdict(dict):
    """
    hashable dict implementation, suitable for use as a key into
    other dicts.

        >>> h1 = hashdict({"apples": 1, "bananas":2})
        >>> h2 = hashdict({"bananas": 3, "mangoes": 5})
        >>> h1+h2
        hashdict(apples=1, bananas=3, mangoes=5)
        >>> d1 = {}
        >>> d1[h1] = "salad"
        >>> d1[h1]
        'salad'
        >>> d1[h2]
        Traceback (most recent call last):
        ...
        KeyError: hashdict(bananas=3, mangoes=5)

    based on answers from
       http://stackoverflow.com/questions/1151658/python-hashable-dicts

    """
    def __key(self):
        return tuple(sorted(self.items()))
    def __repr__(self):
        return "{0}({1})".format(self.__class__.__name__,
            ", ".join("{0}={1}".format(
                    str(i[0]),repr(i[1])) for i in self.__key()))

    def __hash__(self):
        return hash(self.__key())
    def __setitem__(self, key, value):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def __delitem__(self, key):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def clear(self):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def pop(self, *args, **kwargs):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def popitem(self, *args, **kwargs):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def setdefault(self, *args, **kwargs):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def update(self, *args, **kwargs):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    # update is not ok because it mutates the object
    # __add__ is ok because it creates a new object
    # while the new object is under construction, it's ok to mutate it
    def __add__(self, right):
        result = hashdict(self)
        dict.update(result, right)
        return result

if __name__ == "__main__":
    import doctest
    doctest.testmod()

解决方案 1：

这是创建可哈希字典的简单方法。只需记住，出于显而易见的原因，在嵌入另一个字典后不要改变它们。

class hashabledict(dict):
    def __hash__(self):
        return hash(tuple(sorted(self.items())))

解决方案 2：

Hashable 应该是不可变的 —— 不是强制要求这一点，而是相信你在第一次将字典用作键之后不会改变它，下面的方法是可行的：

class hashabledict(dict):
  def __key(self):
    return tuple((k,self[k]) for k in sorted(self))
  def __hash__(self):
    return hash(self.__key())
  def __eq__(self, other):
    return self.__key() == other.__key()

如果你确实需要改变你的字典并且仍然想将它们用作键，那么复杂性就会激增百倍——并不是说它无法完成，但是我会等到非常具体的迹象出现之后再陷入那个令人难以置信的困境！-)

解决方案 3：

为了使字典能够满足您的目的，只需添加 hash 方法：

class Hashabledict(dict):
    def __hash__(self):
        return hash(frozenset(self))

注意，frozenset转换适用于所有字典（即它不要求键可排序）。同样，字典值也没有限制。

如果有许多字典具有相同的键但具有不同的值，则需要让哈希考虑这些值。最快的方法是：

class Hashabledict(dict):
    def __hash__(self):
        return hash((frozenset(self), frozenset(self.itervalues())))

这比 更快，frozenset(self.iteritems())原因有二。首先，该frozenset(self)步骤重用了字典中存储的哈希值，从而节省了对 的不必要调用hash(key)。其次，使用itervalues将直接访问值，并避免每次查找时使用items在内存中形成许多新的键/值元组的多次内存分配器调用。

解决方案 4：

给出的答案还可以，但是可以通过使用frozenset(...)而不是tuple(sorted(...))生成哈希来改进：

>>> import timeit
>>> timeit.timeit('hash(tuple(sorted(d.iteritems())))', "d = dict(a=3, b='4', c=2345, asdfsdkjfew=0.23424, x='sadfsadfadfsaf')")
4.7758948802947998
>>> timeit.timeit('hash(frozenset(d.iteritems()))', "d = dict(a=3, b='4', c=2345, asdfsdkjfew=0.23424, x='sadfsadfadfsaf')")
1.8153600692749023

性能优势取决于字典的内容，但在我测试的大多数情况下，使用散列frozenset至少快 2 倍（主要是因为它不需要排序）。

解决方案 5：

一个相当干净、直接的实现是

import collections

class FrozenDict(collections.Mapping):
    """Don't forget the docstrings!!"""

    def __init__(self, *args, **kwargs):
        self._d = dict(*args, **kwargs)

    def __iter__(self):
        return iter(self._d)

    def __len__(self):
        return len(self._d)

    def __getitem__(self, key):
        return self._d[key]

    def __hash__(self):
        return hash(tuple(sorted(self._d.iteritems())))

解决方案 6：

我一直回到这个话题……这是另一种变体。我不太愿意通过子类化dict来添加__hash__方法；实际上，字典是可变的，这个问题是无法避免的，相信它们不会改变似乎是一个很弱的想法。所以我转而研究基于本身不可变的内置类型构建映射。虽然tuple这是一个显而易见的选择，但访问其中的值意味着排序和二分法；这不是问题，但它似乎并没有充分利用它所基于的类型的大部分功能。

如果将键、值对塞入 会怎么样frozenset？这需要什么？它将如何工作？

第 1 部分，您需要一种对“项目”进行编码的方法，以便冻结集主要通过它们的键来处理它们；我将为此创建一个小子类。

import collections
class pair(collections.namedtuple('pair_base', 'key value')):
    def __hash__(self):
        return hash((self.key, None))
    def __eq__(self, other):
        if type(self) != type(other):
            return NotImplemented
        return self.key == other.key
    def __repr__(self):
        return repr((self.key, self.value))

仅凭这一点，你就已经接近不可变映射了：

>>> frozenset(pair(k, v) for k, v in enumerate('abcd'))
frozenset([(0, 'a'), (2, 'c'), (1, 'b'), (3, 'd')])
>>> pairs = frozenset(pair(k, v) for k, v in enumerate('abcd'))
>>> pair(2, None) in pairs
True
>>> pair(5, None) in pairs
False
>>> goal = frozenset((pair(2, None),))
>>> pairs & goal
frozenset([(2, None)])

哎呀！不幸的是，当你使用集合运算符并且元素相等但不是同一个对象时；哪一个最终返回值为undefined，我们将不得不经历更多的旋转。

>>> pairs - (pairs - goal)
frozenset([(2, 'c')])
>>> iter(pairs - (pairs - goal)).next().value
'c'

但是，以这种方式查找值很麻烦，更糟糕的是，会创建大量中间集；这不行！我们将创建一个“假”键值对来解决这个问题：

class Thief(object):
    def __init__(self, key):
        self.key = key
    def __hash__(self):
        return hash(pair(self.key, None))
    def __eq__(self, other):
        self.value = other.value
        return pair(self.key, None) == other

其结果是问题较少：

>>> thief = Thief(2)
>>> thief in pairs
True
>>> thief.value
'c'

这就是所有深奥的魔法；剩下的就是把它们包装成具有类似字典的接口frozenset的东西。由于我们是从 子类化而来的，它有一个非常不同的接口，所以有很多方法；我们从 那里得到了一点帮助collections.Mapping，但大部分工作是覆盖frozenset像字典一样工作的版本的方法，而是：

class FrozenDict(frozenset, collections.Mapping):
    def __new__(cls, seq=()):
        return frozenset.__new__(cls, (pair(k, v) for k, v in seq))
    def __getitem__(self, key):
        thief = Thief(key)
        if frozenset.__contains__(self, thief):
            return thief.value
        raise KeyError(key)
    def __eq__(self, other):
        if not isinstance(other, FrozenDict):
            return dict(self.iteritems()) == other
        if len(self) != len(other):
            return False
        for key, value in self.iteritems():
            try:
                if value != other[key]:
                    return False
            except KeyError:
                return False
        return True
    def __hash__(self):
        return hash(frozenset(self.iteritems()))
    def get(self, key, default=None):
        thief = Thief(key)
        if frozenset.__contains__(self, thief):
            return thief.value
        return default
    def __iter__(self):
        for item in frozenset.__iter__(self):
            yield item.key
    def iteritems(self):
        for item in frozenset.__iter__(self):
            yield (item.key, item.value)
    def iterkeys(self):
        for item in frozenset.__iter__(self):
            yield item.key
    def itervalues(self):
        for item in frozenset.__iter__(self):
            yield item.value
    def __contains__(self, key):
        return frozenset.__contains__(self, pair(key, None))
    has_key = __contains__
    def __repr__(self):
        return type(self).__name__ + (', '.join(repr(item) for item in self.iteritems())).join('()')
    @classmethod
    def fromkeys(cls, keys, value=None):
        return cls((key, value) for key in keys)

这最终回答了我的问题：

>>> myDict = {}
>>> myDict[FrozenDict(enumerate('ab'))] = 5
>>> FrozenDict(enumerate('ab')) in myDict
True
>>> FrozenDict(enumerate('bc')) in myDict
False
>>> FrozenDict(enumerate('ab', 3)) in myDict
False
>>> myDict[FrozenDict(enumerate('ab'))]
5

解决方案 7：

@Unknown 接受的答案以及@AlexMartelli 的答案工作得很好，但仅限于以下约束：

1. 字典的值必须是可哈希的。例如，hash(hashabledict({'a':[1,2]}))will raise TypeError。

2. 键必须支持比较运算。例如，hash(hashabledict({'a':'a', 1:1}))将提高TypeError。

3. 键上的比较运算符强制执行全序。例如，如果字典中的两个键是 和frozenset((1,2,3))，frozenset((4,5,6))则它们在两个方向上的比较都不相等。因此，使用此类键对字典的项目进行排序可能会导致任意顺序，因此将违反相等对象必须具有相同哈希值的规则。

@ObenSonne 的回答更快，解除了约束 2 和 3，但仍然受约束 1 的约束（值必须是可哈希的）。

@RaymondHettinger 的回答更快，因为它不包含.values()在哈希计算中，因此解除了所有 3 个约束。但是，只有在以下情况下，其性能才良好：

1. 大多数需要进行散列的（不相等）字典都不相同.keys()。

如果不满足此条件，哈希函数仍然有效，但可能会导致过多的冲突。例如，在极端情况下，所有字典都是从网站模板生成的（字段名称作为键，用户输入作为值），键将始终相同，哈希函数将为所有输入返回相同的值。因此，依赖于此类哈希函数的哈希表在检索项目时将变得与列表一样慢（O(N)而不是O(1)）。

我认为，即使违反了我上面列出的所有 4 个约束，以下解决方案也能很好地工作。它还有一个额外的优点，它不仅可以散列字典，还可以散列任何容器，即使它们有嵌套的可变容器。

我非常感谢任何关于此的反馈，因为到目前为止我只是对此进行了简单的测试。

# python 3.4
import collections
import operator
import sys
import itertools
import reprlib

# a wrapper to make an object hashable, while preserving equality
class AutoHash:
    # for each known container type, we can optionally provide a tuple
    # specifying: type, transform, aggregator
    # even immutable types need to be included, since their items
    # may make them unhashable

    # transformation may be used to enforce the desired iteration
    # the result of a transformation must be an iterable
    # default: no change; for dictionaries, we use .items() to see values

    # usually transformation choice only affects efficiency, not correctness

    # aggregator is the function that combines all items into one object
    # default: frozenset; for ordered containers, we can use tuple

    # aggregator choice affects both efficiency and correctness
    # e.g., using a tuple aggregator for a set is incorrect,
    # since identical sets may end up with different hash values
    # frozenset is safe since at worst it just causes more collisions
    # unfortunately, no collections.ABC class is available that helps
    # distinguish ordered from unordered containers
    # so we need to just list them out manually as needed

    type_info = collections.namedtuple(
        'type_info',
        'type transformation aggregator')

    ident = lambda x: x
    # order matters; first match is used to handle a datatype
    known_types = (
        # dict also handles defaultdict
        type_info(dict, lambda d: d.items(), frozenset), 
        # no need to include set and frozenset, since they are fine with defaults
        type_info(collections.OrderedDict, ident, tuple),
        type_info(list, ident, tuple),
        type_info(tuple, ident, tuple),
        type_info(collections.deque, ident, tuple),
        type_info(collections.Iterable, ident, frozenset) # other iterables
    )

    # hash_func can be set to replace the built-in hash function
    # cache can be turned on; if it is, cycles will be detected,
    # otherwise cycles in a data structure will cause failure
    def __init__(self, data, hash_func=hash, cache=False, verbose=False):
        self._data=data
        self.hash_func=hash_func
        self.verbose=verbose
        self.cache=cache
        # cache objects' hashes for performance and to deal with cycles
        if self.cache:
            self.seen={}

    def hash_ex(self, o):
        # note: isinstance(o, Hashable) won't check inner types
        try:
            if self.verbose:
                print(type(o),
                    reprlib.repr(o),
                    self.hash_func(o),
                    file=sys.stderr)
            return self.hash_func(o)
        except TypeError:
            pass

        # we let built-in hash decide if the hash value is worth caching
        # so we don't cache the built-in hash results
        if self.cache and id(o) in self.seen:
            return self.seen[id(o)][0] # found in cache

        # check if o can be handled by decomposing it into components
        for typ, transformation, aggregator in AutoHash.known_types:
            if isinstance(o, typ):
                # another option is:
                # result = reduce(operator.xor, map(_hash_ex, handler(o)))
                # but collisions are more likely with xor than with frozenset
                # e.g. hash_ex([1,2,3,4])==0 with xor

                try:
                    # try to frozenset the actual components, it's faster
                    h = self.hash_func(aggregator(transformation(o)))
                except TypeError:
                    # components not hashable with built-in;
                    # apply our extended hash function to them
                    h = self.hash_func(aggregator(map(self.hash_ex, transformation(o))))
                if self.cache:
                    # storing the object too, otherwise memory location will be reused
                    self.seen[id(o)] = (h, o)
                if self.verbose:
                    print(type(o), reprlib.repr(o), h, file=sys.stderr)
                return h

        raise TypeError('Object {} of type {} not hashable'.format(repr(o), type(o)))

    def __hash__(self):
        return self.hash_ex(self._data)

    def __eq__(self, other):
        # short circuit to save time
        if self is other:
            return True

        # 1) type(self) a proper subclass of type(other) => self.__eq__ will be called first
        # 2) any other situation => lhs.__eq__ will be called first

        # case 1. one side is a subclass of the other, and AutoHash.__eq__ is not overridden in either
        # => the subclass instance's __eq__ is called first, and we should compare self._data and other._data
        # case 2. neither side is a subclass of the other; self is lhs
        # => we can't compare to another type; we should let the other side decide what to do, return NotImplemented
        # case 3. neither side is a subclass of the other; self is rhs
        # => we can't compare to another type, and the other side already tried and failed;
        # we should return False, but NotImplemented will have the same effect
        # any other case: we won't reach the __eq__ code in this class, no need to worry about it

        if isinstance(self, type(other)): # identifies case 1
            return self._data == other._data
        else: # identifies cases 2 and 3
            return NotImplemented

d1 = {'a':[1,2], 2:{3:4}}
print(hash(AutoHash(d1, cache=True, verbose=True)))

d = AutoHash(dict(a=1, b=2, c=3, d=[4,5,6,7], e='a string of chars'),cache=True, verbose=True)
print(hash(d))

解决方案 8：

您可能还想添加这两种方法，以使 v2 pickling 协议与 hashdict 实例一起工作。否则 cPickle 将尝试使用 hashdict.____setitem____ 导致 TypeError。有趣的是，使用协议的其他两个版本，您的代码可以正常工作。

def __setstate__(self, objstate):
    for k,v in objstate.items():
        dict.__setitem__(self,k,v)
def __reduce__(self):
    return (hashdict, (), dict(self),)

解决方案 9：

这是python3的正确方法：

    class KeyDict(dict):
        def __hash__(self):
            return hash(frozenset(self.items()))

被接受的答案是执行排序，这比使用集合要慢，而另一个流行的答案frozenset(self)是错误的（两个不同的字典可以有相同的哈希输入）。实际上，这可能会导致过多的冲突，在某些情况下将查找时间减少到 O(n)。

上面的解决方案在评论中提到，但应该是主要答案。

解决方案 10：

使用 json 包将字典序列化为字符串：

d = {'a': 1, 'b': 2}
s = json.dumps(d)

在需要时恢复字典：

d2 = json.loads(s)

解决方案 11：

如果您没有将数字放入字典中，并且您从未丢失包含字典的变量，那么您可以这样做：

cache[id(rule)] = "whatever"

因为 id() 对于每个字典来说都是唯一的

编辑：

哦，抱歉，是的，在这种情况下，其他人说的会更好。我认为你也可以将你的字典序列化为字符串，例如

cache[ 'foo:bar' ] = 'baz'

如果你需要从键中恢复你的字典，那么你必须做一些更丑陋的事情，比如

cache[ 'foo:bar' ] = ( {'foo':'bar'}, 'baz' )

我想这样做的好处是你不必编写那么多代码。