問７
自然数をキーとするデータを、ハッシュ表を用いて管理する。キー 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 の倍数ということ。
つまり、イの場合になる。
タグ：ハッシュ表
