自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を h(x) = x mod n とすると，任意のキー a と b が衝突する条件はどれか。ここで，n はハッシュ表の大きさであり，x mod n は x を n で割った余りを表す。

なぜ違う: 和ではなく差が条件。a＋b が n の倍数でも余りが一致するとは限らない。

なぜ違う: 倍数の向きが逆。衝突条件は a−b 側が n の倍数であること。

なぜ違う: 倍数の向きが逆。a−b が n の倍数（n が a−b を割り切るのではない）が正しい。

要点: 衝突＝h(a)=h(b)＝(a mod n = b mod n)。これは a−b が n の倍数のとき。

衝突とは h(a)=h(b)，すなわち a mod n = b mod n が成り立つこと。これは a と b を n で割った余りが等しい，つまり差 a−b が n で割り切れる（a−b が n の倍数）ことと同値である。

App Store

応用情報技術者の学習アプリ（応用情報トレ）