完全なハッシュ関数を設計するにはどうしたらいいですか？

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; 
} 

Answer 3

参照：

What is a good Hash Function?

Best hashing algorithm in terms of hash collisions and performance

What is a performant string hashing function that results in a 32 bit integer with low collision rates？

Choosing a multiplier for a (string) hash function

Very low cost hash function

What’s the best hashing algorithm to use on a stl string when using hash_map?

Answer 4

衝突が絶対に許可されていない場合は、あなたの唯一のオプションは、おそらくへの最善の方法ではありませんデータベースにすべての文字列を追跡することです行く。

私が行うことは、MD5やSHAなどの既存の一般的な強力なハッシュアルゴリズムの1つを適用することです。サンプルの周りにはすべてのサンプルがあります。例：http://www.codeproject.com/KB/security/cryptest.aspx

Answer 5

まあ、完璧なハッシュ関数はありません。

衝突を最小限に抑えるものがいくつかありますが、衝突を最小限に抑えるものはありません。

はしかし1に助言することはできません：P

EDIT：ソリューションは完璧なハッシュ関数を見つけることができません 。解決策は、衝突を認識することです。一般に、ハッシュ関数には衝突があります。明らかに、データセットと生成されるハッシュコードのサイズに依存します。

Answer 6

バランスのとれたバイナリツリーを使用します。その後、あなたはノウエフの動作は常にO（ログ）です。

私はハッシュを強く嫌っています。人々は彼らのアルゴリズムでどれくらいのリスクを冒すか分かりません。彼らはいくつかのテストデータを実行し、次にフィールドに展開します。私は、配備されたハッシュアルゴリズムがフィールドの動作をチェックするのを決して見たことはありません。

O（log n）は、O（1）の代わりにほぼ常に許容されます。

Answer 7

概要では、CとC++の両方が一覧表示されます。あなたはどちらをお探しですか？ CとC++は2つの異なる言語であり、文字列の扱いやデータ構造が大きく異なります（C++で動作するものはそれを変更しません）。

なぜ、具体的には、完全なハッシュ関数が必要ですか？文字列を関数に関連づけたいのですが、それを行うには良い方法だろうと思いますか？これはある種の宿題ですか？マップ<>をC++で使用しない理由がありますか？ （または、unordered_map <が利用可能であれば）

完全なハッシュが必要な場合は、文字列の制約は何ですか？ディスパッチしたい固定セットがありますか？セットの1つに一致しない文字列はどうですか？ランダムな文字列からのヒットを受け入れるのですか、または入力文字列の数が制限されていますか？

質問を編集してそのような情報を含めることができれば、より多くの役に立ちます。 （最初の2つのコメントに応答して）

EDIT：あなたはおそらくあなたのCおよびC++の仕事の両方のためにこれをしたいので、

OK、我々は、Cのソリューションをご覧ください。あなたはおそらくパフォーマンスを望んでいますが、テストしましたか？私たちがI/Oシステムに入ってくる文字列を処理している場合、ディスパッチ時間を矮小化する可能性があります。

任意の文字列が必要です。ランダムなデータからのすべての衝突を避ける完璧なハッシュ関数を期待するのはちょっとですから、それを考慮する必要があります。

trieとお考えですか？それは完全なハッシュ関数よりも効率的であるかもしれませんし、そうでないかもしれません.Cで実装するのはかなり簡単で、ディスパッチ文字列や衝突の可能性のあるリストをやり直す際の問題を避けます。

Answer 8

この演習の最終結果は、ネットオフの文字列指向のハッシュ関数の数を盗む

にしました。
• 一連のファクト・クラスを作成し、各ファンクションを、そのファンクションで動作する最小の完全なハッシュを探して、一連のmod演算子値を持つデータ・セットに対してテストしました。
• その工場クラスのデフォルトのコンストラクタは、文字列を返します。文字列は、使用時に正しいハッシュ関数を選択する引数の集合を表し、最小サイズのメモリを必要とする完全なハッシュを与えるためのサイズです。
• 通常の使用では、返された引数を使用してクラスをインスタンス化するだけで、クラスは目的の関数を持つ動作状態になります。
• そのコンストラクタは、衝突がないことを検証し、衝突があれば中止します。
• 完全なハッシュが見つからない場合、ソートされたバージョンの入力テーブルをバイナリ検索に分解します。

私のドメインにある配列のセットについては、これは非常にうまくいくようです。 将来可能な最適化は、入力の部分文字列に対して同じ種類のテストを行うことです。サンプルの場合、各ミュージシャンの名前の最初の文字は、それらを区別するのに十分です。次に、実際のハッシュ関数のコストを と比較する必要があります。

アイデアを寄稿したすべての人に感謝します。