ハッシュ関数と衝突対策とは？
ハッシュ関数と衝突対策とは、キー（データを識別する値）から、データを格納する配列の位置（添字）を計算する関数がハッシュ関数。異なるキーが同じ格納位置に計算される「衝突」が起きた場合の対処法として、同じ位置に複数のデータを連結して保持するチェイン法（連鎖法）や、別の空いている位置を探して格納するオープンアドレス法（開番地法）がある。
はっしゅかんすうとしょうとつたいさく
ハッシュ関数と衝突対策の意味
キー（データを識別する値）から、データを格納する配列の位置（添字）を計算する関数がハッシュ関数。異なるキーが同じ格納位置に計算される「衝突」が起きた場合の対処法として、同じ位置に複数のデータを連結して保持するチェイン法（連鎖法）や、別の空いている位置を探して格納するオープンアドレス法（開番地法）がある。
ハッシュ関数と衝突対策の具体例
社員番号をハッシュ関数で配列の添字に変換して格納すれば、探索時も同じ計算をするだけで直接目的のデータにアクセスでき、理論上O(1)で探索できる。
ハッシュ関数と衝突対策は試験でどう引っ掛けられる？
衝突とは異なるキーが同じ格納位置に写ることで、同じキーが重複することではない。チェイン法は同じ位置に連結して保持、オープンアドレス法は表内の別の空き位置を探す。探索は理想時O(1)だが衝突多発でO(n)に劣化する。
ハッシュ関数と衝突対策と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。