hash的返回值如何使用？

3 投票

3 回答

581 浏览

提问于 2025-04-17 13:29

假设我写了一个类，但没有为它定义 __hash__ 方法。那么根据文档，__hash__(self) 默认会返回 id(self)，也就是这个对象在内存中的地址。

不过我在文档中没有看到这个值是怎么被使用的。
比如说，如果我的 __hash__ 方法只是简单地返回 1，那么我这个类的所有实例的哈希值都会是一样的，它们都会被放到同一个哈希桶里（我猜这个是用C语言实现的）。但是，这并不意味着 __hash__ 返回的值会直接作为这个哈希表中元素的键。
所以，我真正想问的是：__hash__ 返回的值会发生什么？它是直接作为键使用，还是经过某种计算后（比如再哈希一下）才作为哈希表的键？

如果有关系的话，我用的是python2.7

编辑：为了更清楚，我不是在问哈希冲突是怎么处理的。在Python中，这似乎是通过线性链表来处理的。我想问的是 __hash__ 返回的值是怎么转化为对应桶的内存地址的（？）。

对象方法数据模型哈希表内存地址哈希值哈希冲突线性链表哈希桶

3 个回答

从代码使用哈希表的角度来看，实际上对象本身就是键。如果你在哈希表中查找键 "foo"，无论哈希表中其他对象的哈希值是否与 "foo" 相同，只有当哈希表中存储的键值对的键确实等于 "foo" 时，才会返回对应的值。

我不太清楚 Python 的具体实现，但哈希表的实现必须考虑哈希冲突。如果哈希表的数组有 N 个槽位，那么如果你插入了 N + 1 个值（而且没有先调整表的大小），就一定会发生冲突。此外，就像你提到的情况，__hash__ 总是返回 1，或者由于哈希函数的实现特点，可能会有两个对象的哈希值完全相同。

在内存中处理哈希表的哈希冲突主要有两种策略（对于分布式哈希表等会有不同的技术）：

数组中的每个槽位都是一个列表（通常是链表），所有哈希到 k 取模 N 的值都放在槽位 k 的列表中。所以如果哈希值发生冲突，这并不是问题，因为具有相同哈希值的对象会最终放在同一个列表里。
某种探测方案。基本上，如果你要插入的对象的哈希值等于 k 取模 N，你就查看槽位 k。如果这个槽位已经满了，你就对当前位置应用某个公式（可能只是加 1），然后查看下一个槽位。你会根据原始哈希值和到目前为止的探测次数，按照一定的规律选择下一个槽位，继续探测直到找到一个空槽位。这种方法使用得较少，因为如果实现不当，可能会出现聚集问题，也就是需要探测很多次才能找到对象。

维基百科对哈希表的实现有更多的讨论，可以在这里查看。

回答于 2025-04-17 由 Python大师

分享举报

当一个对象被存储在字典里时，__hash__这个东西会用来决定这个对象放在哪个“箱子”里。不过，这并不意味着字典会把一个对象搞混成另一个对象——它们还是会检查对象是否相等。只是说，对于这种类型的对象，字典在处理它们的时候会稍微慢一点。

回答于 2025-04-17 由 Python大师

分享举报

因为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的数组，每个条目的形式是(hash, key, value)：

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

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

回答于 2025-04-17 由 Python大师

分享举报

__hash__的返回值如何使用？

3 个回答

撰写回答

hash的返回值如何使用？