本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成23年度 秋期 高度情報技術者試験問題と解説

問3

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


正解


解説

ハッシュ関数は、ある入力値から唯一に決まる固定値を生成する関数のことである。
例えば
 x = 100, n = 13 のとき、ハッシュ値は 9
 x = 101, n = 13 のとき、ハッシュ値は 10
 x = 113, n = 13 のとき、ハッシュ値は 9
となり、101, 113のハッシュ値は衝突する。

他にも n = 13 のとき、ハッシュ値が 9 になるのは、
9, 22, 35, 48, 61, 74, 87, 100, 113, 126, ・・・
共通するのは、差が 13 の倍数ということ。
つまり、イの場合になる。

問2 目次 問4