BohYoh.com《基本情報技術者試験》2004年度＝平成16年度・春期午前問13

基本情報技術者試験

2004年度＝平成16年度・春期

午前

問13

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

ア　54

イ　A1

ウ　B2

エ　B3

解答

ウ

解説

　ハッシュ法は、データのキー値に対して何らかの変換関数を適用することによって、そのデータを格納する表における位置（配列の添字やレコード番号など）を求める手法です。なお、変換関数のことをハッシュ関数と呼びます。

　　キー値　→　ハッシュ関数　→　ハッシュ値

　本問のハッシュ関数は単純であり、キー値であるデータの各桁の合計を8で割った余りをハッシュ値とするものです。表に入れられる9個のデータと、そのハッシュ値は、以下のようになります。

データ	16進数	1A	35	3B	54	8E	A1	AF	B2	B3
データ	10進数	26	53	59	84	142	161	175	178	179
ハッシュ値		2	5	3	4	6	1	7	2	3

　ここで、8番目のデータB2のハッシュ値2が、先頭データ2番目の1Aのハッシュ値2と衝突します。また、9番目のデータB3のハッシュ値3が、3番目のデータ3Bのハッシュ値3と衝突します。
　題意により、順に格納する際に〔最初に衝突が起こる〕ものを選ばなければなりませんので、正解は選択肢ウのB2です。