FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の手続 hashPlaceScore() を実行したときの…
問題
次の手続 hashPlaceScore() を実行したときの戻り値はどれか。
○整数型: hashPlaceScore()
整数型の配列: key ← {8, 15, 3, 10}
整数型の配列: table[1..7] ← すべて空
整数型: i, p
for (i を 1 から keyの要素数 まで 1ずつ増やす)
p ← ((2 × key[i] ＋ 1) mod 7) ＋ 1
while (table[p] が空でない)
p ← p ＋ 1
if (p ＞ 7)
p ← 1
endif
endwhile
table[p] ← key[i]
endfor
return table[5] ＋ table[2]- ア 18
- イ 25（正解）
- ウ 30
- エ 33
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：25
初期位置は ((2×key+1) mod 7)+1 です。8は4、15も4なので5、3は1、10も1なので2に入ります。したがって table[5]=15、table[2]=10 で、戻り値は25です。
18はtable[5]ではなく8を使った場合、30は15を2回足した場合に出やすい値です。33は衝突後の位置ではなく初期位置だけで考えた誤りです。
ハッシュ関数が少し複雑でも、まず初期位置を計算し、その後に線形探索で実際の格納位置を決めます。初期位置と格納位置を分けて表にしましょう。
この衝突処理の正体：空きが出るまで p を1ずつ進め、7を超えたら1へ戻すこの方式は、オープンアドレス法のうち「線形探索法（リニアプロービング）」です。本問では8と15、3と10がそれぞれ同じ初期位置で衝突し、後者が隣の空きへずれています。隣接マスが連鎖して埋まる「一次クラスタリング」が起きやすく、探索が遅くなる点が弱点です。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。