python - 哈希基和表大小如何影响哈希的时间复杂度？

Question

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

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

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

为什么选择 hashBase = 1 会增加哈希表操作的时间复杂度？为什么挑大tableCapacity比较好？另外，为什么 ie. hashBase = 250726 和 table capacity = 250727 导致其操作变慢？

Answer 1

tableCapacity通常应与将散列到表中的键数保持合理比率。究竟什么比例取决于哈希冲突的处理方式——即:

1. 将找到替代存储桶("open addressing" 又名“封闭哈希”):使用良好哈希函数，存储桶比键多 20-50%一个大致合理的范围

2. 每个桶都包含一些在那里散列的元素链("separate chaining"):使用好的散列函数它无关紧要，所以你可以有一半的桶作为 key ，或者两倍的 key ，事情会很顺利，没有任何戏剧性的事情发生

也就是说，当散列函数不好，并且被散列的键的随机性不足以帮助散列函数充分执行时，有一个 tableCapacity 是有帮助的。减少冲突:尝试从被散列的键数和上面列出的比率派生的值附近的任何质数。例如，如果您有 6 个键并使用单独的链接，则 tableCapacity 5、7 或 11 是理智的。

但是，您的问题并未说明如何处理碰撞，因此我们将其留给您。

让我们继续考虑哈希逻辑本身:

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

这就像 this question 中描述的“MAD”哈希方法的简化/折衷形式- my answer 中有解释以后我假设您已经阅读过。

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

总结:选择一个大的伪随机 hashBase - 说一个 32 位甚至 64 位的随机数，和一个素数 tableCapacity考虑到您选择的开/关散列设计，与您的 key 数量成合理的比例。

Why does picking hashBase = 1 increase the time complexity of the hash table's operations?

hashBase不应该很小 - 这意味着 key[i] 的贡献不太可能包装 h %之前绕过 table 很多次再次应用操作，失去了分散映射的所有好处。

Why is it better to pick a large tableCapacity?

好吧，更大的表意味着更多的桶 - 使用相同数量的键，冲突往往会更少，但通过适当的散列，您不需要过分。更多的桶意味着更多的内存使用和更少的缓存命中，这会减慢速度。

Also, why does ie. hashBase = 250726 and table capacity = 250727 cause its operations to slow down?

如上所述，您希望 hashBase 比表容量大得多。