平成20年春期試験問題 午前問12

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

  • 54
  • A1
  • B2
  • B3
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
9個のデータを10進数で表記すると、26,53,59,84,142,161,175,178,179になります。
12_1.png
それぞれについて関数 ƒ(データ)=mod(データ,8)を用いてハッシュを求めると、2,5,3,4,6,1,7,2,3となり、データが「26」と「178」の間で最初の衝突が起こることがわかります。
12_2.png
10進数178は、16進数状態のデータでB2だったので、これが正解となります。

【別解】
16進数の2桁目は「16×n」なので必ず8で割り切れます。これを利用して2桁目を無視すれば素早く計算できます。
12_3.png

この問題の出題歴


Pagetop