HOME»ソフトウェア開発技術者平成20年春期»午前問12
ソフトウェア開発技術者平成20年春期 午前問12
問12
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になります。
それぞれについて関数 ƒ(データ)＝mod(データ，8)を用いてハッシュを求めると、2，5，3，4，6，1，7，2，3となり、データが「26」と「178」の間で最初の衝突が起こることがわかります。
10進数178は、16進数状態のデータでB2だったので、これが正解となります。
【別解】
16進数の2桁目は「16×n」なので必ず8で割り切れます。これを利用して2桁目を無視すれば素早く計算できます。
【別解】
16進数の2桁目は「16×n」なので必ず8で割り切れます。これを利用して2桁目を無視すれば素早く計算できます。