ハードコードされたハッシュテーブルの固定ハッシュ関数を判断する良い方法はありますか？

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個の異なる文字列を0からN-1までのN個の異なる整数にマッピングする既知のアルゴリズムはありますか？

このような感じがします。

Answer 1

これらは、minimal perfect hash functionsとして知られており、それらを見つけるための確かに既知のアルゴリズムがあります。私はアルゴリズムを個人的には知っていませんが、それは問題ありません。既存のライブラリはあなたのためにそれを行うことができます。

CMPHは、非常に多数のキーに対して最小完全ハッシュ関数を見つけるのに適しています。

gperfは、完全なハッシュ関数を最小限に抑える必要がない（したがってテーブルに空きがあるかもしれない）少数のキーに対するハッシュ評価速度に焦点を当てています。