自然数をキーとするデータをハッシュ表を用いて管理する。 キー x のハッシュ値を
求めるハッシュ関数を h（x） = x mod n とした場合、キー a と b のハッシュ値が
常に衝突する条件はどれか。ここで n はハッシュ表の大きさであり、
x mod n は x を n で割った余りを示す。
① a ＋ b が 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ということ。
つまり、②の場合になる。
EXCEL ＶＢＡのご相談なら ファーストマクロ へ
タグ：ハッシュ
