3

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

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

万一这很重要，我在 python2.7

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

4

3 回答 3

2

由于 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

于 2013-01-24T03:28:20.893 回答
1

当一个对象存储在字典中时，__hash__用于确定该对象所在的原始 bin。但是，这并不意味着一个对象会与字典中的另一个对象混淆——它们仍然会检查对象是否相等。这只是意味着字典在散列该类型的对象时会比其他对象慢一些。

于 2013-01-24T03:02:08.037 回答
0

当然在逻辑上（从使用哈希表的代码来看）对象本身就是关键。如果在哈希表中搜索key "foo"，无论哈希表中的其他哪些对象具有与 相同的哈希值"foo"，只有在哈希表中存储的键值对之一的键等于"foo".

我不确切知道Python做了什么，但哈希表实现必须考虑哈希冲突。如果哈希表数组有N槽，那么如果你插入N + 1值（并且表没有首先调整大小），那么肯定会发生冲突。此外，正如您提到的 where__hash__始终返回 1 的情况，或者只是作为散列函数实现的一个怪癖，可能有两个对象具有完全相同的散列码。

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

  1. 数组中的每个槽都是一个列表（通常是一个链表），所有散列到k模的值N都放在槽的列表中k。因此，如果散列值发生冲突，这不是问题，因为具有相同散列值的两个对象最终都在同一个列表中。
  2. 某种探测方案。基本上，如果您要插入的对象的哈希值等于kmodulo N，则查看 slot k。如果它已满，则将一些公式应用于当前位置（可能只是添加 1），然后查看下一个插槽。您按照常规模式选择下一个插槽，给定原始哈希值和到目前为止的探测次数，并继续探测直到找到一个开放的插槽。这很少使用，因为如果您对您的实现不小心，您可能会遇到集群问题，即在找到对象之前必须进行多次探测。

Wikipedia在这里讨论了更多关于哈希表实现的内容。

于 2013-01-24T03:10:17.460 回答