文字列を整数にマップするハッシュ

Question

文字列からintへのマッピングを行うためのハッシュ関数を探しています。

制限： 同じ文字列は同じ番号になります。 異なる文字列は異なる番号に移動します。 アプリケーションの実行中に同じ長さの文字列を取得していますが、実行時にのみ長さがわかります。

ハッシュ関数を作成する方法を教えてください。

Answer 1

ハッシュ関数は、2つの異なる値（あなたの場合の文字列）が異なるハッシュコードを生成することを決して保証しません。ただし、同じ値でも常に同じハッシュコードが返されます。

これは、情報が失われるためです。 32文字の長さの文字列を持つ場合、64バイト（1文字あたり2バイト）になります。 intハッシュコードは4バイトです。これは避けられず、衝突と呼ばれます。

注：Dictionary<Tkey,TValue>は内部的にハッシュテーブルを使用します。つまり、衝突解決戦略を実装しているからです。 MSDNのAn Extensive Examination of Data Structures Using C# 2.0を参照してください。

ここにはdictionary.csの現在の実装があります。

Answer 2

String.GetHashCode関数が必要条件を満たさないのですか？

Answer 3

異なる文字列に対して同じ整数が返されないことを保証するハッシュアルゴリズムを見つけることはできません。定義上、ハッシュアルゴリズムは衝突を有する。 32ビットの整数よりもはるかに多くの可能な文字列が世界中にあります。

Answer 4

異なる文字列は異なる番号になります。

数値よりも多くの文字列があるため、これは入力セットを制限することなく不可能です。あなたは鳩を箱に入れてn > mとすることはできません。少なくとも1箱に複数の鳩が入っていなくてはいけません。