在Python中对不可变字典进行哈希处理

Question

在Python中对不可变字典进行哈希处理

pythondictionaryhashimmutabilitypython-3.2

18

短版：作为无序项字典实现的多重集最佳哈希算法是什么？

我正在尝试对作为字典实现的不可变多重集（在其他语言中称为袋或多重集：类似于数学集合，但可以容纳多个相同元素）进行哈希。我已经创建了一个标准库类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)

我想使用位异或运算符意味着哈希值的顺序不重要，不像哈希元组一样？我可以在数据的无序元组流上半实现Python元组哈希算法。请参见https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h（在页面中搜索单词'hash'）-但我几乎不了解足够的C语言来阅读它。

有什么想法？建议？谢谢。

（如果您想知道为什么我要尝试对多重集进行哈希：我的问题的输入数据是多重集的集合，并且在每个多重集的集合中，每个多重集必须是唯一的。我正在按期限工作，而且我不是经验丰富的编码人员，因此我希望尽可能避免发明新的算法。似乎确保我拥有一堆独特的东西的最Pythonic方法是将它们放入set()中，但这些东西必须是可哈希的。）

从评论中我所收集到的

@marcin和@senderle给出了几乎相同的答案：使用hash(frozenset(self.items()))。这是有道理的，因为items()“视图”类似于集合。虽然@marcin先回答，但我选择了@senderle，因为他对不同解决方案的大O运行时间进行了良好的研究。@marcin还提醒我要包含一个__eq__方法--但从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

- wkschwartz

任何可哈希的对象都是可排序的。如果它是可哈希的，则始终会产生相同的哈希值，因此可以按哈希值进行排序。 - senderle

1

你确定创建 tuple 占用了很多内存吗？它只是指向字典中每个项目的“指针”，而不是创建一个副本。 - agf

请查看http://www.cs.toronto.edu/~tijmen/programming/immutableDictionaries.html。 - wkschwartz

非常全面地更新了问题，并提供了最终的实现，给你加1分。 - mklauber

2个回答

1

你考虑过使用 hash(sorted(hash(x) for x in self.items())) 吗？这样，你只需要对整数进行排序，而不必构建列表。

你也可以将元素哈希值进行异或运算，但老实说我不知道那样做会有多好（会有很多碰撞吗？）。说到碰撞，你不需要实现 __eq__ 方法吗？

或者，类似于我的答案这里, 使用 hash(frozenset(self.items()))。

- Marcin

列表不可哈希。应该是 hash(tuple(sorted(... - tejasvi88

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- senderle · Accepted Answer

由于字典是不可变的，因此您可以在创建字典时创建哈希并直接返回它。我的建议是从items（在3+中使用）创建一个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 的这个很好的回答，介绍了他对frozenset哈希函数的实现方式。在那里，他明确解释了如何避免排序值以获得稳定、不敏感于顺序的值。