平成21年度春期 プロジェクトマネージャ 午前Ⅰ 問3

ハッシュ表の衝突条件を読む視点

ハッシュ表の条件を読むときは、キーそのものだけでなく、表への対応付けと比較対象の関係に注目し、用語の定義を問題文の記述に沿って丁寧に整理しましょう。まず判定対象を一つに定めて考えることが大切です。

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

今回確認する観点は、二つのキーが同じ扱いになる条件を、キーの値・対応付け・格納位置のどの関係として説明しているか、という一点です。各語の役割を区別して読み取りましょう。

視点

衝突を考える際は、入力となるキー、キーから導かれる対応先、表内で実際に比較される対象を混同しないように整理します。説明がどの関係を述べているかを確認し、記号や用語の意味を問題文の定義に合わせて読み進めてください。

確認ポイント

• キーについて説明されている対象を確認する
• 対応付けに関する記述と結果の記述を分けて読む
• 同じ語が問題文中でどの意味で使われているか照合する

正解

イ

解説

ハッシュ法では、キーを表の大きさ n で割った余りが格納位置を決める。a と b の余りが一致する条件を、二つのキーの差が n で割り切れる関係として整理すると、衝突条件を判断できる。

ハッシュ値の意味

ハッシュ関数 h(x)=x mod n は、キーを n で割った余りを表の位置として用いる。したがって衝突とは、a と b の余りが等しく、同じ位置に対応付けられることです。

条件の整理

剰余が等しい条件は a mod n=b mod n であり、これは a−b が n で割り切れることと同値です。よって条件は「a−bがnの倍数」となる。

選択肢ア

これは不正解だよ。a＋bがnの倍数という条件は、aとbの和がnで割り切れることを示すだけで、二つのキーをnで割った余りが一致する条件ではない。衝突では和ではなく、二つのキーの差とnの関係を確認する。

選択肢イ（正解）

これは正解だよ。衝突は h(a)=h(b)、つまり a mod n=b mod n となることをいう。二つの整数の余りが等しいとき、その差 a−b は nで割り切れるので、条件は「a−bがnの倍数」と表せる。

選択肢ウ

これは不正解だよ。nがa＋bの倍数とは、表の大きさnがキーの和で割り切れる関係を意味する。しかしハッシュ表では各キーをnで割った余りを比較するため、nと和のこの向きの関係だけでは余りの一致、すなわち衝突は保証されない。

選択肢エ

これは不正解だよ。nがa−bの倍数は、差a−bがnの約数になるという意味であり、衝突条件の向きが逆である。衝突では差がnで割り切れる必要があるため、nが差の倍数であることだけでは一般に同じハッシュ値にならない。

学習のポイント

剰余の一致と整数の割り切れ方の同値関係を理解する。