この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)
出典検索?: "ハッシュ関数"
この項目では、ハッシュ関数について説明しています。プログラミング言語における配列については「連想配列」をご覧ください。
ハッシュ関数で名前と0から15までの整数をマッピングしている。"John Smith" と "Sandra Dee" のハッシュ値が衝突している。
ハッシュ関数 (ハッシュかんすう、英語: hash function) あるいは要約関数[1]とは、任意のデータから、別の(多くの場合は短い固定長の)値を得るための操作、または、その様な値を得るための関数のこと。ハッシュ関数から得られた値のことを要約値やハッシュ値または単にハッシュという。
ハッシュ関数は、主に検索の高速化やデータ比較処理の高速化、さらには改竄の検出に使われる。例えば、データベース内の項目を探したり、大きなファイル内で重複しているレコードや似ているレコードを検出したり、核酸の並びから類似する配列を探したりといった場合に利用できる。
ハッシュ関数は、チェックサム、チェックディジット、フィンガープリント、誤り訂正符号、暗号学的ハッシュ関数などと関係がある。それぞれ用途が異なり、異なった形で設計・最適化されている。 ハッシュ関数の入力を「キー (key)」と呼ぶ。得られるハッシュ値は、2つ以上のキーから同じ値が得られることがある。これを衝突という。多くの場合、衝突の発生は最小限に抑えるのが望ましい。そのため、ハッシュ値の出現頻度は一様になるように設計しなければならない。 ハッシュ関数は特にハッシュテーブルで使われ、与えられた検索キー(例えばキーワード)から素早くデータレコード(辞書でのキーワードの定義)を探すのに使われる。ハッシュ関数は検索キーをハッシュにマッピングする。ハッシュをインデックスとして対応するレコードの格納位置が分かる。さらにハッシュテーブルは連想配列や動的集合 一般にハッシュ関数は複数の異なるキーを同じインデックスにマッピングする可能性がある。したがって、ハッシュテーブルの各スロットは(明示的か暗黙かはともかく)単一のレコードではなくレコードの集合に対応していることが多い。このため、ハッシュテーブルの各スロットを「バケット (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]。
衝突
用途
ハッシュテーブル
キャッシュ
ブルームフィルタ
重複レコードの検出
類似レコードの探索
Size:53 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef