散列基数和表大小如何影响散列的时间复杂度？

Question

上周我正在学习哈希表，但我想知道为哈希基选择的最佳值是什么，以及哈希函数的表大小，以便它能够在良好的时间复杂度上运行。

这是我的哈希函数的代码：

h = 0
for i in range(len(key)):
    h = (h * hashBase + ord(key[i])) % tableCapacity
return h

为什么选择 hashBase = 1 会增加哈希表操作的时间复杂度？为什么选择大桌子容量更好？另外，为什么 ie。hashBase = 250726 和表容量 = 250727 导致其操作变慢？

Answer 1

tableCapacity通常应该与将被散列到表中的键的数量保持合理的比例。确切的比率取决于如何处理散列冲突 - 即：

1. 将找到替代桶（“开放寻址”又名“封闭散列”）：具有良好的散列函数的桶比键多 20-50% 是一个通常合理的范围

2. 每个存储桶都包含一些散列在那里的元素链（“单独的链接”）：如果散列函数很好，它就没有那么重要了，因此您可以拥有与键一样多的存储桶，或者两倍的存储桶，事情就会变得不稳定没有任何伟大的戏剧

也就是说，当散列函数不好，并且被散列的键不够随机以帮助散列函数充分执行时，它有助于tableCapacity减少冲突：尝试围绕从该数派生的值的任何质数-of-keys-being-hashed 和上面列出的比率。例如，如果您有 6 个键并且使用单独的链接tableCapacity，则 5、7 或 11 的 a 将是合理的。

但是，您的问题并没有说明如何处理碰撞，所以我们将把它留给您。

让我们继续考虑散列逻辑本身：

h = (h * hashBase + ord(key[i])) % tableCapacity

这就像这个问题中描述的“MAD”哈希方法的简化/妥协形式-我的答案中有一个解释，我将在此后假设您已经阅读。

如果我们将您的函数与一般 MAD 形式进行对比，我们会看到您在% tableCapacity键的每个切片（字节？）上使用。在 python 中可能有意义的原因是 python 没有像许多低级语言（和 CPU 本身）那样溢出的固定位数的整数，所以如果你%在循环中没有一些操作该h值可能会增长到与整个密钥相似的大小 - 如果您生成视频文件的哈希作为廉价校验和，那将非常缓慢且浪费内存。因此，使用%来限制h每次迭代后可以获得多大是合理的，但出于另一个答案中解释的原因，tableCapacity质数尤其重要，并且hashBase应该选择通常产生比tableCapacity 尽量减少较早的哈希桶比后来的哈希桶更频繁地使用的数量（请参阅上面链接的其他答案中的 200/255 示例）。

总结：选择一个大的伪随机数hashBase——比如一个 32 位甚至 64 位的随机数，以及一个tableCapacity与您选择的打开/关闭散列设计的密钥数量成正比的素数。

为什么选择 hashBase = 1 会增加哈希表操作的时间复杂度？

hashBase不应该很小 - 这意味着在再次应用操作之前，的贡献key[i]不太可能h在表周围多次环绕%，从而失去分散映射的所有好处。

为什么选择大桌子容量更好？

好吧，更大的表意味着更多的存储桶 - 使用相同数量的键，冲突往往会更少，但是有了不错的散列，你就不需要太过分了。更多的桶意味着更多的内存使用，更少的缓存命中，这会减慢速度。

另外，为什么 ie。hashBase = 250726 和表容量 = 250727 导致其操作变慢？

如上所述，您希望 hashBase 远大于表容量。