4

假设我想建立一个完美的哈希表来查找预定义键为 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 个桶时？

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

4

2 回答 2

6

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

 mph < systemdictionaryfile | emitc > output.c

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

于 2009-12-04T13:25:24.197 回答
4

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

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

于 2009-11-20T14:31:07.543 回答