自然数をキーとするデータをハッシュ表を用いて管理する。 キーx のハッシュ値を求めるハッシュ関数を ｈ(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 ということ。
つまり、②の場合になる。
| Ⅰ－１１ | 目次 | Ⅰ－１３ |