平成28年度 技術士第二次試験問題【必須科目】
【16】情報工学部門
T−12
自然数をキーとするデータをハッシュ表を用いて管理する。 キー x のハッシュ値を
求めるハッシュ関数を 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 の倍数



【正解】 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の場合になる。


EXCEL VBAのご相談なら ファーストマクロ 



T−11 目次 T−13
ファーストマクロ TOPページ