ハッシュ表
データの取り出しを高速にするためのデータ構造
キー値(データ値)をハッシュ関数に通して、ハッシュ値を導き出し、そのハッシュ値がデータの格納アドレス(住所)となる
キー値(データ値) → ハッシュ関数 → ハッシュ値
ハッシュ表を使用する際、ハッシュ値がかぶることで
衝突(コリジョン)
を起こしてしまうことがある。(もとから入っていたデータをホーム、衝突したデータをシグノムという。)
衝突(コリジョン)があったときは、シーケンシャル法とチェーン法がある。
シーケンシャル法 → シーケンシャルとは順次という意味を持ち、衝突が発生したときは次の空きがあるまで順次探していく方法
チェーン法 → 衝突が起こったとき、その格納アドレスのところにリストを作って、つなげる方法
私的には、シーケンシャル法をよく見るイメージがある。