c - 如何设计一个可扩展到恰好 n 个元素的哈希函数？

Question

我有一个包含 n 个字符串(人名)的列表，我想将其存储在哈希表或类似结构中。我知道 n 的确切值，所以我想使用这个事实进行 O(1) 查找，如果我必须使用链表来存储我的哈希节点，这将变得不可能。我的第一 react 是使用 djb 哈希，它基本上是这样做的:

for ( i = 0; i < len; i++ )
    h = 33 * h + p[i];

要将生成的 h 压缩到 [0,n] 范围内，我喜欢简单地执行 h%n ，但我怀疑这会导致更高的冲突概率，从而使我的哈希变得毫无用处。

那么我的问题是，我如何对字符串或生成的哈希进行哈希处理，以便 n 元素在 [0,n] 上提供相对均匀的分布？

Answer 1

仅仅知道 n 是不够的。将项目分配到存储桶是项目本身的函数，因此，如果您想要一个完美的哈希函数(每个存储桶一个项目)，您需要知道数据。

在任何情况下，如果您将元素的数量限制为已知的 n，那么从技术上讲，您已经进行了 O(1) 查找。上限将基于常量 n。即使对于非哈希解决方案也是如此。

您最好的选择可能是只使用您拥有的散列函数，并让每个桶成为碰撞项目的链接列表。即使哈希不够完美，您仍然可以大大减少所花费的时间。

只有当哈希完全不完美(所有 n 元素都放在一个桶中)时，它才会像普通链表一样糟糕。

如果您事先不知道数据，完美的哈希是不可能的。当然，除非您使用 h 本身而不是 h%n 作为散列键，但这会占用大量存储空间:-)

我的建议是使用链表路由进行足够好的散列。我不怀疑你可以根据人群中人名中字母的相对频率来制作更好的散列函数，但即使你拥有的散列(这对于所有具有相同频率的字母来说都是理想的)也应该足够了。

而且，无论如何，如果您开始依赖频率，并且大量来自那些似乎不使用元音的国家(例如波斯尼亚^a)的人涌入，您最终会有更多的碰撞。

但请记住，这实际上取决于您使用的 n。

如果 n 足够小，您甚至可以对未排序的数组进行顺序搜索。我假设您的 n 在这里足够大，您已经确定(或平衡二叉树)不会为您提供足够的性能。

一个恰当的例子:我们有一些代码可以搜索问题摘要，寻找留下评论的人的名字(这样我们就可以确定我们团队中最后一个回复的成员)。我们的团队中只有大约 10 名左右的成员，所以我们只对他们使用顺序搜索 - 使用更快的数据结构来提高性能被认为太麻烦了。

---

^a无意冒犯。我只记得很久以前关于克林顿授权空运元音到波斯尼亚的幽默文章。我敢肯定还有其他国家也有类似的“问题”。