基本情報技術者平成16年春期 午前問13

午前問13

16進数で表される9個のデータ1A,35,3B,54,8E,A1,AF,B2,B3を順にハッシュ表に入れる。ハッシュ値をハッシュ関数f(データ)=mod(データ,8)で求めたとき,最初に衝突が起こる(既に表にあるデータと等しいハッシュ値になる)のはどのデータか。ここで,mod(a,b)はaをbで割った余りを表す。
  • [この問題の出題歴]
  • ソフトウェア開発技術者 H20春期 問12

分類

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

正解

解説

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

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

Pagetop