试图散列字符串统一的哈希表？

Question

我目前在学期末附近的数据结构课程中，并且已经分配了一个项目，我们正在实施链接哈希表来存储和检索密钥。我们已经被赋予了相当大的自由度，我们将如何设计我们的哈希表实现，但是对于奖励要点，我们被告知要尝试找到一个散列函数，它将我们的密钥（唯一字符串）一致且随机地桌子。

我已经选择了使用ELF散，看到这里http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

我的问题是：有了这个哈希函数返回一个整数，但我无法看到这是如何用于帮助指定将我的密钥放入散列表中。我可以简单地这样做：index = ELFhash（String key）％tableSize，但是这是否会破坏首先使用ELF哈希的目的？

此外，我选择了我的冲突解决策略为双重哈希。有没有一种很好的方法来确定一个合适的二次哈希函数来查找跳转？我的哈希表不会是一个常量大小（字符串集将被添加并从我哈希的数据集中删除，我将在每次添加和删除迭代之后重新哈希它们以使负载因子为.75 ），所以我很难做出像k％n这样的事情，其中​​n是一个与我的表格大小相对的数字。

感谢您花时间阅读我的问题，并让我知道您的想法！

Answer 1

你想想“包装偏见”是正确的，但对于大多数实际目的来说，这不会是一个问题。

如果散列表的大小为N，并且散列值在[0..M）的范围内，则让k = floor(M/N)。在[0..k*N)范围内的任何散列值都是“好”的，因为使用mod N作为映射，每个散列桶映射的确实是k散列值。 [k*N..M)中的散列值是“坏”的，因为如果使用它们，则相应的M-K*n最低散列桶将从一个附加散列值映射。即使哈希函数是完美的，这些桶具有更高的接收给定值的概率。

但问题是“多高？这取决于M和N.如果哈希值是unsigned int,[0..2^32)，并且 - 读过Knuth和其他人 - 你决定选择大约一千个桶的素数，比如说1009，会发生什么？

floor(2^32/1009) = 4256657 

的“坏”值数为

2^32 - 4256657 * 1009 = 383 

因此，所有的桶从4256657“好”值映射，以及383获得一个额外的不利的“坏”的价值4256658.因此， “偏见”为1/4,256,657。

这是非常不可能的，你会发现一个散列函数，其中桶之间的概率差异是百分之四十是明显的。

现在，如果您重新计算数百万个桶而不是一千个，那么情况会有所不同。在这种情况下，如果你有点OC，你可能想切换到64位散列。

另外还有一件事：精灵哈希不太可能给出绝对可怕的结果，而且速度相当快，但是哈希函数有更好的表现。一个相当受人重视的人，你可能想尝试一下是Murmur 32。（这篇Wiki文章提到原始alg有一些弱点可以用于DoS攻击，但是对于你的应用程序来说它没问题。）我确定你的教授不希望你复制代码，但Wikipedia页面有它完成。自己实施Elf并尝试对付Murmur来看看他们的比较会很有趣。