テクノロジ系
秋期
応用情報技術者 2024年 秋期 問6
6 / 80
自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ 関数 h(x)を h(x)=xmod n とすると、任意のキーaとbが衝突する条件はどれか。ここで、nはハッシュ表の大 きさであり、xmodnはxをnで割った余りを表す。
正解と解説
表示する
正解 イ
aーbがnの倍数
h(x)=x mod n で a と b が衝突するのは a mod n と b mod n が等しいとき、すなわち a−b が n で割り切れる（nの倍数になる）ときです。よってイが正解です。和や n が倍数という条件では衝突の必要十分条件になりません。