Python哈希值字典

Question

作为一种练习，并且主要是出于我的娱乐，我正在实现回溯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'}

好。但是我必须为我想使用的规则中的每个可能的键组合创建一个类，这并不坏，因为每个解析规则都确切知道它使用的参数，因此可以同时定义该类。作为解析规则的函数。

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

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

Answer 1

这是制作可哈希字典的简单方法。请记住，出于明显的原因，不要在将它们嵌入另一本词典后对它们进行变异。class hashabledict(dict):&nbsp; &nbsp; def __hash__(self):&nbsp; &nbsp; &nbsp; &nbsp; return hash(tuple(sorted(self.items())))

Answer 2

散列应该是不可变的-不强制执行此操作，但可信任您不要在将dict作为键首次使用后对其进行突变，可以使用以下方法：class hashabledict(dict):&nbsp; def __key(self):&nbsp; &nbsp; return tuple((k,self[k]) for k in sorted(self))&nbsp; def __hash__(self):&nbsp; &nbsp; return hash(self.__key())&nbsp; def __eq__(self, other):&nbsp; &nbsp; return self.__key() == other.__key()如果您确实需要更改您的命令并且仍然想将它们用作键，那么复杂性会爆炸数百倍-并不是说无法完成，但是我将等到非常明确的指示后再进入那令人难以置信的烂摊子！ -）

Answer 3

使字典可用于您的目的所需要做的就是添加__hash__方法：class Hashabledict(dict):&nbsp; &nbsp; def __hash__(self):&nbsp; &nbsp; &nbsp; &nbsp; return hash(frozenset(self))请注意，frozenset转换将适用于所有词典（即，不需要键是可排序的）。同样，对字典值也没有限制。如果有许多字典具有相同的键但具有不同的值，则必须让散列将这些值考虑在内。最快的方法是：class Hashabledict(dict):&nbsp; &nbsp; def __hash__(self):&nbsp; &nbsp; &nbsp; &nbsp; return hash((frozenset(self), frozenset(self.itervalues())))这比frozenset(self.iteritems())两个原因要快。首先，该frozenset(self)步骤重用了存储在字典中的哈希值，将不必要的调用保存到中hash(key)。其次，使用itervalues将直接访问这些值，并避免每次进行查找时都使用by 项在内存中形成新的许多键/值元组的许多内存分配器调用。