アルゴリズムとプログラミング
ハッシュ表のサイズ m=7 とし、ハッシュ関数を h(k) = k mod 7 で定義する。キー集合 {15, 22, 8, 36, 25} を順に挿入したとき、衝突が発生する組み合わせとして正しいものはどれか。
ア.15と22はスロット2に衝突する
イ.15、22、8、36の4つすべてが同じスロット1に衝突する正解
ウ.8と36はスロット4に衝突する
エ.衝突は発生しない
解説
除算法は「mod でロッカー番号を決める」シンプルな方式。同じロッカーに別の人が来たら衝突。表サイズに素数を選ぶのは、規則的な衝突パターンを避けるための古くからの知恵です。
なぜ イ が正解か
イが正解。各キーを h(k) = k mod 7 で計算：①h(15) = 15 mod 7 = 1（15 = 7×2+1）、②h(22) = 22 mod 7 = 1（22 = 7×3+1）、③h(8) = 8 mod 7 = 1（8 = 7×1+1）、④h(36) = 36 mod 7 = 1（36 = 7×5+1）、⑤h(25) = 25 mod 7 = 4（25 = 7×3+4）。15, 22, 8, 36 がすべてスロット1に集中し、4個同時衝突する。25だけがスロット4で単独。
出典: AI生成問題（学習用）