什么是实现hash的正确而好的方法？

Question

实现__hash__()的正确而好的方法是什么？

我说的是一个函数，它返回一个hashcode，然后用于将对象插入hashtables（也称为字典）中。

由于__hash__()返回一个整数，并用于将对象“装箱”到哈希表中，因此我假设返回的整数的值应均匀分布于公共数据（以最小化冲突）。 获得这样的价值观有什么好的做法？碰撞是个问题吗？ 在我的例子中，我有一个小类，它充当一个容器类，包含一些int、一些float和一个string。

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

此外，documentation of ^{}还有更多的信息，这些信息在某些特定情况下可能很有价值。

Answer 2

微软研究院的保罗·拉森研究了各种各样的散列函数。他告诉我的

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

适用于各种弦，效果出奇的好。我发现类似的多项式技术可以很好地计算不同子字段的散列。

Answer 3

约翰·米利金提出了一个类似的解决方案：

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文档现在建议使用一个元组，如上面的例子所示。请注意，文档说明

The only required property is that objects which compare equal have the same hash value

请注意，事实并非如此。不比较等于的对象可能具有相同的哈希值。这种散列冲突在用作dict键或set元素时不会导致一个对象替换另一个对象，只要这些对象不同时比较equal。

过时/错误的解决方案

该Python documentation on ^{}建议使用类似于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)))

更新：正如Blckknght指出的，更改a、b和c的顺序可能会导致问题。我添加了一个附加的^ hash((self._a, self._b, self._c))来捕获被散列的值的顺序。如果无法重新排列要组合的值（例如，如果它们具有不同的类型，因此_a的值永远不会分配给_b或_c等），则可以删除最后的^ hash(...)。