応用情報技術者 予想問題｜練習問題 第10問

解説

チェイン法（連鎖法）は、ハッシュ値が衝突した複数の要素を、同じバケットに連結リストなどでつないで格納する方式である。表の外にリストを伸ばせるため、要素数がバケット数を超えても動作し、削除処理も比較的容易という特徴がある。衝突したら次の空きバケットを線形に探索するのはオープンアドレス法（線形探査法）の説明で、こちらは表内の別の位置に格納するため、データが連続して固まるクラスタリングが発生しやすい。別のハッシュ表に再度ハッシュをかける、ハッシュ関数を動的に変更するという記述は、チェイン法の定義とは異なる。「チェイン＝鎖＝同じ場所にリストでつなぐ」「オープンアドレス＝空いている別の住所を探す」と対比して覚えると混同しない。