给定一组125,000个字符串，表大小为250,000个（因此负载因子.5），并且考虑到这些字符串永不更改，那么寻找更好的哈希函数的好方法是什么？
字符串长度为1到59个字符，包含72个唯一字符（典型的ascii值），平均长度和中位长度为7个字符。
到目前为止已经尝试过的方法（哈希总是最终修改表的大小）
假设负载因子为.5，那么散列函数的工作方式是否有理论上的限制？如果没有非常庞大的附加查询表，它会完美吗？
我已经读到最小的完美散列需要〜1.6位/密钥，而当前的最佳结果是〜2.5位/密钥。但这是最小的（表大小=＃键）。当然，在我的情况下，通过很小的查询表，我们可以非常接近完美（如果不是完美的话）？
哈希函数的速度在这种情况下并不重要。
您是否考虑过使用两个独立的哈希函数？杜鹃哈希的变体可以仅使用两个哈希函数来构建具有惊人高负载因子的哈希表。
未经修改的布谷鸟哈希（每个项目都精确哈希到其两个位置之一）以恒定的概率达到0.5的负载系数。如果您修改它以使用大小为2的存储桶（因此每个项目都散列为两个存储桶之一，因此是四个位置之一，并且逐出存储桶中最古老的元素），我相信您可以获得的负载系数约为0.8或0.9没有不合理的长时间最坏情况插入时间。
在提出的问题中，从字符串到表单元格的映射可能有250000 ^ 125000。其中250000 * 249999 * ... * 125001是单射的（“完美哈希函数”）。使用斯特林近似后一个数字；取这两个数字的对数之差，您会发现随机选择的函数将是一个理想的散列，概率约为2 ^（-55000）。这意味着（以惊人的高概率）存在一个55千位的表，该表指定了一个完美的散列函数，其大小“仅为” 55 kb，并且没有任何实质性更小的函数。（查找此表是另一回事。此外，请注意，这种信息论方法假设没有进行任何探测。）
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句