本文へスキップ

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


Since 2016.4.19

平成28年度 技術士第二次試験問題【必須科目】

T−12

自然数をキーとするデータをハッシュ表を用いて管理する。 ハッシュ関数を h(x) = x mod n としたとき、キー a と b が常に衝突する条件は次のうちどれか。ここで n はハッシュ表の大きさであり、x mod n は x を n で割った余りを示す。

@ a + b が n の倍数

A b − a が n の倍数

B a ÷ b が n の倍数

C n が a + b の倍数

D n が b − a の倍数


類題

H27 T-12


正解

A


解説

ハッシュ関数は、ある入力値から唯一に決まる固定値を生成する関数のことである。
固定値から入力値を求めることはできない。

例えば
 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 ということ。
つまり、Aの場合になる。

T−11 目次 T−13