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

问题描述：

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

我正在谈论返回哈希码的函数，该哈希码随后用于将对象插入到哈希表（又称字典）中。

由于__hash__()返回一个整数，并用于将对象“分箱”到哈希表中，我假设返回的整数值应该均匀分布于公共数据（以尽量减少冲突）。获取此类值的良好做法是什么？冲突是个问题吗？在我的例子中，我有一个小类，它充当容器类，包含一些整数、一些浮点数和一个字符串。

解决方案 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__还包含更多信息，这些信息在某些特定情况下可能会有价值。

解决方案 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 文档现在建议使用元组，如上例所示。请注意，文档中指出

唯一需要的属性是比较相等的对象具有相同的哈希值

请注意，反之则不然。比较结果不相等的对象可能具有相同的哈希值。只要对象比较结果不相等，这种哈希冲突就不会导致一个对象在用作字典键或集合元素时替换另一个对象。

过时/糟糕的解决方案

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))来捕获被散列的值的顺序。^ hash(...)如果组合的值无法重新排列（例如，如果它们具有不同的类型，因此的值_a永远不会分配给_b或_c，等等），则可以删除此最终值。

解决方案 3：

微软研究院的 Paul Larson 研究了各种各样的哈希函数。他告诉我

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

对于各种字符串，它的效果都出奇地好。我发现类似的多项式技术对于计算不同子字段的哈希值也非常有效。

解决方案 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__不需要哈希，但是很容易实现）。

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

obj = A(2, 2.2, "cat")
hash(obj)  # 977171927842460677
dict(obj)  # {'a': 2, 'b': 2.2, 'c': 'cat'}
list(obj)  # [('a', 2), ('b', 2.2), ('c', 'cat')]
tuple(obj) # (('a', 2), ('b', 2.2), ('c', 'cat'))
assert obj == A(2, 2.2, "cat")
assert obj != A(2, 2.2, "cats")

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

hash(A(2, 2.2, [1]))  # TypeError: unhashable type: 'list'

解决方案 5：

我可以尝试回答你问题的第二部分。

冲突可能不是由哈希码本身引起的，而是由将哈希码映射到集合中的索引引起的。例如，您的哈希函数可以返回 1 到 10000 之间的随机值，但如果您的哈希表只有 32 个条目，则插入时会发生冲突。

此外，我认为冲突将由集合内部解决，并且有许多方法可以解决冲突。最简单（也是最糟糕的）的方法是，给定一个要在索引 i 处插入的条目，将 i 加 1，直到找到一个空位并插入那里。然后检索以相同的方式工作。这会导致某些条目的检索效率低下，因为您可能需要遍历整个集合才能找到某个条目！

其他冲突解决方法通过在插入项目时移动哈希表中的条目来减少检索时间，以分散内容。这会增加插入时间，但假设您读取的内容多于插入的内容。还有一些方法尝试将不同的冲突条目分支出来，以便条目聚集在一个特定的位置。

此外，如果您需要调整集合大小，则需要重新散列所有内容或使用动态散列方法。

简而言之，根据您使用哈希码的目的，您可能必须实现自己的冲突解决方法。如果您不将它们存储在集合中，您可能可以使用仅在很大范围内生成哈希码的哈希函数。如果是这样，您可以确保您的容器比它需要的更大（当然越大越好），这取决于您的内存问题。

如果您有兴趣的话，这里有一些链接：

维基百科上的合并哈希

维基百科也对各种碰撞解决方法进行了总结：

此外，Tharp 的《文件组织与处理》广泛涵盖了许多冲突解决方法。在我看来，它是哈希算法的绝佳参考。

解决方案 6：

programiz 网站__hash__上对何时以及如何实现该功能进行了很好的解释：

仅提供一张截图以供概览：（检索日期：2019-12-13）

至于该方法的个人实现，上面提到的网站提供了一个与millerdev的答案相匹配的示例。

class Person:
def __init__(self, age, name):
    self.age = age
    self.name = name

def __eq__(self, other):
    return self.age == other.age and self.name == other.name

def __hash__(self):
    print('The hash is:')
    return hash((self.age, self.name))

person = Person(23, 'Adam')
print(hash(person))

解决方案 7：

@dataclass(frozen=True)（Python 3.7）

这个很棒的新功能会自动为您定义一个__hash__and__eq__方法，使其能够像在字典和集合中通常预期的那样工作，而无需任何繁琐的重复：

数据类_cheat.py

from dataclasses import dataclass, FrozenInstanceError

@dataclass(frozen=True)
class MyClass1:
    n: int
    s: str

@dataclass(frozen=True)
class MyClass2:
    n: int
    my_class_1: MyClass1

d = {}
d[MyClass1(n=1, s='a')] = 1
d[MyClass1(n=2, s='a')] = 2
d[MyClass1(n=2, s='b')] = 3
d[MyClass2(n=1, my_class_1=MyClass1(n=1, s='a'))] = 4
d[MyClass2(n=2, my_class_1=MyClass1(n=1, s='a'))] = 5
d[MyClass2(n=2, my_class_1=MyClass1(n=2, s='a'))] = 6

assert d[MyClass1(n=1, s='a')] == 1
assert d[MyClass1(n=2, s='a')] == 2
assert d[MyClass1(n=2, s='b')] == 3
assert d[MyClass2(n=1, my_class_1=MyClass1(n=1, s='a'))] == 4
assert d[MyClass2(n=2, my_class_1=MyClass1(n=1, s='a'))] == 5
assert d[MyClass2(n=2, my_class_1=MyClass1(n=2, s='a'))] == 6

