令和5年度 科目B 問4

✓ これが正解エ{－1, 18, －1, 3, 11}

解説

3は4番目、18は2番目、11は5番目に入ります。

関数 add は、まず calcHash1 で格納先の要素番号を求め、そこが空き（－1）なら格納します。空いていなければ calcHash2 で別の要素番号を求め、そこが空きなら格納し、どちらも埋まっていれば false を返します。このように値から格納先を計算する方法をハッシュといいます。hashArray の要素数は 5 なので、calcHash1 は value mod 5 ＋ 1、calcHash2 は (value ＋ 3) mod 5 ＋ 1 です。mod は割り算の余りです。

add(3) では 3 mod 5 ＋ 1＝4 なので、4番目に 3 が入ります。add(18) では 18 mod 5 ＋ 1＝4 となり、4番目はすでに 3 で埋まっています。そこで calcHash2 を使い、21 mod 5 ＋ 1＝2 なので、2番目に 18 が入ります。add(11) では 11 mod 5 ＋ 1＝2 となり、2番目は 18 で埋まっています。calcHash2 は 14 mod 5 ＋ 1＝5 なので、5番目に 11 が入ります。

したがって test の終了直後は {－1, 18, －1, 3, 11} です。異なる値から同じ格納先が計算されることを衝突といい、このプログラムでは、衝突が起きたときに2つ目のハッシュ関数で別の位置を求めて対処しています。

格納の順序と、埋まっていたときに2つ目の関数へ切り替える流れを1件ずつ追えば、格納先の取り違えを防げます。

ほかの選択肢はなぜ違うのか

• ア{－1, 3, －1, 18, 11}：3 と 18 の位置が逆です。この並びは add(18) を add(3) より先に実行した場合に得られます。実際は 3 が先に 4番目を取り、後から来た 18 が衝突して calcHash2 の 2番目に回ります。
• イ{－1, 11, －1, 3, －1}：18 が格納されていません。4番目が埋まっていたときに calcHash2 を試さず false を返すと、この並びになります。プログラムは2つ目の関数で 2番目を求めるので、18 はそこに入ります。
• ウ{－1, 11, －1, 18, －1}：3 が消えて 4番目が 18 になっています。空きかどうかを確かめずに calcHash1 の位置へ上書きすると、この並びになります。add は －1 と等しいときだけ格納するので、3 は上書きされません。
• オ{－1, 18, 11, 3, －1}：11 が 3番目に入っていますが、11 の格納先は calcHash1 では 2番目、calcHash2 では 5番目で、どちらの関数からも 3番目は導けません。2番目が埋まっているので、11 は 5番目に入ります。