アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20210613 実施分 問8
自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を
h(x) = x mod n
とすると，任意のキー a と b が衝突する条件はどれか。ここで，n はハッシュ表の大きさであり，x mod n は x を n で割った余りを表す。
- ア a+b が n の倍数
- イ a−b が n の倍数
- ウ n が a+b の倍数
- エ n が a−b の倍数
出典：基本情報技術者試験 科目A免除 修了試験 20210613 実施分 問8
答えと解説を見る
正解：イ
覚える知識
ハッシュ関数によるハッシュ値計算
ハッシュ関数h(x)=x mod nで衝突が起きるのは、2つのキーの差がnの倍数のときである。
この問題で必要なこと
a mod n = b mod n となるのは、a−bがnの倍数であるとき。
ひっかけ
a+bがnの倍数としたり、nがa−bの倍数としたりと、倍数関係の向きや演算を取り違えさせる。
この知識の出題：本試験系 5 回・免除試験 11 回（公開問題での観測値）