平成20年 春期 ソフトウェア開発技術者 午前 問12

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

 ア  54
 イ  A1
 ウ  B2
 エ  B3


答え ウ


解説
各データのハッシュ値を求めます。
ハッシュ値はハッシュ関数f (データ)=mod(データ, 8)から、データを8で割った余りです。(8で割った余りとは、データの下3ビットの値になります。)

データ ハッシュ値
1 1A 2
2 35 5
3 3B 3
4 54 4
5 8E 6
6 A1 1
7 AF 7
8 B2 2
9 B3 3
このデータをハッシュ表に入れたとき衝突が発生するのは、1番目のデータ1Aと同じハッシュ値(2)の8番目のデータB2と、3番目のデータ3Bと同じハッシュ値(3)の9番目のデータB3で、最初に衝突が発生するのは8番目のデータB2(ウ)です。


キーワード
・ハッシュ関数

キーワードの解説

戻る 一覧へ 次へ