如何正确且有效地实现__hash__()?

Question

怎样正确且有效地实现 __hash__() 函数呢？

我说的是这个函数，它会返回一个哈希值，这个哈希值会用来把对象放进哈希表，也就是字典里。

因为 __hash__() 返回的是一个整数，并且这个整数是用来把对象“分箱”的，所以我认为返回的整数值应该是均匀分布的，这样可以减少碰撞的发生。有什么好的方法可以得到这样的值吗？碰撞会是个问题吗？在我的例子中，我有一个小类，它是一个容器类，里面存放了一些整数、一些浮点数和一个字符串。

Answer 1

微软研究院的保罗·拉尔森研究了很多种哈希函数。他告诉我，

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

对于各种不同的字符串，这种方法效果出乎意料地好。我发现类似的多项式技术在计算不同子领域的哈希值时也表现得很好。

Answer 2

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

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文档推荐使用上面示例中的元组。请注意，文档中提到：

唯一的必要条件是，相等的对象必须有相同的哈希值。

但反过来就不一定成立。不同的对象可能会有相同的哈希值。如果发生这样的哈希冲突，当这些对象用作字典的键或集合的元素时，只要这些对象不相等，就不会互相替换。

过时/不好的解决方案

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)))

更新：正如Blckknght所指出的，改变a、b和c的顺序可能会导致问题。我添加了一个额外的^ hash((self._a, self._b, self._c))来捕捉哈希值的顺序。如果组合的值不能被重新排列（例如，如果它们有不同的类型，因此_a的值永远不会被赋值给_b或_c等），那么这个最终的^ hash(...)可以去掉。

Answer 3

实现 __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__ 的文档中还有更多信息，这在某些特定情况下可能会很有用。