問題
問4
次の記述中の【 】に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。
- 関数 add は，引数で指定された正の整数 value を大域の整数型の配列 hashArray に格納する。格納できた場合は true を返し，格納できなかった場合は false を返す。ここで，整数 value を hashArray のどの要素に格納すべきかを，関数 calcHash1 及び calcHash2 を利用して決める。
- 手続 test は，関数 add を呼び出して，hashArray に正の整数を格納する。手続 test の処理が終了した直後の hashArray の内容は，【 】である。
- ア：{-1, 3, -1, 18, 11}
- イ：{-1, 11, -1, 3, -1}
- ウ：{-1, 11, -1, 18, -1}
- エ：{-1, 18, -1, 3, 11}
- オ：{-1, 18, 11, 3, -1}
[出典：基本情報技術者試験 令和5年度(科目B) 問4]
スポンサーリンク
正解
正解は「エ」です。
解説
この問題は、オープンアドレス法を使ったハッシュ法による格納処理の理解を問うものです。問題では配列 hashArray に対して、関数 add() を用いて整数を格納する過程を追い、その最終的な配列状態を選ぶ必要があります。
初期状態：hashArray = {-1, -1, -1, -1, -1}
- add(3)：
calcHash1(3) = (3 mod 5) + 1 = 4
→ hashArray[4] = -1
→ 空き → 3 を格納 → 配列は {-1, -1, -1, 3, -1} - add(18)：
calcHash1(18) = (18 mod 5) + 1 = (3) + 1 = 4
→ hashArray[4] = 3（使用済）
→ calcHash2(18) = ((18 + 3) mod 5) + 1 = (21 mod 5) + 1 = 1 + 1 = 2
→ hashArray[2] = -1
→ 18 を格納 → 配列は {-1, 18, -1, 3, -1} - add(11)：
calcHash1(11) = (11 mod 5) + 1 = (1) + 1 = 2
→ hashArray[2] = 18（使用済）
→ calcHash2(11) = ((11 + 3) mod 5) + 1 = (14 mod 5) + 1 = 4 + 1 = 5
→ hashArray[5] = -1
→ 11 を格納 → 配列は {-1, 18, -1, 3, 11}
このように、ハッシュ値に衝突が発生した場合は、第二ハッシュ関数によって代替位置を決定し格納されます。すべての格納処理が成功した最終的な配列は「{-1, 18, -1, 3, 11}」で、選択肢「エ」が正解となります。
ア({-1, 3, -1, 18, 11}):
3が最初に格納された位置4に対し、18が同じ位置をcalcHash1で指定するため衝突します。これを回避するため、18は位置2に格納されるべきです。
イ({-1, 11, -1, 3, -1}):
11が位置2に格納されていますが、18が既にその位置に格納されるため、この配列状態は成立しません。
ウ({-1, 11, -1, 18, -1}):
18が位置4、11が位置2になっていますが、3の格納が抜けており不正確です。
オ({-1, 18, 11, 3, -1}):
11が位置3に格納されていますが、実際にはcalcHash1で2、calcHash2で5に格納されるため誤りです。
難易度
この問題は、ハッシュ法とオープンアドレス方式を用いた探索と格納処理の理解が求められます。ハッシュ値の計算方法と衝突時の代替位置処理を正確に把握しておく必要があり、初学者にはやや複雑に感じられる内容です。よって、難易度は「やや難しい」といえます。
スポンサーリンク
用語補足
ハッシュ法：
データを格納する位置を、データに対して関数を使って計算する方法です。検索や挿入が高速で行えるのが特徴です。
オープンアドレス法：
ハッシュの衝突が発生した場合に、配列内の別の空き場所にデータを格納する方法です。代表的な再ハッシュ戦略の一つです。
mod（剰余演算）：
割り算の余りを求める演算です。例えば、18 mod 5 は 3 です。ハッシュ値の計算に使われます。
対策
ハッシュ法の問題では、mod演算や配列のインデックス操作、衝突時の処理（再ハッシュ）が理解できているかが重要です。まずは手順を紙に書いて追ってみることで、値の移動や挿入の過程を視覚化するのが有効です。アルゴリズムの動作を模擬して追体験する学習が効果的です。
