ボンカレー 〜凡人コミュ障の僕が華麗に生きていく術を考えるブログ〜

凡人コミュ障の僕が華麗に生きていく術を考えるブログ

基本情報技術者 ミスノート 20180916

過去問H16春問13

問題

16進数で表される9個のデータ1A,35,3B,54,8E,A1,AF,B2,B3を順にハッシュ表に入れる。ハッシュ値ハッシュ関数f(データ) = mod(データ, 8)で求めたとき、

最初に衝突が起こる(既に表にあるデータと等しいハッシュ値になる)のはどのデータか。

ここで、mod(a, b)はaをbで割った余りを表す。

 

解答

そのまま、十進数になおして計算をすると手間がかかりすぎる。

16進数は、?×2(7乗) + ?×2(6乗) + ?×2(5乗) + ?×2(4乗) + ?×2(3乗) + ?×2(2乗) + ?×2(1乗) + ?×2(0乗)で表される数字。

この数字を8つまり2(3乗)で割ると、2(3乗)のように指数3以上の指数の項に関しては、必ず割り切れる。

 

これは、54630という数=5×10(4乗) + 4×10(3乗) + 6×10(2乗) + 3×10(1乗) + 0×10(0乗)を、10(2乗)で割ったらその指数2以上の指数を持つ項は必ず割り切れるのと同じ理屈。

しかし、指数2未満の指数を持つ項はあまりとしてでてしまう。

 

さて、2(3乗)で割ると、3未満の指数である下位三桁の部分があまりとして出てくる。

よって、16進数の下位三桁にだけ注目すれば良い。

 

1Aの下位三桁は、Aが10進数で言う10, 2進数で言う1010なので、010が該当する。

35の下位三桁は、5が10進数で言う5, 2進数で言う0101なので、101が該当する。

3Bの下位三桁は、Bが10進数で言う11, 2進数で言う1011なので、011が該当する。

54の下位三桁は、4が10進数で言う4, 2進数で言う0100なので、100が該当する。

8Eの下位三桁は、Eが10進数で言う14, 2進数で言う1110なので、110が該当する。

A1の下位三桁は、1が10進数で言う1, 2進数で言う0001なので、001が該当する。

AFの下位三桁は、Fが10進数で言う15, 2進数で言う1111なので、111が該当する。

B2の下位三桁は、2が10進数で言う2, 2進数で言う0010なので、010が該当する。

→ここで初めてコリジョンが発生する。

B3の下位三桁は、Aが10進数で言う3, 2進数で言う0011なので、011が該当する。