哈希Python中一个不变的词典(Hashing an immutable dictionary i

2019-07-28 20:20发布

短版:什么是对的无序项目的字典实现一个多重的最佳哈希算法?

我想凑一个不可变多集(这是其他语言包或多重集:像数学集合,但它可以保持每个元素的不止一个)作为字典实现。 我创建了标准库类的子类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

Answer 1:

因为字典是不可变的,你可以创建哈希创建字典时,直接返回。 我的建议是建立一个frozensetitems (在3+ iteritems 2.7),散列它,并存储哈希值。

为了提供一个明显的例子:

>>>> 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_hashset_next实现。



Answer 2:

你有没有考虑hash(sorted(hash(x) for x in self.items())) 这样一来,你只排序整数,而不必建立一个列表。

你也可以异或元素哈希在一起,但坦率地说,我不如何,将工作(你将有很多冲突的?)。 说起冲突的,你不必须实现__eq__方法?

另外,类似于我的答案在这里 , hash(frozenset(self.items()))



文章来源: Hashing an immutable dictionary in Python