c - 制作一个完美的散列(所有连续的桶都满了)，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 程序中。此外，该程序非常脆弱(在任何类型的错误输入上都会因“段错误”而崩溃)，我不信任它。进一步的谷歌搜索让我找到了 this page ，然后转到 mph .我下载了 mph，发现它非常好。它有一个可选的程序来生成一个名为“emitc”的 C 文件，并像使用它一样

 mph < systemdictionaryfile | emitc > output.c

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