ハッシュ法とは？

ハッシュ法とは、キーからハッシュ関数で「格納する場所（インデックス）」を計算し、配列に直接置く方法です。探すときも同じ計算をすれば一発でたどり着くため、挿入も探索も平均 O(1) という速さになります。

ただし、たくさんのキーを少ないインデックスに割り当てるので、別々のキーが同じ位置になることが起きます。これを衝突（コリジョン）、同じ値になったキー同士をシノニム（synonym）と呼び、原理的に避けられません。

図：別のキーが同じインデックスに来る「衝突（シノニム）」を、連結リストでつなぐのがチェイン法

衝突の解決には、同じ場所に来たキーを連結リストでつなぐチェイン法と、空いている別のマスを探すオープンアドレス法があります。キーが偏ると鎖が長くなり、最悪 O(n) まで落ちるので、よく散らばるハッシュ関数が重要です。

基本情報技術者試験では、平均計算量 O(1)、衝突・シノニム、チェイン法とオープンアドレス法の違いが定番です。