科目B
令和5年度 基本情報技術者試験 科目B 公開問題 問4
次の記述中の に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。
関数 add は，引数で指定された正の整数 value を大域の整数型の配列 hashArray に格納する。格納できた場合は true を返し，格納できなかった場合は false を返す。ここで，整数 value を hashArray のどの要素に格納すべきかを，関数 calcHash1 及び calcHash2 を利用して決める。
手続 test は，関数 add を呼び出して，hashArray に正の整数を格納する。手続 test の処理が終了した直後の hashArray の内容は， である。
〔プログラム〕
大域: 整数型の配列: hashArray
○論理型: add(整数型: value)
整数型: i ← calcHash1(value)
if (hashArray[i] ＝ －1)
hashArray[i] ← value
return true
else
i ← calcHash2(value)
if (hashArray[i] ＝ －1)
hashArray[i] ← value
return true
endif
endif
return false
○整数型: calcHash1(整数型: value)
return (value mod hashArrayの要素数) ＋ 1
○整数型: calcHash2(整数型: value)
return ((value ＋ 3) mod hashArrayの要素数) ＋ 1
○test()
hashArray ← {5個の －1}
add(3)
add(18)
add(11)
答えを選ぶ
出典：令和5年度 基本情報技術者試験 科目B 公開問題 問4（問題文は IPA の公開問題。図・数式・下線などはテキストに直して掲載。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：エ
覚える知識
オープンアドレス法によるハッシュ衝突時の格納位置のトレース
ハッシュ関数で求めた格納位置が埋まっている（衝突した）とき、別の計算式で求めた位置に格納する方法です。
この問題で必要なこと
配列の要素数は 5 です。add(3) は 3 mod 5＋1 = 4 なので [4] に 3 を入れます。add(18) は 18 mod 5＋1 = 4 が埋まっているので、calcHash2 で (21 mod 5)＋1 = 2 を求め [2] に 18 を入れます。add(11) は 11 mod 5＋1 = 2 が埋まっているので、(14 mod 5)＋1 = 5 の [5] に 11 を入れます。結果は {−1, 18, −1, 3, 11} で、正解はエです。
ひっかけ
「＋1」は要素番号が 1 から始まるためのずらしで、これを忘れると格納位置が 1 つずれます。ア・イ・オは、衝突したときの処理（calcHash2 での位置の求め直し）を取り違えた場合の結果です。