2

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

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

我解释了哈希表数组长度应该是素数，并且 BOUNDS 数小于表长度，但与表长度互质。

为什么 BOUNDS 数应该小于桶数？与桌子长度互质有什么作用？它不应该与 BOUNDS 互质吗？

4

3 回答 3

4

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

此外，输出与桶数的界限应该在散列函数之外。这是该特定哈希表的实现细节。您可能有一张非常大的桌子，使用很多桶，而另一张桌子使用的桶很少。两者应该共享相同的字符串->哈希函数

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

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

于 2009-05-13T04:02:13.620 回答
0

我曾经在一家知名的搜索公司面试过一份工作。我得到了完全相同的问题。我试图通过使用哈希表来解决它。

我从那次采访中学到的一件事是，在一家著名的搜索公司，你不会提出哈希作为解决方案。你可以使用任何你喜欢的树状结构，但你总是使用有序结构，而不是哈希表。

于 2009-05-13T08:53:08.093 回答
0

一个简单的显式后缀树只会使用最坏的情况，可能是 500k 内存（具有中等效率的实现，4 字节字符编码，以及具有最小重叠的相对较长的英文单词）来做同样的事情。

我认为文章中的那个人比自己聪明。

于 2009-05-19T18:31:02.190 回答