2020年02月17日

令和元年度秋期 応用情報技術者試験問題 問7

問7

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

タグ:ハッシュ表
posted by ファーストマクロ at 19:23| Comment(0) | R01秋応用情報技術者
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント: