ハッシュ関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動先: 案内、 検索
ファイル:Hash table 4 1 1 0 0 1 0 LL.svg
ハッシュ関数で名前と0から15までの整数をマッピングしている。"John Smith" と "Sandra Dee" のハッシュ値が衝突している点に注意。

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

ハッシュ関数は主に検索の高速化やデータ比較処理の高速化、さらには改竄の検出に使われる。例えば、データベース内の項目を探したり、大きなファイル内で重複しているレコードや似ているレコードを検出したり、核酸の並びから類似する配列を探したりといった場合に利用できる。

ハッシュ関数の入力を「キー (key)」と呼ぶ。ハッシュ関数は2つ以上のキーに同じハッシュ値をマッピングすることがある。多くの場合、このような衝突の発生は最小限に抑えるのが望ましい。したがって、ハッシュ関数はキーとハッシュ値をマッピングする際に可能な限り一様になるようにしなければならない。用途によっては、他の特性も要求されることがある。ハッシュ関数の考え方は1950年代に遡るが[1]、ハッシュ関数の設計の改善は今でも盛んに研究されている。

ハッシュ関数は、チェックサム、チェックディジット、フィンガープリント、誤り訂正符号、暗号学的ハッシュ関数などと関係がある。これらの概念は一部はオーバーラップしているが、それぞれ用途が異なり、異なった形で設計・最適化されている。

またプログラミング言語の一部（Perl、Ruby等、主に高等言語とされる一般的なプログラミング言語の多く）においては、連想配列のことを伝統的にハッシュと呼ぶが、これは連想配列そのもののプログラムの内部的実装に拠るものであり、ハッシュ関数そのものとは全く異なる。連想配列はハッシュ関数の応用例の一つのハッシュテーブルの実用例である。

用途

ハッシュテーブル

ハッシュ関数は特にハッシュテーブルで使われ、与えられた検索キー（例えばキーワード）から素早くデータレコード（辞書でのキーワードの定義）を探すのに使われる。ハッシュ関数は検索キーをハッシュにマッピングする。ハッシュをインデックスとして対応するレコードの格納位置が分かる。さらにハッシュテーブルは連想配列や動的集合の実装に使われる。

一般にハッシュ関数は複数の異なるキーを同じインデックスにマッピングする可能性がある。したがって、ハッシュテーブルの各スロットは（明示的か暗黙かはともかく）単一のレコードではなくレコードの集合に対応していることが多い。このため、ハッシュテーブルの各スロットを「バケット (bucket)」、ハッシュ値を「バケットインデックス」とも呼ぶ。

したがって、ハッシュ関数はレコードの位置のヒントでしかない。つまり、探すための出発点を教えるだけである。それでも、半分以上埋まったテーブルで良いハッシュ関数を使えば、検索対象をせいぜい1つか2つのエントリに減らすことができる。

キャッシュ

ハッシュ関数は、低速な記憶媒体に格納された巨大なデータセットのためのキャッシュを構築するのに使うことがある。ハッシュテーブルと似ているが、キャッシュであるため、衝突が発生しても古い方のアイテムを消去するか本来の媒体に書き戻せばよいという特徴がある。

ブルームフィルタ

ハッシュ関数はブルームフィルタの基本的構成要素である。ブルームフィルタはキーが集合に含まれるかどうかを近似的に表すコンパクトなデータ構造である。

重複レコードの検出

巨大なソートされていないファイルから重複したレコードを探す場合、各レコードをハッシュ関数に入力して配列 T のインデックスを得て、各バケット T[i] にハッシュ値が i になった全レコードの番号をリストの形で集める。この配列が完成すると、重複したレコードは必ず同じバケットに存在しているはずである。そこで、リストの要素数が2つ以上のバケット全てについて実際のレコードを求めて比較することで、重複レコードを探すことができる。配列が適切な大きさであれば、この方法が他のどんな方法（ファイルをソートし、隣り合うレコードを比較していく方法など）よりも高速な場合が多い。

類似レコードの探索

ハッシュ関数は、キーが似ているが全く同一ではない場合のレコード検索にも使える。この場合の入力は1つのキーか、似たようなキーを持つ巨大ファイル内の2つのレコードである。このためには、似たようなキーを与えられたとき、最大でも m しか違わないハッシュ値（m は小さい整数で例えば1か2）を生成するハッシュ関数を必要とする。このようなハッシュ関数を使って全レコードに関するハッシュテーブル T を構築すると、似たようなレコードは同じバケットか近いバケットに格納されることになる。すると各バケット T[i] について、-m から m の範囲の k で表されるバケット T[i+k] に格納されているレコード群を相互に比較すればよい。

この応用として音響指紋アルゴリズムと呼ばれる技法がある。これを使うと音声ファイルの巨大なコレクションから似たようなエントリを探すことができる（MusicBrainzの楽曲ラベリングサービスで使われている）。この場合のハッシュ関数は、ノイズやタイミングの違いや音量の違いといった差異をなるべく無視できるようなものであることが望ましい[2]。

類似部分文字列の探索

同じ技法は巨大な文字列の集まりから同じ部分か類似する部分を見つけ出すのに応用できる。例えば、文書リポジトリや遺伝子データベースなどに応用できる。この場合、入力文字列群を多数の小さな部分に分割し、それらに対してハッシュ関数を適用して上述してきたような技法で同じ部分や類似の部分を探す。

ラビン-カープ文字列検索アルゴリズムは比較的高速な文字列検索アルゴリズムで、平均でO(n)の時間で動作する。このアルゴリズムは文字列の比較にハッシュ関数を使っている。

幾何学的ハッシュ

この原理は、コンピュータグラフィックスや計算幾何学を代表とする様々な分野で、2次元平面や3次元空間でのいわゆる類似性問題を解くのに使われている。例えば、多数の点から最も近い2つの点を探すとか、一連の形状から類似した形状を探すとか、画像データベースから類似する画像を探すなどの用途である。これらの用途では、あらゆる入力は何らかの距離空間にあり、ハッシュ関数はその空間を格子状に分割するものと解釈できる。このときに使用するテーブルは2次元以上の配列であり（グリッドファイルなどと呼ぶ）、ハッシュ関数はその次元数に対応した一連のインデックスを返す。このようなハッシュ技法を幾何学的ハッシュなどと呼ぶ。幾何学的ハッシュは電気通信でのベクトル量子化でも使われており、多次元の信号を符号化し圧縮するために使われている。

改竄の検出

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

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

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

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

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

改竄の検出を行う場合は、単純なハッシュ関数アルゴリズムを用いると、容易に同じハッシュ値を求めることができるため、安全に設計されたハッシュ関数を用いる必要がある。

特性

本来の意味での良いハッシュ関数は、一般に以下のような特性を満たす必要がある。なお、関連する概念（暗号学的ハッシュ関数、チェックサムなど）では要求は異なる。

低コスト

他の手法に比べてハッシュ関数を用いた手法をより有利にするには、ハッシュ関数の計算コストが十分小さくなければならない。例えば、n個の要素のあるソート済みテーブルにある要素を挿入する場合、二分探索では log2 n 回のキーの比較を必要とする。したがって、ハッシュテーブルを使った手法が二分探索よりも効率的であるためには、ハッシュ関数が1つのキーからハッシュ値を計算するコストが log2 n 回のキー比較のコストよりも小さくなければならない。暗号学的ハッシュ関数は、そういう意味では時間がかかりすぎるテンプレート:要出典。

決定性

ハッシュを使った手法は決定的でなければならない。つまり、ある入力が与えられたとき、生成するハッシュ値は常に同じでなければならない。言い換えれば、数学的な意味で関数になっていなければならない。したがってハッシュ関数は、時刻などに基づいた擬似乱数のような外部パラメータに依存してはならない。また、ハッシュ対象オブジェクトのメモリアドレスが処理中に変化する可能性があるなら（ガベージコレクションが行われるシステムでは変化する可能性がある）、それもパラメータとして利用することはできないが、時にはアドレス変更と同時にハッシュのやり直しを行うこともある。

一様性

良いハッシュ関数は、考えられる入力範囲が出力範囲全体になるべく一様に分布するようにマッピングを行う。つまり、出力範囲のそれぞれのハッシュ値はほぼ同じ確率で生成されるべきである。このような条件があるのは、異なる入力が同じハッシュ値にマッピングされてしまう「衝突」が発生すると、ハッシュに基づく各種技法のコストは衝突発生回数と共に増大するためである。あるハッシュ値が他のハッシュ値より生成されやすいなら、参照操作で衝突しているエントリ間でどれが探しているエントリかを調べる作業が基本的に大きな部分を占めることになる。

注意しなければならないのは、「一様分布」が必要なのであって「無作為」である必要はないという点である。よい無作為化関数はハッシュ関数にも適していることが多いが、ハッシュ関数が無作為化関数である必要はない。

ハッシュテーブルには可能な入力のうちのごく一部が格納されているということが多い。例えば、ある会の会員名簿には100人ほどの会員の名前が並んでいるが、それはこの世に存在する人名のごく一部である。その場合、一様性はほぼ全ての典型的な部分集合に対して成り立てばよいのであって、全ての可能なエントリ全体の集合に対して成り立たせる必要はない。

言い換えれば、典型的な m 個のレコードの集合を n 個のバケットにマッピングする場合、1つのバケットに対応するレコード数が m/n より大きくなる可能性をなるべく小さくすればよい。特に m が n より小さい場合、一部のバケットだけが1つまたはせいぜい2つのレコードを格納するようにすべきである。理想的な完全ハッシュ関数では、各バケットには最大でも1つのレコードしか格納されない。しかし、n が m よりずっと大きくても、衝突を完全に無くすことはできない（誕生日のパラドックスを参照）。

ハッシュ関数を評価する場合、ハッシュ値の分布の一様性はカイ二乗検定で評価できる[3]。

可変な値域

多くの用途では、プログラムを実行するたびにハッシュ値の範囲は変化するし、場合によっては1回の実行中にも範囲が変化することもある（ハッシュテーブルを拡張する必要が生じた場合など）。そのような場合、ハッシュ関数は2つのパラメータを入力する必要がある。1つは入力データ z で、もう1つは生成可能なハッシュ値の数 n である。

よくある方式は、非常に大きな値域（例えば 0 から 232−1）のハッシュ関数を用意し、その出力を n で割った余りを最終的な出力とする。n が2のべき乗なら、割り算ではなくビットマスクやビットシフトで代替できる。この方式を採用するなら、ハッシュ関数は n がいくつであっても、0 から n−1 の間でハッシュ値が一様に分布するようなものを選択する必要がある。関数によっては、奇数や素数など特定の n でないと余りが一様分布にならないこともある。

データ正規化

用途によっては、入力データに比較目的には不適切な特徴が含まれていることがある。例えば、英語の個人名を参照するとき、大文字と小文字を区別しない方がよい。そのようなデータをハッシュ関数の入力にする場合、データの同値関係基準を考慮すべきであり、同じと見なされる入力には同じハッシュ値を生成すべきである。

連続性

（等しいデータではなく）類似するデータを探索する用途では、ハッシュ関数は可能な限り連続となっているべきである。少しだけ異なる入力に対しては、同じハッシュ値かごく近いハッシュ値を生成すべきである。

なお、連続性はチェックサムや暗号学的ハッシュ関数などにとっては不適切な特性である。ハッシュ関数に連続性が必要となる用途は、線型探索を使うハッシュテーブルなどの用途である。

ハッシュ関数のアルゴリズム

ハッシュ関数の選択は、その用途における入力データの性質や確率分布に大きく左右される。

簡単なハッシュ関数

ハッシュ対象のデータが十分に小さいなら、入力データそのものをハッシュ値として使うこともできる（何らかのバイナリを整数として再解釈する）。このような自明なハッシュ関数（恒等関数）の計算コストは事実上ゼロである。

「十分に小さい」の意味は、ハッシュテーブルに割り当てられるメモリ量に依存する。2008年現在、典型的なPCでは1GB程度のメモリが利用可能で、30ビット程度のハッシュ値なら扱える。ただし、多くの場合そこまで大きなハッシュテーブルは必要としない。例えば、英文の文字列の大文字/小文字の変換をするとき、各文字をバイナリ符号化したものを使い、その文字符号を整数のインデックスとしてテーブルを参照すると対応する変換後の文字符号が得られるようにするという方法が考えられる（例えば、'A' には 'a'、'8' には '8' を返すなど）。それぞれの文字が8ビットで表されていれば（ASCIIまたはISO Latin 1）、テーブルのエントリ数は 28 = 256 個だけとなるし、Unicodeの場合でも 17×216 = 1114112 エントリである。

同じ技法は 'us' とか 'ja' のような2文字国名コードを実際の国名にマッピングする場合（262=676 エントリ）、アメリカの5桁の郵便番号を地名にマッピングする場合（10万エントリ）などに利用できる。不正なデータ値（例えば国名コードなら 'xx'、ZIPコードなら 00000）に対応するエントリは未定義とされたり、何らかの 'null' 値にマッピングすることになるだろう。

完全ハッシュ関数

ファイル:Hash table 4 1 1 0 0 0 0 LL.svg
4つの人名についての完全ハッシュ関数

ハッシュ関数が単射の場合、すなわち正しい入力に対して必ず異なるハッシュ値が対応する場合、これを完全 (perfect) だという。このような関数を使えば、1つのハッシュテーブルで目的のエントリを直接探すことができ、それ以外の探索の手間が生じない。

完全ハッシュ関数は、入力される範囲が予め分かっていて変化しない場合のみ成立する。例えば英語の月の名前を0から11の整数にマッピングするとか、ある辞書に掲載されている単語にハッシュ値を割り当てるといった場合である。入力の集合を与えられると、それに対応した完全ハッシュ関数を実行する最適化されたサブルーチンを出力する生成器がいくつか存在する（例えば、GNU gperf）。

最小完全ハッシュ関数

ファイル:Hash table 4 1 0 0 0 0 0 LL.svg
4つの人名についての最小完全ハッシュ関数

n 個のキーに対する完全ハッシュ関数が最小 (minimal) であるとは、その値域が n 個の連続な整数（通常 0 から n-1）の場合である。単に参照が単純化されるだけでなく、ハッシュテーブルもコンパクトになり、空きスロットができない。最小完全ハッシュ関数は単なる完全ハッシュ関数よりも求めるのが難しい。

一様に分布するデータのハッシュ技法

入力が制限された長さの文字列（例えば、電話番号、自動車のナンバー、送り状番号など）で、個々の入力値は独立にかつ一様な確率で発生する場合、ハッシュ関数は個々のハッシュ値にだいたい同じ個数の入力値をマッピングすればよい。例えば、入力 z が 0 から N−1 の範囲の整数、出力 h が 0 から n−1 の範囲の整数で、N が n より大きいとする。するとハッシュ関数としては、h = z mod n （ z を n で割った余り）、h = (z × n) ÷ N （z を n/N 倍して整数に丸めた値）、などの式が考えられる。

その他の分布のデータのハッシュ技法

入力の出現確率が一様でない場合や、独立性がない場合は、上のような単純な方式ではうまくいかない。例えば、あるスーパーマーケットの利用者は地理的に近い場所に集中しているため、電話番号の先頭数桁は同じになってしまう。その場合、(z × n) ÷ N の式では元の数値の上の桁が残るため、衝突が多発する。一方、z mod n の式では、末尾側の桁が残るため、この場合のハッシュ値の分布はこちらの方がよい。

可変長データのハッシュ技法

データが非常に長い（または可変長の）文字列の場合（人名、URL、電子メールの中身など）、その分布は一様でないことが多く、複雑な依存関係が存在することが多い。例えば、自然言語の文章では文字の分布は全く一様ではないし、文字の並び方にも相関関係があり、その言語に特有の性質を持っている。その場合、ハッシュ関数は文字列内の全文字を何らかの形で使用し、しかもそれぞれの文字を異なった形で使用するのが望ましい。

そのようなデータをハッシュ値に変換する典型的手法は、入力を小さな単位（数ビット、数バイト、数ワードなど）の並び b[1], b[2], …, b[m] に分割し、それを順に以下のように結合していく。 

S ← S0;                             // 状態を初期化
for k in 1, 2, …, m do              // 入力データ単位をスキャン:
  S ← F(S, b[k]);                   //   データ単位 k を状態に結合する。
return G(S, n)                      // 状態からハッシュ値を抽出する。

この手法は、テキストのチェックサムやフィンガープリントのアルゴリズムにも利用されている。状態変数 S は32ビットか64ビットの符号無し整数である。例の場合、S0 は 0 でよいし、G(S,n) は単に S mod n でよい。最適な F の選択は難しい問題で、データの性質にも依存する。データ単位 b[k] が1ビットなら、F(S,b) は例えば次のようになる。 

 if highbit(S) = 0 then
   return 2 * S + b
 else
   return (2 * S + b) ^ P

ここで highbit(S) は S の最上位ビットを意味し、'*' 演算子は符号無しの整数の乗算でオーバーフローを無視する操作を表す。'^' はビット単位の排他的論理和演算を表し、P は適当な固定のワードである[4]。

特定用途のハッシュ関数

多くの場合ヒューリスティクスを利用して、汎用のハッシュ関数よりも特定用途で衝突を削減できるハッシュ関数を設計できる。例えば、入力が FILE0000.CHK、FILE0001.CHK、FILE0002.CHK などのファイル名で、多くの場合このような一連の番号が名前に含まれているとする。すると、ファイル名から番号部分 k を抜き出し、k mod n をハッシュ値とすれば、ほぼ最適な結果が得られる。言うまでもないが、特定の入力に最適化したハッシュ関数は、それ以外の分布を示す入力に対しては非常に悪い結果を生じる。

ハッシュとしてのチェックサム関数

チェックサムやフィンガープリント用のアルゴリズムをハッシュ関数として採用することもできる。それらのアルゴリズムの一部は、任意長の文字列データ z から32ビットまたは64ビットのビット列を生成するので、そこから 0 から n-1 のハッシュ値を容易に抽出できる。

この手法は、ハッシュ値の範囲 n がチェックサムやフィンガープリント関数の値域より十分小さい場合に限って、十分一様に分布するハッシュ値を生成する。しかし、一部のチェックサムは雪崩効果が弱いため、用途によっては不向きである。よく使われているCRC32チェックサムは、上位16ビットだけがハッシュ用途に使える。さらに言えば、入力の各ビットはCRC32の1つのビットにのみ影響を与える。したがって、32ビットのチェックサムをそのままハッシュ値に利用する場合は十分な注意が必要である[5]。

暗号学的ハッシュ関数

Secure Hash Algorithmのような暗号学的ハッシュ関数は、チェックサムやフィンガープリントよりも強力な一様性を保証するので、汎用ハッシュ関数としても最適である。

しかし暗号化などの用途以外では、その計算コストが高いため利点が打ち消されてしまう[6]。しかし、悪意ある者がキーを選んでもハッシュ値が一様に分布するという特性がある。このためDoS攻撃からサービスを保護する助けとなる場合もある。

ハッシュ関数の安全性

暗号学的ハッシュ関数の安全性を議論する場合、以下の三種類について議論を行う。

原像計算困難性

原像計算困難性(Preimage Resistance)とは、与えられたどのハッシュ値に対しても、そのハッシュ値を出力するようなハッシュ関数への入力を求めることが困難であるような性質を言う。ただし、異なる入力から同じハッシュ値が得られるため、そのハッシュ値を得られる入力を一つ求めればよい。

第2原像計算困難性

第2原像計算困難性(Second Preimage Resistance)とは、与えられたどの入力値に対しても、その入力値をハッシュ関数へ入力したときのハッシュ値と同じハッシュ値を出力する入力値を求めることが困難であるような性質を言う。

衝突困難性

衝突困難性(Collision Resistance)とは、同じハッシュ値を与える二つの入力値を求めることが困難であるような性質を言うのである。

それぞれの困難性の関係

原像計算困難性を満たさないハッシュ関数では、任意の入力値からハッシュ値を得られるため、第2原像計算困難性を満たさない。また、第2原像計算困難性を満たさないハッシュ関数では、衝突困難性を満たさない。 すなわち、

原像計算困難 ⊂ 第2原像計算困難 ⊂ 衝突困難

である。

語源

"hash" という用語は、本来の「切り刻んで混ぜる」という意味からの類推で使われるようになった。実際、合同操作を行う典型的なハッシュ関数は、入力の定義域を多数の部分に「切り刻み」、キーの分布が値域で一様になるように「混ぜた」形で出力する。

ドナルド・クヌースによれば、この用語を最初に使ったのはIBMの Hans Peter Luhn で、1953年1月の社内メモで使っていた。そして、Robert Morris が学会誌 Communications of the ACM に掲載した論文でこの用語を使い、単なるジャーゴンから正式な専門用語に昇格した[1]。

脚注・出典

テンプレート:Reflist

関連項目

外部リンク

解説

実装

オンラインハッシュ生成

  • Hash Generator オンラインのハッシュ生成器 (md2,md4,md5,sha1,tiger,snefru,ripemd,whirlpool,haval...)
  • Ajax-based Hash Generator オンラインのハッシュ生成器。文字入力の度にハッシュ値を計算する。
  • hashr オンラインのハッシュ生成器。40以上のハッシュアルゴリズムを選択できる。

テンプレート:データ構造

テンプレート:Cryptography navbox
  1. ↑ 1.0 1.1 テンプレート:Cite book
  2. ↑ "Robust Audio Hashing for Content Identification" by Jaap Haitsma, Ton Kalker and Job Oostveen
  3. ↑ Bret Mulvey, Hash Functions. Accessed April 11, 2009
  4. ↑ A. Z. Broder. Some applications of Rabin's fingerprinting method. In Sequences II: Methods in Communications, Security, and Computer Science, pages 143--152. Springer-Verlag, 1993
  5. ↑ Bret Mulvey, Evaluation of CRC32 for Hash Tables, in Hash Functions. Accessed April 10, 2009.
  6. ↑ Bret Mulvey, Evaluation of SHA-1 for Hash Tables, in Hash Functions. Accessed April 10, 2009.
「http://wikippe.e-do-match.com/index.php?title=ハッシュ関数&oldid=2775」から取得