做一个完美的散列(所有连续的桶都是满的)，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加上字符值。不知怎么的，在我的脑海里我想象了一个奇特的功能...:)

如果我只想要12个存储桶(也就是说，我不想跳过未使用的存储桶)怎么办？对于像这样的小集合，这真的无关紧要，但是当我有1000个预定义的键，并且希望在一行中恰好有1000个存储桶时？

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

Answer 1

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

当我第一次看到minimal perfect hasihing时，我在CiteseerX上发现了非常有趣的读数，但我抵制住了自己尝试编写其中一个解决方案的诱惑。我知道我最终会得到一个比gperf或cmph更差的解决方案，或者，即使假设解决方案是可比较的，我也必须在上面花费大量的时间。

Answer 2

我对这个问题的答案很感兴趣，通过搜索gperf找到了它。我尝试过gperf，但它在处理大型输入文件时速度非常慢，因此看起来并不合适。我试过cmph，但我对它不满意。它需要构建一个文件，然后在运行时将其加载到C程序中。此外，这个程序非常脆弱(任何一种错误的输入都会导致“分段故障”崩溃)，以至于我不信任它。进一步的谷歌搜索让我找到了this page，然后又找到了mph。我下载了mph，发现它非常好用。它有一个可选的程序来生成一个名为"emitc“的C文件，并像这样使用它

 mph < systemdictionaryfile | emitc > output.c

几乎可以立即工作(用大约200,000个单词的字典只需几秒钟)，并创建了一个可以正常编译的C文件，没有任何问题。我的测试也表明它是有效的。不过，我还没有测试散列算法的性能。