# Due to `frozen=True` we can't modify objects.
o = MyClass1(n=1, s='a')
try:
    o.n = 2
except FrozenInstanceError as e:
    pass
else:
    raise 'error'

正如我们在本例中看到的，哈希值是根据对象的内容计算的，而不是简单地根据实例的地址计算的。这就是为什么像这样的事情：

d = {}
d[MyClass1(n=1, s='a')] = 1
assert d[MyClass1(n=1, s='a')] == 1

即使第二个MyClass1(n=1, s='a')实例与第一个实例完全不同并且具有不同的地址，它仍然可以工作。

frozen=True是强制性的，否则该类不可哈希，否则用户可能会在将对象用作键后修改对象，从而无意中导致容器不一致。更多文档：https://docs.python.org/3/library/dataclasses.html

@dataclass还提供其他好东西，比如__str__，太棒了。

在 Python 3.10.7、Ubuntu 22.10 上测试。

解决方案 8：

取决于您返回的哈希值的大小。逻辑很简单，如果您需要根据四个 32 位整数的哈希值返回一个 32 位整数，那么您将遇到冲突。

我更喜欢位操作。例如，以下 C 伪代码：

int a;
int b;
int c;
int d;
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F);

这样的系统也可以适用于浮点数，如果您只是将它们视为它们的位值而不是实际表示浮点值，可能会更好。

对于字符串，我知之甚少或者一无所知。

解决方案 9：

我认为，由于当今已知的定义，__hash__您必然无法同时实现“正确”和“良好”的实现。因此，让我们选择“良好”（因为公认的答案旨在实现“正确”）：

class Thing:
    def __hash__(self):
        return id(self)

    def __eq__(self, other):
        # it is advised to implement __eq__ when you implement __hash__
        # however this __eq__ impl has nothing to do with this being a 
        # "good" implementation of __hash__, it merely ensures correctness
        # of behavior for use in container types. you could obviously write
        # something more tailored to your class than this, this is merely
        # inheritance-friendly.
        if not isinstance(other, type(self)):            
            return False
        for aname in (set(dir(self)) | set (dir(other))):
            if aname.startswith('__'):
                continue
            if (not hasattr(self, aname)) or (not hasattr(other, aname)):
                return False
            atype = type(self.attr)
            if atype is types.MethodType or atype is types.FunctionType:
                continue
            if getattr(self, aname) != getattr(other, aname):
                return False
        return True

对于此实现，__hash__将生成一个在对象整个生命周期内唯一的值。对于存储到list或set（可访问性可防止对象破坏）的对象，这是可以接受的。

当用作 的键时dict，如果对象不再可访问且被销毁，则此键“可能”发生冲突。我们还必须考虑到，__hash__由于实现的差异，其他对象的结果“也可能”发生冲突。出于这些原因，容器的实现通常检查对象相等性（无论是在 Python 中还是在其他语言中，因为用于容器标识的对象哈希概念并不是 Python 独有的概念。）

有一些方法可以不依赖任何因素来解决冲突问题__eq__，但最好留到下次问答时再讨论，这确实值得容器开发人员而不是使用其容器的开发人员考虑。

无论如何，这种实现具有高效和简单的价值，并且不会因依赖__hash__诸如 之类的“正确”实现而导致冲突Tuple。理想情况下，首先通过__hash__结果比较来解决对象身份，从而避免对结果进行额外调度__eq__。

为了演示此实现，请考虑以下子类以及unittest用于验证的类：

class SubThing(Thing):
    def __init__(self, val1, val2):
        if val1 != None:
            self.val1 = val1
        if val2 != None:
            self.val2 = val2

import unittest
class ThingTests(unittest.TestCase):
    def test_Things(self):
        t1 = Thing()
        t2 = Thing()
        self.assertEqual(t1, t2)
        set1 = set()
        set1.add(t1)
        set1.add(t2)
        set1.add(t1)
        set1.add(t2)
        self.assertEqual(2, len(set1))
        t3 = SubThing(1,2)
        t4 = SubThing(1,2)
        t5 = SubThing(2,3)
        t6 = SubThing(None,None)
        t7 = SubThing(None,5)
        t8 = SubThing(5,None)
        set2 = set()
        set2.add(t3)
        set2.add(t4)
        set2.add(t5)
        set2.add(t6)
        set2.add(t7)
        set2.add(t8)
        self.assertEqual(6, len(set2))
        self.assertEqual(t1, t2)
        self.assertEqual(t3, t4)
        self.assertNotEqual(t1, t3)
        self.assertNotEqual(t3, t4)
        self.assertNotEqual(t4, t5)
        self.assertNotEqual(t5, t6)
        self.assertNotEqual(t6, t7)
        self.assertNotEqual(t7, t8)

测试通过。

结论

这个实现是“好的”但是它不是“正确的”，为什么？

因为当前的 Python 规范定义__hash__了这样的约束：两个在相等性测试中返回 true 的对象也必须返回相同的哈希值。糟糕。这可能会永远困扰 Python。但这并不意味着您需要编写幼稚的代码。上述内容将符合除最差的容器实现（那些愚蠢地依赖对象相等而不是对象哈希的容器实现）之外的所有要求，并且如果有一个容器实现由于上述原因而行为不当__hash__，那么该实现值得被调出并修复。