什麼是確定硬編碼哈希表的固定哈希函數的好方法？

Question

通常我會發現自己需要一個散列表，其值在編譯時已知並且永遠不會改變。

我想知道是否有一種標準方法來生成定製算法，該算法僅用於特定的哈希表，以便它不需要在運行時構建，並確保沒有碰撞。

這種最糟糕的算法只是做一系列的if語句，但這有點毀了O（N）。

我想知道是否有一些現有算法將固定數量的唯一字符串映射到索引從0到唯一字符串的數量。

例如;我可能有一個哈希表，在建立這樣一個硬編碼表

{ 
    "one": "1", 
    "two": "2", 
    "three": "3" 
} 

一個天真的企圖是使一個函數入口對內部表，並拿出一些任意的歧視，如下面的一個。

#include <stdio.h> 
#include <string.h> 
#include <math.h> 

static const char *my_hash(const char *input) 
{ 
    const struct { 
     const char *key; 
     const char *value; 
    } h_table[] = { 
     {"three", "3"}, 
     {"one", "1"}, 
     {"two", "2"} 
    }; 

    int hash; 
    int len = strlen(input); 

    if (len != 3 && len != 5) { 
     return (char *)0; 
    }   

    hash = (int)ceil((((input[1] - 102)/4) - 1)/2.0);  

    return h_table[hash].value; 
} 

int main(int argc, char **argv) 
{ 
    puts(my_hash("one")); 
    puts(my_hash("two")); 
    puts(my_hash("three")); 

    return 0; 
} 

是否有已知的算法來生成這種算法？

摘要：是否有已知的將N個不同的字符串映射到N個不同整數從0到N-1的算法？

我覺得像這樣的東西已經存在。

Answer 1

這些被稱爲minimal perfect hash functions，確實有已知的算法來找到它們。我個人不知道算法，但沒關係。現有的圖書館可以爲你做。

CMPH適用於尋找非常大量密鑰的最小完美散列函數。

gperf專注於少量密鑰的散列評估速度，其中完美散列函數不需要最小化（因此表中可能有一些空白空間）。