ハッシュ法によるデータの格納と衝突【基本情報技術者試験 科目B 公開問題】

← 科目Bの公開問題一覧へ戻る

　基本情報技術者試験の科目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)

解答群

ア　{－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}

【参考】	「流れ図と擬似言語によるプログラミングの基礎まとめ」 「アルゴリズムと計算量の基礎まとめ（ハッシュ法とは）」

この問題のポイント

　この問題から学べることは，

• ハッシュ法によってデータの格納位置を求める方法
• ハッシュ値が衝突した場合の処理
• 複数のハッシュ関数を使って格納位置を求める方法
• 配列の要素番号とハッシュ値の関係
• プログラムをトレースして，配列の内容の変化を追跡する方法

です。特に，複数のデータを格納するときは，同じ位置が計算される「衝突」が起こることがあります。その場合に，どの位置を調べ，どのように値が格納されるのかを，プログラムの流れに沿って追跡できるようにしておきましょう。

基本情報技術者試験の学習におすすめの参考書

基本情報技術者試験の合格を目指す方におすすめの参考書です。