已知字符串的近乎完美的散列表

给定一组125,000个字符串，表大小为250,000（所以加载因子为.5），并且假定这些字符串永不改变，寻找更好散列函数的好过程是什么？已知字符串的近乎完美的散列表

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

途径试图到目前为止（哈希总是最终MOD表的大小）

（有人建议）MD5与线性探测（48）
Python的内置散列（最多每次搜索40个探头）
定制散列与二次探测（25）
多项式与原系数，具有不同质系数双重散列，搜索素数1-1000最佳一对（13）
执行前5个探针深，然后生成一个大小为256的数组，其中包含表中剩余的最大连续空闲块空间，然后使用这些模256与线性探测（11）
布谷鸟散列与三个独立的散列函数，但没有发现任何散列组合函数来避免无限循环

鉴于负载因数为0.5，散列函数的工作性能有多大的理论限制？如果没有一个非常庞大的附加查找表，它可以完美吗？

我已经读过，最小完美散列需要〜1.6位/密钥，当前最好的结果是〜2.5位/密钥。但这是最小的（表格大小=＃键）。当然在我的情况下，我们可以非常接近完美，如果不是完美的，有一个相当小的查找表？顺便提一下，在这种情况下，哈希函数的速度并不重要。

来源

2014-07-11 Henry

除了有趣的理论问题：如果快速查找是目标，不会像一个特里值得调查吗？您正在花费一些内存来处理.5的加载因子，所以特里结构的开销不应该阻止。 – laune

@laune：空间开销可能并不重要，但查找时间开销（多个缓存未命中，而不是1或2）可能是杀手。不知道OP的具体应用，很难说。 – tmyklebu

@tmyklebu是的，这就是我认为的 - 快速查找问题，尽管不是最糟糕的情况下（40 - OMG）的探针是衡量标准，这是平均值。但是，trie需要O（长度）的努力，而这正是字符串的典型哈希码计算所需要的。我说：让树尝试并计算所有字符串的查找时间。嘿，如果我有现实的数据，我会这样做，只是为了它的乐趣！ – laune

你有没有想过使用两个独立的散列函数？杜鹃散列的变体可以仅使用两个散列函数构建出令人惊讶的高负载因子的散列表。

未经修改的杜鹃散列（每个项目散列到其两个位置中的一个）以恒定概率获得0.5的加载因子。如果您修改它以使用大小为2的桶（因此每个项目散列到两个桶中的一个，因此四个位置中的一个，并且您逐出桶的最旧元素），我相信您可以获得大约0.8或0.9的加载因子没有不合理的漫长的最坏情况插入时间。

在你提出的问题中，有250000个可能的从字符串到表格单元格的映射。 250000 * 249999 * ... * 125001是内射（“完美散列函数”）。用斯特林近似后者的数字;考虑到这两个数字的日志的差异，你会发现随机选择的函数将是一个完美的散列，概率大约为2 ^（ - 55000）。这意味着（以惊人的高概率）存在一个55千比特表，它指定了一个完美的哈希函数，其大小仅为“55千比特”，而且也没有任何实质性的小数据。（查找这张表是另外一回事，另外请注意，这种信息论的方法假定没有任何探索是做的。）

来源

2014-07-11 19:22:45 tmyklebu

我用3个独立的散列函数编写了杜鹃散列的实现，到目前为止我还没有能够调整它们以避免无限循环引用。选择'新的散列函数'（如维基百科所提到的）是困难的部分。对此表示欢迎。 – Henry

当你得到一个循环时，你可以选择新的散列函数。查找“散列函数的通用族”。如果你不喜欢挑选新的散列函数，使用两倍大小的水桶的一半，并且*真的*很高的可能性，它将起作用。 – tmyklebu

好的通用家族的散列函数绝对是我需要阅读的，谢谢你的提示，我会看到这让我感兴趣。 – Henry

已知字符串的近乎完美的散列表

回答

相关问题