哈希基数和 table 大小如何影响哈希的时间复杂度？
How does the hash base and table size affect the time complexity of the hash?
上周我学习了哈希 tables，但我想知道为哈希基选择的最佳值是多少，以及我的哈希函数的 table 大小是多少以良好的时间复杂度进行操作。
这是我的哈希函数的代码：
h = 0
for i in range(len(key)):
h = (h * hashBase + ord(key[i])) % tableCapacity
return h
为什么选择 hashBase = 1 会增加散列 table 操作的时间复杂度？为什么挑大table容量比较好？另外，为什么 ie. hashBase = 250726 和 table capacity = 250727 导致其操作变慢？
tableCapacity 通常应与将散列到 table 中的键数保持 合理的 比率。究竟什么比例取决于哈希冲突的处理方式——即：
将找到替代桶（"open addressing" 又名 "closed hashing"）：好 哈希函数比键多 20-50% 的桶是一个通常合理的范围
每个桶都包含一些在那里散列的元素链 ("separate chaining")：使用 good 散列函数它并不重要，因此您可以拥有的桶数量是钥匙数量的一半，或者是钥匙数量的两倍，并且事情会顺利进行而不会有任何戏剧性的变化
就是说，当散列函数不好，并且被散列的键的随机性不足以帮助散列函数充分执行时，tableCapacity 有助于减少冲突：尝试从 number-of-keys-being-hashed 和上面列出的比率得出的值附近的任何质数。例如，如果您有 6 个键并使用单独的链接，则 tableCapacity 5、7 或 11 是合理的。
但是，您的问题没有说明如何处理碰撞，所以我们将把它留给您。
让我们继续考虑哈希逻辑本身：
h = (h * hashBase + ord(key[i])) % tableCapacity
这就像 - there's an explanation in 中描述的 "MAD" 散列方法的简化/折衷形式，我假设您已经阅读了下文。
如果我们将您的函数与一般 MAD 形式进行对比，我们会发现您在密钥的每个切片（字节？）上都使用了 % tableCapacity。在 python 中可能有意义的原因是 python 没有像许多 lower-level 语言（以及 CPU 本身）那样溢出的 fixed-number-of-bit 整数，因此，如果您在循环内没有一些 % 操作， h 值可能会增长到与整个密钥相似的大小 - 如果您正在生成视频文件的哈希值作为廉价校验和，那将非常缓慢并且浪费内存。因此，使用 % 来限制每次迭代后 h 的大小是理智的，但是由于另一个答案中解释的原因， tableCapacity 是质数尤为重要，并且 hashBase 应该被选择为通常产生比 tableCapacity 大得多的值，以最小化早期哈希桶比后来的哈希桶被更频繁地使用的数量（参见我上面链接的其他答案中的 200/255 示例）。
总结一下：选择一个大的 pseudo-random hashBase - 比如说一个 32 位甚至 64 位的随机数，以及一个与你的键数成合理比例的素数 tableCapacity open/close-hashing 您选择的设计。
Why does picking hashBase = 1 increase the time complexity of the hash table's operations?
hashBase 不应该很小——这意味着 key[i] 的贡献不太可能在 % 操作再次应用，失去了分散映射的所有好处。
Why is it better to pick a large tableCapacity?
好吧，更大的 tables 意味着更多的桶 - 使用相同数量的键，冲突往往会更少，但是通过适当的散列，你不需要过分。更多的桶意味着更多的内存使用和更少的缓存命中，这会减慢速度。
Also, why does ie. hashBase = 250726 and table capacity = 250727 cause its operations to slow down?
如上所述，您希望 hashBase 比 table 容量大得多。
上周我学习了哈希 tables，但我想知道为哈希基选择的最佳值是多少，以及我的哈希函数的 table 大小是多少以良好的时间复杂度进行操作。
这是我的哈希函数的代码：
h = 0
for i in range(len(key)):
h = (h * hashBase + ord(key[i])) % tableCapacity
return h
为什么选择 hashBase = 1 会增加散列 table 操作的时间复杂度？为什么挑大table容量比较好？另外，为什么 ie. hashBase = 250726 和 table capacity = 250727 导致其操作变慢？
tableCapacity 通常应与将散列到 table 中的键数保持 合理的 比率。究竟什么比例取决于哈希冲突的处理方式——即：
将找到替代桶（"open addressing" 又名 "closed hashing"）：好 哈希函数比键多 20-50% 的桶是一个通常合理的范围
每个桶都包含一些在那里散列的元素链 ("separate chaining")：使用 good 散列函数它并不重要，因此您可以拥有的桶数量是钥匙数量的一半，或者是钥匙数量的两倍，并且事情会顺利进行而不会有任何戏剧性的变化
就是说，当散列函数不好，并且被散列的键的随机性不足以帮助散列函数充分执行时，tableCapacity 有助于减少冲突：尝试从 number-of-keys-being-hashed 和上面列出的比率得出的值附近的任何质数。例如，如果您有 6 个键并使用单独的链接，则 tableCapacity 5、7 或 11 是合理的。
但是，您的问题没有说明如何处理碰撞，所以我们将把它留给您。
让我们继续考虑哈希逻辑本身：
h = (h * hashBase + ord(key[i])) % tableCapacity
这就像
如果我们将您的函数与一般 MAD 形式进行对比，我们会发现您在密钥的每个切片（字节？）上都使用了 % tableCapacity。在 python 中可能有意义的原因是 python 没有像许多 lower-level 语言（以及 CPU 本身）那样溢出的 fixed-number-of-bit 整数，因此，如果您在循环内没有一些 % 操作， h 值可能会增长到与整个密钥相似的大小 - 如果您正在生成视频文件的哈希值作为廉价校验和，那将非常缓慢并且浪费内存。因此，使用 % 来限制每次迭代后 h 的大小是理智的，但是由于另一个答案中解释的原因， tableCapacity 是质数尤为重要，并且 hashBase 应该被选择为通常产生比 tableCapacity 大得多的值，以最小化早期哈希桶比后来的哈希桶被更频繁地使用的数量（参见我上面链接的其他答案中的 200/255 示例）。
总结一下：选择一个大的 pseudo-random hashBase - 比如说一个 32 位甚至 64 位的随机数，以及一个与你的键数成合理比例的素数 tableCapacity open/close-hashing 您选择的设计。
Why does picking hashBase = 1 increase the time complexity of the hash table's operations?
hashBase 不应该很小——这意味着 key[i] 的贡献不太可能在 % 操作再次应用，失去了分散映射的所有好处。
Why is it better to pick a large tableCapacity?
好吧，更大的 tables 意味着更多的桶 - 使用相同数量的键，冲突往往会更少，但是通过适当的散列，你不需要过分。更多的桶意味着更多的内存使用和更少的缓存命中，这会减慢速度。
Also, why does ie. hashBase = 250726 and table capacity = 250727 cause its operations to slow down?
如上所述，您希望 hashBase 比 table 容量大得多。