已知字符串的近乎完美哈希

Question

已知字符串的近乎完美哈希

3

给定一组125,000个字符串，表大小为250,000（负载因子为0.5），并且假设这些字符串永远不会改变，那么找到更好的哈希函数的好方法是什么？

字符串长度为1-59个字符，包含72个唯一字符（典型的ASCII值），平均长度和中位数长度为7个字符。

到目前为止尝试过的方法（哈希始终最终模表大小）：

- （某人建议的）使用线性探测的md5（48） - Python内置哈希（每次搜索最多40次探测） - 自定义哈希与二次探测（25） - 用质数系数的多项式、双重哈希和优化配对的质数1-1000进行搜索（13） - 深入前5个探测，然后生成一个大小为256的数组，其中包含表中剩余的最大连续空闲块，然后使用这些mod 256进行线性探测（11） - 三个独立哈希函数的布谷鸟哈希，但没有找到任何避免无限循环的哈希函数组合

考虑到负载因子为0.5，哈希函数能够发挥的作用是否存在一些理论上的限制？如果没有非常庞大的额外查找表，它是否能够完美地工作？

我已经读到最小完美哈希需要大约1.6位/键，当前最佳结果为大约2.5位/键。但这是针对最小的（表大小=键数）情况。如果不是最小的情况下，我们肯定可以使用相对较小的查找表非常接近甚至达到完美哈希吧？

顺便说一句，哈希函数的速度在这种情况下并不重要。

- Henry

@laune：空间开销可能并不重要，但查找时间开销（需要多次缓存未命中而不是1或2次）可能是致命的。如果不知道OP的具体应用程序，很难说。 - tmyklebu

@VikramBhat 单独使用 MD5 不起作用（由于模表大小存在许多冲突）。还需要探测概念。 - Henry

@Henry 抱歉，你还需要探测，我认为线性探测会做到。 - Vikram Bhat

@VikramBhat 使用线性探测的 MD5 模数表大小结果为 48 最大探针，总探针远超过了限制，很抱歉。 - Henry

1

你试过使用gperf吗？诚然，它声称可以快速处理大约15,000个单词（在这里），这意味着它可能会非常慢（生成查找代码的时间可能很长，但这似乎不重要），并且可能无法处理125,000个单词，但值得一试... 另外，你能分享一下你的字符串集吗（可以在wetranfer.com或类似网站上分享）？ - Tony Delroy

显示剩余13条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tmyklebu · Accepted Answer

你有没有想过使用两个独立的哈希函数？变种的布谷鸟哈希可以使用仅两个哈希函数构建哈希表，其负载因子出奇地高。

未经修改的布谷鸟哈希（每个项恰好散列到它的两个位置之一）以常数概率达到0.5的负载因子。如果你将其修改为使用大小为2的桶（因此每个项散列到两个桶中的一个，即四个位置，并驱逐桶中最老的元素），我相信你可以获得约0.8或0.9的负载因子，而不会有不合理长的最坏情况插入时间。

在你所提出的问题中，有250000^125000种从字符串到表格单元的可能映射方式。其中250000*249999*...*125001是可逆的（“完美哈希函数”）。使用斯特林近似后，取这两个数字的对数差，你会发现随机选择的函数将以约2^(-55000)的概率成为完美哈希。这意味着（以惊人的高概率）存在一个55千比特的表格，指定了一个“仅”55千比特的完美哈希函数大小，也没有任何实质性更小的东西。（找到这个表格又是另一回事了。此外，请注意，这种信息理论方法假定根本没有探测。）