python - __hash__ 的返回值是如何使用的？

Question

假设我写了一个类，但没有为它定义一个__hash__。然后__hash__(self)默认为id(self)(self的内存地址)，根据the documentation .

但是我没有在文档中看到这个值是如何使用的。
因此，如果我的 __hash__ 只是 return 1，这将导致我的类的所有实例的哈希值都相同，它们都将被放入相同的底层哈希桶中(我假设是在 C 中实现的)。但是，这并不意味着 __hash__ 的返回值被用作此底层哈希表中 bin 元素的键。
所以真的，我的问题是:__hash__ 返回的值发生了什么？它是直接用作键，还是它的哈希(或对其执行的某些其他计算的结果)用作哈希表的键？

以防万一，我在python2.7上

编辑:澄清一下，我不是在询问哈希冲突是如何处理的。在 python 中，this seems to be done with linear chaining .相反，我问的是 __hash__ 的返回值如何转换为相应存储桶的内存地址(？)。

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 的数组，每个条目的形式为 (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