ハッシュ法

データが存在するかは、ハッシュ値を求めて該当位置にデータが登録されているかで判定できる。 ハッシュ値は、ハッシュ関数で求められる。 ハッシュ法は、辞書データに対して高速に検索できる特徴があり、実用的で高速な検索手法としてよく使用される。 ハッシュ法で注意する点は、異なるデータのハッシュ値が一致する（衝突と言われる）可能性である。 衝突が発生した場合の対処にはいくつかの手法があり、対象のデータにも依存するため、状況に応じて採用される。 ハッシュ関数は、算出が容易でハッシュ値の衝突が起きにくい関数が好ましい。 ハッシュ関数には決定的なものはないが、文字列に用いられるハッシュ関数の例としては、文字を数値と見なして各文字に係数をかけて加算していくものがある。