問題プレビューID: 134acc6e基本情報技術者試験 午前免除試験 2020年1月26日

問 9
基本情報技術者試験 午前免除試験 2020年1月26日

16 進数で表される 9 個のデータ 1A,35,3B,54,8E,A1,AF,B2,B3 を順にハッシュ表に入れる。ハッシュ値を,データの値を 8 で割った余りを求めるハッシュ関数 f(x)=mod(x,8)f(x) = \mathrm{mod}(x, 8) で求めたとき,最初に衝突が起こるのはどのデータか。ここで,mod(a,b)\mathrm{mod}(a, b) は aa を bb で割った余りを表す。

解説

正解は「ウ」である。

各データを 10 進数に直して 8 で割った余り(ハッシュ値)を求めると,次のようになる。

  • 1A(26)→ 2
  • 35(53)→ 5
  • 3B(59)→ 3
  • 54(84)→ 4
  • 8E(142)→ 6
  • A1(161)→ 1
  • AF(175)→ 7
  • B2(178)→ 2
  • B3(179)→ 3

データを順に格納していくと,1A はハッシュ値 2 の位置に格納される。8 番目の B2 もハッシュ値が 2 となり,既に 1A が格納されている位置と衝突する。これが最初に起こる衝突である。

  • ア: 54 のハッシュ値は 4 で,それ以前に同じ値のデータはない。
  • イ: A1 のハッシュ値は 1 で,それ以前に同じ値のデータはない。
  • エ: B3 のハッシュ値は 3 で,3B と衝突するが,B2 の衝突より後である。

したがって,最初に衝突が起こるのは B2 であり,正解は「ウ」である。

関連問題

本文が同じ・似ている問題を表示しています