令和6年度秋期応用情報技術者試験午前問6

この問題は2024(R6)秋応用情報技術者午前に出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。

本ページの問題文・選択肢は、原本の体裁を Web 表示用に正規化しています（改行・記号・数式・図表参照の調整）。設問の趣旨および正解に影響する変更は加えていません。

自然数をキーとするデータを，ハッシュ表を用いて管理する。キー 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 と b に対してハッシュ関数の戻り値が同じになる、すなわち h(a) = h(b) となる状態を指します。

本問のハッシュ関数は h(x) = x mod n であるため、衝突が起きる条件は以下の等式が成り立つことです。
a mod n = b mod n

これは、「a を n で割った余り」と「b を n で割った余り」が等しいことを意味します。
数学的に、2つの数を同じ数で割った余りが等しい場合、その2つの数の差は割った数の倍数になります。
したがって、a - b（または b - a）が n の倍数になる場合が衝突の条件となります。

各選択肢の解説

ア. a+b が n の倍数
誤りです。例えば n=10, a=7, b=3 の場合、a+b=10 で n の倍数になりますが、h(a)=7, h(b)=3 となり衝突しません。
イ. a-b が n の倍数
正解です。 差が n の倍数となる場合、それぞれの数を n で割った余りが等しくなるため、必ず衝突します。（例：n=10, a=23, b=13 のとき、h(a)=3, h(b)=3 で衝突。差は 23-13=10 で n の倍数）
ウ. n が a+b の倍数
誤りです。例えば n=10, a=3, b=2 の場合、a+b=5 であり n は a+b の倍数ですが、h(a)=3, h(b)=2 となり衝突しません。
エ. n が a-b の倍数
誤りです。例えば n=10, a=5, b=3 の場合、a-b=2 であり n は a-b の倍数ですが、h(a)=5, h(b)=3 となり衝突しません。