__hash__方法的返回值有什么用途？

Question

假设我写了一个类，但没有为其定义__hash__。根据文档，__hash__(self)将默认为id(self)（即self的内存地址）。

然而，我没有在文档中看到这个值是如何被使用的。
因此，如果我的__hash__只是简单地返回1，这将导致我的类的所有实例的哈希值相同，它们都会被分配到同一个底层哈希桶中（我假设这是用C实现的）。但是，这并不意味着__hash__的返回值被用作底层哈希表中元素的键。
所以，我的问题是：__hash__返回的值会发生什么？它是直接用作键，还是其哈希值（或对其执行的某些其他计算的结果）用作哈希表的键？

如果有关系的话，我正在使用Python 2.7。

编辑：澄清一下，我不是在问如何处理哈希冲突。在Python中，这似乎是通过线性链接完成的。相反，我想知道__hash__的返回值如何转换为相应桶的内存地址（？）。

- inspectorG4dget

---

可能是Python. Identity in sets of objects. And hashing的重复问题。 - BrenBarn

@BrenBarn：这不是那个问题的重复。那个问题问哈希如何工作以及为什么等效对象不会在集合中重复。我的问题是__hash__的输出如何转换为存储该对象的桶的内存位置。 - inspectorG4dget

我认为这并不是由语言定义的，因为Python的大部分方面并没有以那种粒度来定义。行为是有定义的，就像我在链接的帖子中描述的那样（以及其他帖子中提到的）。 - BrenBarn

另外，我不太明白你所说的“底层哈希表”是什么意思。底层的哈希表是指什么？__hash__只在对对象进行哈希（例如用于字典或集合）时使用。如果您从未以需要对其进行哈希的方式使用对象，则其__hash__的内容并不重要。 - BrenBarn

@BrenBarn: 底层哈希桶（我假设是用C实现的），即Python字典的底层是一个哈希表（其中有桶），由C实现。 - inspectorG4dget

注意，Python不使用线性链式表示法，而是使用了一种特定的开放寻址机制，如Raymond所述。虽然我不确定它是否有一个特定的名称。 - Lie Ryan

Answer 1

由于Python的哈希表大小是2的幂，因此哈希值的低位确定了哈希表中的位置（或者至少确定了初始探测位置）。

对于表大小为n的探测序列如下：

def gen_probes(hashvalue, n):
    'Same sequence of probes used in the current dictionary design'
    mask = n - 1
    PERTURB_SHIFT = 5
    if hashvalue < 0:
        hashvalue = -hashvalue
    i = hashvalue & mask
    yield i
    perturb = hashvalue
    while True:
        i = (5 * i + perturb + 1) & 0xFFFFFFFFFFFFFFFF
        yield i & mask
        perturb >>= PERTURB_SHIFT

例如，这个词典：

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

这个数据被存储为一个大小为8的数组，每个条目的形式为(哈希值, 键, 值)：

entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

您可以在这里找到Python字典中键插入的C源代码：http://hg.python.org/cpython/file/cd87afe18ff8/Objects/dictobject.c#l550

。该代码涉及IT技术，如果需要，我可以帮您进一步解释。

- Raymond Hettinger

Answer 2

当一个对象被存储在字典中时，__hash__会被用来确定该对象所在的原始bin。然而，这并不意味着一个对象会与另一个对象在字典中混淆——它们仍然会检查对象的相等性。这只是意味着字典在对这种类型的对象进行哈希时会稍微慢一些。

- David Robinson

---

__hash__ 用于确定原始 bin - 但是如何实现呢？我知道 __hash__ 的返回值与桶（基本上是一个内存位置）之间有严格的一对一对应关系（似乎使用线性链来处理碰撞）。但是，__hash__ 返回的 int 如何转换为该内存地址呢？ - inspectorG4dget

@inspectorG4dget: “我知道有一个严格的一对一映射” - 不完全是这样。不同的对象可以映射到同一个bin中 - 当发生这种情况时，Python字典会处理冲突。这是Python字典实现的很好的总结。 - David Robinson

诚实的问题，如果这是真的，为什么{True:'a',1:'b'}评估为{True:'b'}？（True和1都哈希到1。） - user1107907

@BrianMarshall：不错的发现！看起来是因为 True == 1 - 这意味着哈希表正在测试相等而不是身份。两个对象可以返回相同的哈希值，但仍然不能 ==。 （演示：class Obj2(object): pass; Obj2.__hash__ = lambda s: 1; print hash(Obj2()) == hash(Obj2()); print Obj2() == Obj2()。lambda 部分只是为了让我用分号在一行中定义它们）。 - David Robinson

Answer 3

当然，从使用哈希表的代码的逻辑上来看，对象本身就是键。如果在哈希表中搜索键“foo”，无论哈希表中有哪些其他对象具有与“foo”相同的哈希值，只有在哈希表中存储的键值对之一的键等于“foo”时，才会返回相应的值。

我不知道Python确切的做法，但哈希表实现必须考虑哈希冲突。如果哈希表数组有N个插槽，则如果您插入N + 1个值（并且在调整大小之前未调整表格大小），则必须存在冲突。此外，就像您提到的__hash__始终返回1的情况一样，或者仅作为哈希函数实现的怪癖，可能存在两个具有完全相同哈希码的对象。

在内存中单台计算机的哈希表中处理哈希冲突有两种主要策略（分布式哈希表等使用不同技术）：

数组中的每个槽位都是一个列表（通常是链表），所有哈希到 k 模 N 的值都被放置到 k 号槽位的列表中。所以如果哈希值冲突，那不是问题，因为具有相同哈希值的对象最终会被放置在同一个列表中。

某种探测方案。基本上，如果要插入的对象具有等于 k 模 N 的哈希值，则查看 k 号槽位。如果已满，则对当前位置应用某个公式（可能只需加1），并查看下一个槽位。根据原始哈希值和迄今为止的探测次数选择下一个槽位，并不断探测，直到找到一个空闲槽位。这种方法使用较少，因为如果您没有注意实现，就可能遇到聚集问题，即在找到对象之前必须进行多次探测。

维基百科在这里更详细地讨论了哈希表实现。

- Adam Mihalcin

---

我对哈希算法有工作上的理解。请查看我的编辑以澄清问题。 - inspectorG4dget