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