分野別過去問題テクノロジ系　アルゴリズム No.67

アルゴリズム(全101問中67問目)

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

出典：平成20年春期　問12

正解　ウ問題へ

分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム

解説

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桁目を無視すれば素早く計算できます。