平成23年度秋期 ITサービスマネージャ 午前Ⅰ 問3

ハッシュ表の衝突条件を考える視点

ハッシュ表の設問では、キーと格納位置の関係を整理し、どの条件が同じ位置への割り当てにつながるかという観点に絞って、前提・用語・対象範囲の対応を落ち着いて確認します。

この問題で問われていること

判断するときは、対象となるキー、位置を決める仕組み、表の状態や前提が互いにどう関係するかを一つずつ照合し、表面的な語句や印象だけで結論を出さないことに集中します。

視点

衝突を検討する際は、入力となる対象と結果として参照される場所を区別し、設問内で置かれた前提がどの関係を述べているのかを丁寧に対応づけます。

確認ポイント

• 対象となるキーの範囲を確認する
• 格納位置に関する前提を整理する
• 用語同士の関係を照合する

正解

イ

解説

ハッシュ値が等しいとは、aとbをnで割った余りが等しいことです。このときaとbの差はnを単位とする倍数になります。したがって衝突条件は「a−bがnの倍数」です。

理由

衝突はh(a)=h(b)、つまりa mod n=b mod nとなる場合です。二つの数をnで割った余りが同じなら、その差a−bはnで割り切れます。よってa−bはnの倍数です。

比較

「nがa−bの倍数」は、nをa−bで割り切れるという別の向きを表します。必要なのは、nが差a−bを割り切ること、すなわち差a−bがnの倍数になることです。

選択肢ア

これは不正解だよ。a+bがnの倍数であることは、二つのキーの和と表の大きさの関係を示す条件です。衝突で必要なのは、aとbをnで割った余りが一致することなので、和ではなく二つのキーの差に注目します。

選択肢イ（正解）

これは正解だよ。衝突ではa mod nとb mod nが等しくなります。余りが等しい二つの整数の差はnで割り切れるため、a−bはnの倍数です。この条件が、二つのキーが同じハッシュ位置になることを表しています。

選択肢ウ

これは不正解だよ。nがa+bの倍数という条件は、表の大きさnとキーの和との関係を示しています。しかし、同じハッシュ値になるかどうかはキーの和ではなく、nで割った余りの一致、すなわちキーの差との関係で決まります。

選択肢エ

これは不正解だよ。「nがa−bの倍数」は、nが差a−bで割り切れるという意味です。衝突に必要なのは、nが差a−bを割り切ること、つまり差a−bがnの倍数になることなので、倍数と割り切る向きが逆です。

学習のポイント

剰余の一致を、差が表サイズの倍数になる条件へ変換する考え方を身に付けます。