正解 イ 次の問題へ

問2 自然数をキーとするデータを、ハッシュ表を用いて管理する。キー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 の倍数

解説

余りを求める関数による、ハッシュの衝突の問題です。

「自然数をキーとするデータをハッシュ表を用いて管理する」とはどのようなものでしょうか。

自然数をキーとするデータ

 自然数をキーとするデータとは、以下の様な物だと思ってください。
キーとデータの組み合わせで、JavaScriptの連想配列やJavaのHashMapにデータを
キー データ
1 りんご
7 プリン
10 ドーナツ
3 チョコレート

ハッシュ表を用いて管理

 例えば問題文の、ハッシュ表の大きさ n が7だとしたら以下の様なハッシュ表が出来上がります。
ハッシュ値 データ
0 プリン
1 りんご
2
3 チョコレート
ドーナツ
4
5
6
データが少なくて申し訳ありませんが、ハッシュ表の3番にチョコレートとドーナツが入っています。この状態が問題文の「キーaとキーbが衝突する」に相当します。

さてさて、それでは本題の「キーaとキーbが衝突する条件」について考えてみましょう。
上の例では、チョコレートのキー「3」とドーナツのキー「10」がキーaとキーbに当たります。
ハッシュ表の大きさnは「7」ですね。
これで各選択肢に数字を当てはめてみると以下のようになります。
ア 3 + 10 が 7 の倍数 ・・・ 13 は 7 の倍数ではないので不正解
イ 3 - 10 が 7 の倍数 ・・・ -7 は 7 の倍数なので正解
ウ 7 が 3 + 10 の倍数 ・・・ 7 は 13 の倍数ではないので不正解
エ 7 が 3 - 10 の倍数 ・・・ 7 は -7 の倍数なので正解

イとエの式が成立したので、もう少し検証してみましょう。次はキーaを「3」、キーbを「17」としてみます。
イ 3 - 17 が 7 の倍数 ・・・ -14 は 7 の倍数なので正解
エ 7 が 3 - 17 の倍数 ・・・ 7 は -14 の倍数ではないので不正解

というわけで、正解はイです。