ハッシュ法

検索対象のデータを一定の規則にしたがってハッシュ値と呼ばれる整数に変換し、ハッシュ値を比較して検索を行なう方式。

　文字列検索のように個々のデータが大きい場合、データ全体を比較しながら検索するよりも比較にかかるコストが節約でき、高速に検索できる。 ただし、検索するデータの大きさが小さければ、ハッシュ値に変換する手間が増えるためにかえって効率が悪くなることもある。

　元のデータをハッシュ値に変換する関数をハッシュ関数と呼ぶが、すべてのデータが異なるハッシュ値を持つように変換できれば、探したいデータのハッシュ値と同じハッシュ値を持つデータを探すことで、探したいデータと同じデータを見つけることが可能になる。 しかし現実にはそのようなハッシュ関数を用意することは難しいため、ハッシュ値が重複した場合(1つのハッシュ値に複数のデータがエントリーされる場合)を処理する方法を用意しておく必要がある。

　ハッシュ値の重複を処理する代表的な方法としては、重複した場合に空いているハッシュ値にデータを振り分ける「オープンアドレス法」や、同じハッシュ値を持つデータを線形リストとして保存する「直接連鎖法」などがある。