アルゴリズム(全100問中66問目)
No.66解説へ
16進数で表される9個のデータ1A，35，3B，54，8E，A1，AF，B2，B3を順にハッシュ表に入れる。ハッシュ値をハッシュ関数 ƒ(データ)＝mod(データ，8)で求めたとき，最初に衝突が起こるのはどのデータか。ここで，mod(a，b) はaをbで割った余りを表す。
出典：平成20年春期 問12
- 54
- A1
- B2
- B3
広告
解説
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桁目を無視すれば素早く計算できます。