你会如何设计一个完美哈希的函数？

Question

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

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

} StringArray

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

数组中有固定数量的字符串.它们是硬编码的,如示例中所示.如果表发生变化,则需要重新评估散列函数的质量.

我想将哈希函数应用于字符串,如果字符串与数组中的字符串匹配,则调用该函数.这需要一个完美的哈希函数.不允许冲突.要求散列的目的是在查找上获得O(1)性能.

您在设计功能时有什么想法？

Answer 1

请参阅gperf主页.

Answer 2

您可以使用地图

std::string foo() { return "Foo"; }
std::string bar() { return "Bar"; }

int main()
{
   std::map<std::string, std::string (*)()> m;
   m["foo"] = &foo;
   m["bar"] = &bar; 
}