ハッシュ法(hashing)は、メモリ上でデータを高速に検索するための手法である。各種のツリー構造とは異なり、静的な配列だけで簡単に実装でき、効率も極めて高い。このため、非常に実用的な手法として重宝である。 配列上でデータを検索する手法には、ハッシュの他いくつかある。以下、単純な手法から順に説明していき、ハッシュ法の説明に至ることにしよう。 ある小さな会社の社員情報をメモリ上で処理する場合を考えてみよう。社員情報のキーとして社員番号(整数)を用いることだけを決めておき、その他については考えないことにする。 (1)単純配列 データの出現順に配列につめていく。もっとも単純かつ基本的な方法。 データの挿入は高速だが、検索は端から順に見ていく(リニアサーチという)しかないため、平均するとデータ件数(社員数)の半分について処理が必要となる。 この手法は遅いので、データ件数が多い場合には使われない・・