可哈希的字典(dicts)在Python中

Question

作为一个练习，主要是为了我自己的乐趣，我正在实现一个回溯的“打包鼠”解析器。这个想法的灵感来源于我想更好地理解在类似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'}

好的。但我必须为我想使用的规则中每种可能的键组合创建一个类，这并不是太糟糕，因为每个解析规则确切知道它使用了哪些参数，所以这个类可以在解析规则的函数同时定义。

编辑：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

总结一下：我该如何获得可以作为其他dict键的dict？

在对答案进行了一些修改后，这里是我正在使用的更完整的解决方案。请注意，这做了一些额外的工作，使得结果字典在实际使用中大致是不可变的。当然，通过调用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()

元组可哈希字典回溯解析器卫生宏键值集合不可变集合解析规则语法版本

可哈希的字典(dicts)在Python中

11 个回答

撰写回答