.NET & Control > ハッシュ関数（Hash）

Top > .NET & Control > ハッシュ関数（Hash）

ハッシュ関数（Hash）

文字列やオブジェクトをユニークな数値に変換する

ハッシュ関数とは、データのユニークな整数値で表現する方法です。例えば、文字列データを検索する際、文字列で比較しながら検索すると非常に負荷がかかり処理が遅くなってしまいます。そこで、文字列を数値化することにより、検索、比較、改竄などの処理を高速化するために古くから用いられている手法です。

ハッシュ関数から得られた数値のことを「ハッシュ値」または単に「ハッシュ」とよびます。ハッシュ値の元になる値（文字列など）を「キー (key)」と呼びます。なお、ハッシュ値の完全にユニーク化は不可能です。異なるキー値で同一のハッシュ値になる可能性があります。

これは「衝突」と呼ばれ、最小限に抑えるアルゴリズムが望ましいとされています。末尾に、Stringクラスのアルゴリズムをご紹介します。なお、「同一キーは同一ハッシュ値を返す」が大前提です。

.NETでは、ObjectクラスにGetHashCode()メソッドがありますが、実際のハッシュ値は、それぞれのクラスでoverrideされています。従って、ハッシュ値はクラスによって考え方が異なっています。int32は、thisを返しますので、100の場合ハッシュ値は100です。

ハッシュ値を使ったプログラミング（例）

プログラム中に大量の文字列があったとします。ソースコードから、文字列を抽出してユニークな文字列のリストを作成する場合、上記解説にもあるように、文字列比較を行うのは非効率ですし時間がかかってしまいます。

ハッシュ値は、StringのGetHashCode()で取得できます。List<int>を使ってテーブルを作成し、このリストからハッシュ値で検索することで高速に処理することができます。

ハッシュ値で比較する場合、同一ハッシュ値が複数あるか確認します。複数存在している場合は、直接文字列で比較するといった処理が必要です。

ハッシュ値を使用する際、衝突があることを前提としたプログラムを記述することがポイントです。

●Stringクラスのハッシュ関数のアルゴリズム

　static unsafe int GetHashCode(String text)
　{
　　char[] chars = text.ToCharArray();

　　fixed (char *str = chars)
　　{
　　　char * chPtr = str;
　　　int　　num = 0x15051505;
　　　int　　num2 = num;
　　　int *　numPtr = (int*)chPtr;

　　　for (int i = chars.Length; i > 0; i -= 4)
　　　{
　　　　num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];

　　　　if (i <= 2) { break; }

　　　　num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
　　　　numPtr += 2;
　　　}

　　　return (num + (num2 * 0x5d588b65));
　　}
　}

検証してみようと試みましたが、そもそも定数値の意味合いや演算そのものの正当性を評価する知識を持ち合わせていないため断念しました。

同じ文字列で、StringとStringBuilderを比較しましたが、結果は違っていました。

StringBuilderのコードを調べてみましたが、実装されていません。つまり、Objectクラスで実装されたInternalGetHashCode()メソッドのハッシュ値が返ります。マネージコードのためロジックは不明です。