你会如何​​去为一个完美的设计散列函数？ [英] How would you go about designing a function for a perfect hash?

问题描述

感兴趣的领域是字符串匹配。假设我有一个这样的结构。

The domain of interest is string matching. Assume I have a structure like this.

typedef struct
{
    char *name,
    int (*function)();

} StringArray

StringArray s[] = 
{
    {"George", func1},
    {"Paul",   func2},
    {"Ringo",  func3},
    {"John",   func4},
    {"",       NULL}   /* End of list */ 
}

有数组中串的固定数目。他们很难codeD作为例子。
如果表的改变，将有必要重新评估散列函数的质量。

There are a fixed number of strings in the array. They are hard coded as in the example. If the table changes, there would be a need to re-evaluate the quality of the hash function.

欲散列函数应用到一个字符串，如果该字符串匹配一个阵列中，
然后调用函数。是需要这方面的一个完美的哈希函数。没有冲突是需要散列不允许为目的，是对查找得到O（1）性能。

I want to apply a hash function to a string, and if the string matches one in the array, then call the function. A perfect hash function is needed for this. No collisions are allowed.The purpose of requiring hashing is to get O(1) performance on the lookup.

做些什么的想法设计一个函数来做到这一点，你有吗？

What ideas do you have on designing a function to do this?

推荐答案

查看的gperf 主页。

这篇关于你会如何​​去为一个完美的设计散列函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！