Sin*_*int 3 c gnu hashtable lookup-tables
假设我想构建一个完美的哈希表,用于查找预定义键为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 plus char查找的简单返回.不知何故,在我脑海中,我想象一个看上去很奇怪的功能...... :)
如果我想要12个桶(那是我不想跳过未使用的桶)怎么办？对于这样的小型设备,它确实没关系,但是当我有1000个预定义的键并且连续需要1000个桶时？
可以找到确定性的方法吗？
小智 6
我对这个问题的答案很感兴趣,并通过搜索找到了它gperf.我试过gperf,但是在一个大的输入文件上它很慢,因此看起来不合适.我试过cmph,但我对它并不满意.它需要构建一个文件,然后在运行时将其加载到C程序中.此外,该程序是如此脆弱(在任何类型的错误输入上与"分段错误"崩溃),我不相信它.进一步的谷歌搜索引导我到这个页面,然后继续前进到英里.我下载了mph,发现它非常好.它有一个可选的程序来生成一个名为"emitc"的C文件,并使用它
mph < systemdictionaryfile | emitc > output.c
几乎立即工作(几秒钟,一个大约200,000字的字典)并创建了一个工作的C文件,编译没有任何问题.我的测试也表明它有效.但我还没有测试过散列算法的性能.