ハッシュ関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ハッシュ関数 (hash function) とは、あるデータが与えられた場合にそのデータを代表する数値を得る操作、又は、その様な数値を得るための関数のこと。ハッシュ関数から得られた数値のことをハッシュ値または単にハッシュという。

またプログラミング言語のPerlにおいては、連想配列のことをハッシュと呼ぶ。

[編集] 用途

ハッシュの用途は、「高速な検索」及び「データの検証」である。以下後者の例を説明する。

例えば、「ある文書が正確かどうか検証したいが、その文書そのものを記録・比較したくない」場合を考える。ここでもしこの文書を代表する数値（文書の要約）を数学的に作り出すことができれば、この要約だけを記録し、比較すれば良いことになる。このような要約を作る操作がハッシュになる。

より具体的に、今、ハッシュ関数として、「5字ごとに1字を選択し、その列を並べたものをハッシュ値とする」という操作を選択したとすると、このハッシュ関数によって、元の文書を1/5に短縮することができる。しかしこの方法では、

うまく間に適当な文字を入れて、別の文書を作ることが出来る。
推測から元の文書も復元できてしまう事もある。
短い定型的文章では、異なる文書から同じ要約が出来てしまうこともあり得る（衝突、コリジョン）。
1万字の文章では、要約だけで2000文字になる

という問題がある。そこで、このようなことが確率論的に現実には起こりにくくなるようなハッシュ関数を工夫をする必要がある。

通常は元データのバイナリ表現を使い、それを複雑に操作し数十～数百ビットのハッシュ値を作る。

[編集] ハッシュ関数

ハッシュ関数とは、もとのデータからある一定範囲の数値を生成する関数である。理想的には、異なったデータからは常に異なったハッシュ値が得られることが望ましいが（完全ハッシュ関数）、多くの場合それは困難である。実用上のハッシュ関数は、次のような要件を満たす必要がある。

似たデータから近しいハッシュ値が生成されない
あるデータとハッシュ値が等しい別のデータ（ハッシュ値の衝突(collision)）が容易に生成できない
ハッシュ値に値域上の偏りがない

このため、次のような性質が求められる。

数値の各ビットが、元のデータのできるだけ多くの部分から影響を受ける
元のデータからの影響の受け方が、各ビット毎に全く異なる

ハッシュ関数は次のような技術に用いられる。

ハッシュ関数の例（文字列sから12bit幅[[0..2047]]の数値を得るハッシュ関数、C言語で記述）。

unsigned int hash(char *s) {
    unsigned int h;
    h = 0;
    for (;*s != '\0'; s++) {
        h = h * 137 + *s;
    }
    return h % 1987;
}

ハッシュ関数では、上記の例のように剰余演算によって、数値をある一定範囲に制限することがよく行われる（例では1987の剰余を取ることで1987未満であることを保障している）。また、ハッシュ値が値域内でできるだけ均等に分かれるようにするためには、この剰余を求める数（h = p mod qのq）として素数を選択することが良いことが知られている。なお、hの更新計算で用いる137という数は、 $27 + 2 3 + 2 0$ というものであり、乗法した後にも2進数表現の下位の桁にも情報が残るようになっている。そのため前の方の文字の情報が桁あふれによって失われることはない。

また、文字列の集合を元に、その集合の要素を入力とした場合においての完全ハッシュ関数を求めるソフトウェアとして、GNU gperfがある。