ハッシュ法

IT用語辞典バイナリ

ハッシュ法

読み方：ハッシュほう
【英】hashing

ハッシュ法とは、検索手法の一つで、対象データを数値化して、その数値が示す場所にデータを保持することで、データの検索を容易にすることである。

データが存在するかは、ハッシュ値を求めて該当位置にデータが登録されているかで判定できる。ハッシュ値は、ハッシュ関数で求められる。

ハッシュ法は、辞書データに対して高速に検索できる特徴があり、実用的で高速な検索手法としてよく使用される。

ハッシュ法で注意する点は、異なるデータのハッシュ値が一致する（衝突と言われる）可能性である。衝突が発生した場合の対処にはいくつかの手法があり、対象のデータにも依存するため、状況に応じて採用される。

ハッシュ関数は、算出が容易でハッシュ値の衝突が起きにくい関数が好ましい。ハッシュ関数には決定的なものはないが、文字列に用いられるハッシュ関数の例としては、文字を数値と見なして各文字に係数をかけて加算していくものがある。

情報処理のほかの用語一覧

アルゴリズム：

B木  FIFO  バックトラック法  ハッシュ法  関数  完全2分木  計算複雑度

>>アルゴリズムカテゴリの他の用語

ウィキペディア小見出し辞書

ハッシュ法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/07/22 02:07 UTC 版)

「ハッシュライフ」の記事における「ハッシュ法」の解説

四分木は明らかに他の単純なデータ構造（例えば、ビットの行列）よりも、ライフゲームの計算のために必要なデータ処理量は局所的には多いが、様々な最適化が可能である。名前が示す通り、内容が同一なノードを共有するためにハッシュテーブルが使われる。木の中の多くのサブパターンは互いに同一であることが多い。例えばあるパターンは同じ宇宙船のコピーを多く含んでいるかもしれないし、何もない領域がただ広く集まっているということすらある。これらのサブパターンのコピーについて、同じパターンであればキーとして使用するハッシュ値が同一となるようにハッシュ関数を設計し、ハッシュテーブルを利用するのである。また、コピーごとに計算する他のライフゲームの計算アルゴリズムとは違い、同じサブパターンについては一度だけ計算すれば良いようにできる（前述のように、それが表現している盤面全体について、その未来をメモ化することはできないが）。 このことは計算機資源の大幅な節約につながる。例えば、ブリーダーやスペースフィラーは二次的に生きているセルが増加する（quadratic growth）パターンだが、ハッシュライフを使うことで対数の空間と時間で計算することができる。