アルゴリズム (全97問中63問目)

No.63

16進数で表される9個のデータ1A,35,3B,54,8E,A1,AF,B2,B3を順にハッシュ表に入れる。ハッシュ値をハッシュ関数 ƒ(データ)=mod(データ,8)で求めたとき,最初に衝突が起こるのはどのデータか。ここで,mod(a,b) はaをbで割った余りを表す。
  • 54
  • A1
  • B2
  • B3
  • [出題歴]
  • 基本情報技術者 H16春期 問13

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

9個のデータを10進数で表記すると、26,53,59,84,142,161,175,178,179になります。
12_1.gif/image-size:489×63
それぞれについて関数 ƒ(データ)=mod(データ,8)を用いてハッシュを求めると、2,5,3,4,6,1,7,2,3となり、データが「26」と「178」の間で最初の衝突が起こることがわかります。
12_2.gif/image-size:489×63
10進数178は、16進数状態のデータでB2だったので、これが正解となります。

【別解】
16進数の2桁目は「16×n」なので必ず8で割り切れます。これを利用して2桁目を無視すれば素早く計算できます。
12_3.gif/image-size:489×125
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop