python - 在 Python 中散列一个不可变的字典

Question

简短版:对于作为无序项字典实现的多重集，最好的哈希算法是什么？

我正在尝试对作为字典实现的不可变多重集(在其他语言中是包或多重集:类似于数学集，但它可以容纳多个元素)进行哈希处理。我创建了标准库类 collections.Counter 的子类，类似于此处的建议:Python hashable dicts ，它推荐这样的哈希函数:

class FrozenCounter(collections.Counter):
    # ...
    def __hash__(self):
        return hash(tuple(sorted(self.items())))

创建完整的项目元组会占用大量内存(相对于使用生成器而言)，并且散列将在我的应用程序的内存密集型部分发生。更重要的是，我的字典键(多集元素)可能无法订购。

我正在考虑使用这个算法:

def __hash__(self):
    return functools.reduce(lambda a, b: a ^ b, self.items(), 0)

我认为使用按位 XOR 意味着顺序对于散列值无关紧要，这与元组散列不同？我想我可以在无序流上半实现 Python 元组散列算法我的数据元组。参见 https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h (在页面中搜索“哈希”一词)——但我对 C 语言的了解还不足以阅读它。

想法？建议？谢谢。

---

( 如果你想知道我为什么要尝试散列多重集:我的问题的输入数据是多重集的集合，并且在每组多重集内，每个多重集都必须是唯一的。我在截止日期前工作，我不是经验丰富的编码员，所以我想尽可能避免发明新算法。确保我拥有一堆东西的最 Pythonic 方式似乎是将它们放入一个 set()，但这些东西必须是可散列的。)

---

我从评论中收集到的内容

@marcin 和@senderle 给出了几乎相同的答案:使用 hash(frozenset(self.items()))。这是有道理的，因为 items() "views" are set-like . @marcin 是第一个，但我给@senderle 打了勾，因为对不同解决方案的 big-O 运行时间进行了很好的研究。 @marcin 还提醒我 include an __eq__ method -- 但从 dict 继承的那个会工作得很好。这就是我实现所有内容的方式——欢迎基于此代码提出进一步的意见和建议:

class FrozenCounter(collections.Counter):
    # Edit: A previous version of this code included a __slots__ definition.
    # But, from the Python documentation: "When inheriting from a class without
    # __slots__, the __dict__ attribute of that class will always be accessible,
    # so a __slots__ definition in the subclass is meaningless."
    # http://docs.python.org/py3k/reference/datamodel.html#notes-on-using-slots
    # ...
    def __hash__(self):
        "Implements hash(self) -> int"
        if not hasattr(self, '_hash'):
            self._hash = hash(frozenset(self.items()))
        return self._hash

Answer 1

由于字典是不可变的，所以可以在创建字典的时候创建hash，直接返回。我的建议是从 items(在 3+ 中；iteritems 在 2.7 中)创建一个 frozenset，散列它，并存储散列。

提供一个明确的例子:

>>>> frozenset(Counter([1, 1, 1, 2, 3, 3, 4]).iteritems())
frozenset([(3, 2), (1, 3), (4, 1), (2, 1)])
>>>> hash(frozenset(Counter([1, 1, 1, 2, 3, 3, 4]).iteritems()))
-3071743570178645657
>>>> hash(frozenset(Counter([1, 1, 1, 2, 3, 4]).iteritems()))
-6559486438209652990

澄清为什么我更喜欢 frozenset 而不是排序项目的元组:frozenset 不必对项目进行排序，因此初始散列在 O 中完成(n) 时间而不是 O(n log n) 时间。这可以从frozenset_hash 和set_next 实现中看出。

另请参阅 Raymond Hettinger 的 great answer，描述了他对 frozenset 哈希函数的实现。他在那里明确解释了哈希函数如何避免对值进行排序以获得稳定的、顺序不敏感的值。