基本情報技術者 ミスノート 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が該当する。