实现__hash __()的正确和好方法是什么？

Question

什么是正确和好的实施方式__hash__()？

我在谈论返回哈希码的函数,该哈希码随后用于将对象插入哈希表,即字典.

当__hash__()返回一个整数并用于将对象"分箱"为哈希表时,我假设返回的整数的值应该为公共数据均匀分布(以最小化冲突).获得这些价值观的好习惯是什么？碰撞是一个问题吗？在我的例子中,我有一个小类,它充当一个容器类,包含一些int,一些浮点数和一个字符串.

Answer 1

一种简单,正确的实现方法__hash__()是使用密钥元组.它不会像专门的哈希那么快,但如果你需要那么你应该在C中实现类型.

这是使用密钥进行哈希和相等的示例:

class A:
    def __key(self):
        return (self.attr_a, self.attr_b, self.attr_c)

    def __hash__(self):
        return hash(self.__key())

    def __eq__(self, other):
        if isinstance(other, A):
            return self.__key() == other.__key()
        return NotImplemented

此外,文档中__hash__包含更多信息,这些信息在某些特定情况下可能很有价值.

Answer 2

John Millikin提出了类似的解决方案:

class A(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        return (isinstance(othr, type(self))
                and (self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))

    def __hash__(self):
        return hash((self._a, self._b, self._c))

这个解决方案的问题在于hash(A(a, b, c)) == hash((a, b, c)).换句话说,哈希与其关键成员的元组的哈希冲突.也许这在实践中经常无关紧要？

在对Python文档__hash__建议使用类似XOR的子组件的哈希值相结合,这给了我们这样的:

class B(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        if isinstance(othr, type(self)):
            return ((self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))
        return NotImplemented

    def __hash__(self):
        return (hash(self._a) ^ hash(self._b) ^ hash(self._c) ^
                hash((self._a, self._b, self._c)))

奖金:^ hash((self._a, self._b, self._c))在那里投入更加强大,以获得良好的衡量标准.

更新:正如Blckknght指出的那样,改变a,b和c的顺序可能会导致问题.我添加了一个额外的^ hash(...)来捕获正在散列的值的顺序._a如果要组合的值不能重新排列(例如,如果它们具有不同的类型,因此_b永远不会将值分配给_c或hash(A(a, b, c)) == hash((a, b, c))等),则可以删除此最终结果.

Answer 3

Microsoft Research的Paul Larson研究了各种哈希函数.他告诉我

for c in some_string:
    hash = 101 * hash  +  ord(c)

对各种各样的琴弦都做得非常好.我发现类似的多项式技术可以很好地计算不同子场的散列.

Answer 4

实现哈希（以及列表、字典、元组）的一个好方法是通过使用 使其可迭代，从而使对象具有可预测的项目顺序__iter__。因此，修改上面的示例：

class A:

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __iter__(self):
        yield "a", self._a
        yield "b", self._b
        yield "c", self._c

    def __hash__(self):
        return hash(tuple(self))

    def __eq__(self, other):
        return (isinstance(other, type(self))
                and tuple(self) == tuple(other))

（这里__eq__不需要hash，但是很容易实现）。

现在添加一些可变成员来看看它是如何工作的：

a = 2; b = 2.2; c = 'cat'
hash(A(a, b, c))  # -5279839567404192660
dict(A(a, b, c))  # {'a': 2, 'b': 2.2, 'c': 'cat'}
list(A(a, b, c))  # [('a', 2), ('b', 2.2), ('c', 'cat')]
tuple(A(a, b, c)) # (('a', 2), ('b', 2.2), ('c', 'cat'))

只有当您尝试将不可散列的成员放入对象模型中时，事情才会崩溃：

hash(A(a, b, [1]))  # TypeError: unhashable type: 'list'