問２ 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーｘのハッシュ関数 h(x) を
h(x) = x mod n
とすると、キーａとキーｂが衝突する条件はどれか。ここで、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 が７だとしたら以下の様なハッシュ表が出来上がります。
| ハッシュ値 |
データ |
| 0 |
プリン |
| 1 |
りんご |
| 2 |
|
| 3 |
チョコレート
ドーナツ |
| 4 |
|
| 5 |
|
| 6 |
|
データが少なくて申し訳ありませんが、ハッシュ表の3番にチョコレートとドーナツが入っています。この状態が問題文の「キーａとキーｂが衝突する」に相当します。
さてさて、それでは本題の「キーａとキーｂが衝突する条件」について考えてみましょう。
上の例では、チョコレートのキー「3」とドーナツのキー「10」がキーａとキーｂに当たります。
ハッシュ表の大きさｎは「7」ですね。
これで各選択肢に数字を当てはめてみると以下のようになります。
ア 3 + 10 が 7 の倍数 ・・・ 13 は 7 の倍数ではないので不正解
イ 3 - 10 が 7 の倍数 ・・・ -7 は 7 の倍数なので正解
ウ 7 が 3 + 10 の倍数 ・・・ 7 は 13 の倍数ではないので不正解
エ 7 が 3 - 10 の倍数 ・・・ 7 は -7 の倍数なので正解
イとエの式が成立したので、もう少し検証してみましょう。次はキーａを「3」、キーｂを「17」としてみます。
イ 3 - 17 が 7 の倍数 ・・・ -14 は 7 の倍数なので正解
エ 7 が 3 - 17 の倍数 ・・・ 7 は -14 の倍数ではないので不正解
というわけで、正解はイです。
最終更新：2014年02月19日 01:01
