第2種情報処理技術者試験 1996年度 = 平成8年度・春期 午前 問50

 図に示す番号をキーとする10件のレコードを直接編成ファイルに記録することを考える。
 ハッシング(アドレス変換)の方法として、7を除数とする除算法を用いたとき、シノニムレコードは何件か。なお、除算法によるハッシングでは、
  キー値 ÷ 除数 = X余りY
としたときのYがレコードアドレスとなる。

2 4 6 8 10 12 14 16 18  20 

 ア 1  イ 2  ウ 3  エ 4  オ 5

解答

 ウ

解説

 直接編成ファイルは、レコードアドレスを指定することによって、処理対象となるレコードを指定することができます。すなわち、任意のレコードを読み書きできるファイル編成です。
 ハッシュ法は、キー値に対して何らかの変換関数を適用することによって、そのデータを格納するレコードを求める手法です。なお、変換関数のことをハッシュ関数と呼びます。

  キー値 → ハッシュ関数 → レコードアドレス

 本問のハッシュ関数は単純であり、キー値を7で割った余りをレコードアドレスとするものです。すべてのキー値のレコードアドレスを求めてみましょう。
キー値レコードアドレス
2 2
4 4
66
81
103
125
140
16 2
18 4
206

 シノニムは、同一のハッシュ値が発生し、格納すべきレコードアドレスが衝突することです。上の表から、2463件が衝突していることが分かります。


BohYoh.comトップページへ