给定一组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位/键。但这是针对最小的(表大小=键数)情况。如果不是最小的情况下,我们肯定可以使用相对较小的查找表非常接近甚至达到完美哈希吧?
顺便说一句,哈希函数的速度在这种情况下并不重要。
字符串长度为1-59个字符,包含72个唯一字符(典型的ASCII值),平均长度和中位数长度为7个字符。
到目前为止尝试过的方法(哈希始终最终模表大小):
- (某人建议的)使用线性探测的md5(48) - Python内置哈希(每次搜索最多40次探测) - 自定义哈希与二次探测(25) - 用质数系数的多项式、双重哈希和优化配对的质数1-1000进行搜索(13) - 深入前5个探测,然后生成一个大小为256的数组,其中包含表中剩余的最大连续空闲块,然后使用这些mod 256进行线性探测(11) - 三个独立哈希函数的布谷鸟哈希,但没有找到任何避免无限循环的哈希函数组合
考虑到负载因子为0.5,哈希函数能够发挥的作用是否存在一些理论上的限制?如果没有非常庞大的额外查找表,它是否能够完美地工作?
我已经读到最小完美哈希需要大约1.6位/键,当前最佳结果为大约2.5位/键。但这是针对最小的(表大小=键数)情况。如果不是最小的情况下,我们肯定可以使用相对较小的查找表非常接近甚至达到完美哈希吧?
顺便说一句,哈希函数的速度在这种情况下并不重要。