短版:什么是对的无序项目的字典实现一个多重的最佳哈希算法?
我想凑一个不可变多集(这是其他语言包或多重集:像数学集合,但它可以保持每个元素的不止一个)作为字典实现。 我创建了标准库类的子类collections.Counter
,与这里的建议是: Python的哈希的类型的字典 ,其中建议像这样的哈希函数:
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的元组散列alogrithm。 见https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h (对这个词“散”的页面搜索) -但我几乎不知道足够的C到阅读。
思考? 建议? 谢谢。
( 如果你想知道为什么我瞎搞,试图哈希多集:我的问题输入数据是一组多集,并且每一组多集的范围内,每多集必须是唯一我工作的最后期限。而我不是一个有经验的编码器,所以我想避免创造新的算法,如果可能的话,这似乎是最Python化的方式,以确保我有独特的一堆东西的就是把它们放在一个
set()
但事情一定要哈希的。) 我已经从收集的意见
无论@marcin和@senderle了几乎相同的答案:使用hash(frozenset(self.items()))
这是有道理的,因为items()
“意见”设定类似 。 @marcin是第一,但我给查马克,因为运行时间不同的解决方案的大O的很好的研究,以@senderle。 @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