制作完美的哈希（所有连续的存储桶已满）、gperf 还是替代方案？

Question

假设我想构建一个完美的哈希表来查找预定义键为 12 个月的数组，因此我想要

hash("January")==0
hash("December")==11

我通过 gperf 运行我的月份名称并得到了一个很好的哈希函数，但它似乎给出了 16 个存储桶（或者更确切地说，范围是 16）！

#define MIN_HASH_VALUE 3
#define MAX_HASH_VALUE 18
/* maximum key range = 16, duplicates = 0 */

查看生成的 gperf 代码，它的哈希函数代码执行了从 256 大小的表中查找 len 加 char 值的简单返回。不知何故，我在脑海中想象了一个看起来很奇特的功能......:)

如果我正好想要 12 个存储桶（即我不想跳过未使用的存储桶）怎么办？对于这样的小集合，这确实不重要，但是当我有 1000 个预定义键并且想要连续 1000 个桶时怎么办？

人们能找到一种确定性的方法来做到这一点吗？

Answer 1

我对这个问题的答案很感兴趣，并通过搜索

gperf

找到了它。我尝试了 gperf，但它在大型输入文件上非常慢，因此似乎不合适。我尝试过 cmph 但我对此不满意。它需要构建一个文件，然后在运行时加载到 C 程序中。此外，该程序非常脆弱（任何类型的错误输入都会因“分段错误”而崩溃），以至于我不信任它。进一步的谷歌搜索引导我到此页面，然后继续到mph。我下载了mph，发现它非常好。它有一个可选程序来生成 C 文件，称为“emitc”，并像使用它一样

 mph < systemdictionaryfile | emitc > output.c

几乎立即就可以工作（几秒钟内就有大约 200,000 个单词的字典）并创建了一个可以正常编译的工作 C 文件。我的测试也表明它有效。不过，我还没有测试哈希算法的性能。

Answer 2

我知道的 gperf 的唯一替代方案是 cmph ：http://cmph.sourceforge.net/ 但是，正如 Jerome 在评论中所说，拥有 16 个存储桶可以为您带来一些速度优势。

当我第一次查看最小完美哈希时，我在 CiteseerX 上发现了非常有趣的读物，但我抵制住了尝试自己编写其中一个解决方案的诱惑。我知道我最终会得到一个相对于 gperf 或 cmph 而言较差的解决方案，或者即使假设该解决方案具有可比性，我也将不得不花费大量时间。

Answer 3

有很多 MPH 解决方案和算法，gperf 还没有做 MPH，但我正在研究它。特别是。对于大集合。请参阅https://gitlab.com/rurban/gperf/-/tree/hashfuncs

经典的 cmph 有很多恒定的开销，仅推荐用于巨大的密钥集。修复版本：https://github.com/rurban/cmph

有 NetBSD nbperf 和我的改进变体：https://github.com/rurban/nbperf 它支持 CHM、CHM3 和 BZD，具有整数密钥支持、针对较小密钥集的优化和备用哈希函数。

有 Bob Jenkin 的 发电机，以及 Taj Khattra 的 mph-1.2。

还有两个用于生成 C 查找的 perl 库，一个在 PostgresQL 中 (PerfectHash.pm)，一个用于后期 perl5 unicode 查找 (regen/mph.pl)，以及一个用于比较各种生成器的工具：https://github。 com/rurban/Perfect-Hash