algorithm - 哈希函数的输出是否需要限制为小于桶的数量？

Question

我正在阅读有关此人“在一家知名搜索公司”的采访。

http://asserttrue.blogspot.com/2009/05/one-of-toughest-job-interview-questions.html

有人问了他一个问题，导致他实现了一个哈希表。他说了以下的话:

HASH = INITIAL_VALUE;
FOR EACH ( CHAR IN WORD ) {
HASH *= MAGIC_NUMBER
HASH ^= CHAR
HASH %= BOUNDS
}
RETURN HASH

I explained that the hash table array length should be prime, and the BOUNDS number is less than the table length, but coprime to the table length.

为什么 BOUNDS 数量应该小于桶的数量？与表长度互质有什么作用？它不是应该与边界互质吗？

Answer 1

我敢说他是完全错误的。 BOUNDS 应该是存储桶的数量，否则最后几个存储桶将未被充分利用。

此外，输出对存储桶数量的限制应该在哈希函数之外。这是该特定哈希表的实现细节。您可能有一个非常大的表，使用大量的存储桶，而另一个则使用很少的存储桶。两者应该共享相同的字符串->哈希函数

此外，如果您阅读链接到的页面，它会非常有趣。我会将他的哈希表实现为大约 10,000 个存储桶 - 对于那些还没有读过它的人，文章建议使用约 4,000,000,000 个存储桶来存储 1,000,000 个左右可能的单词。对于冲突，每个桶都有一个字结构向量，每个向量都包含一个计数、一个明文字符串和一个哈希值(桶内唯一)。这将使用更少的内存，并且可以更好地与现代缓存配合使用，因为您的工作集会小得多。

为了进一步减少内存使用量，您可以尝试在输入阶段从哈希中剔除根据当前计数看起来低于前 100,000 个的单词。