基本情報 2022 サンプル問題 問7：テクノロジ系に関する問題

答えは b「2」 です。

ハッシュ法は 「数字を計算して、その答えを“しまう場所”にする」 という収納術。

計算ルールは「各桁を全部足して、13で割った余り」。

54321 でやってみると:

1. 各桁を足す: 5 + 4 + 3 + 2 + 1 = 15

2. 15を13で割る: 15 ÷ 13 = 1 余り 2 → 答えは 2

だから配列の 位置2 に格納します。

👉 覚え方: 「ハッシュ=計算でしまう場所を決める」。データを探すときも同じ計算をすれば一発で見つかる(=超速で検索できる)のが強み。

割り算の余りを使う方法(mod)は、しまう場所を「13個の引き出し」のどれかに振り分ける役割。

なぜこれが正解か

正解は b「2」。問題のハッシュ関数は `mod(a₁ + a₂ + a₃ + a₄ + a₅, 13)`。

54321 の各桁: a₁=5, a₂=4, a₃=3, a₄=2, a₅=1

• 合計: 5 + 4 + 3 + 2 + 1 = 15
• 15 ÷ 13 = 商1 余り 2

ゆえに配列位置 2 に格納される。

各選択肢の解説

• a「1」: 15 ÷ 13 の商を答えとしている。ハッシュ値は余りなので誤り。
• c「7」: 計算ミスの可能性(例: 各桁の積を取った 5×4×3×2×1 = 120, mod 13 = 3 等も該当せず)。
• d「11」: 計算経路が異なる。例えば桁数を含めた別計算等の混同。

覚え方・ひっかけ注意

ハッシュ関数の基本形は 「何らかの計算 → mod(配列サイズ)」 で、結果は必ず [0, サイズ−1] の範囲。本問は配列サイズ13なので結果は0〜12。

衝突(コリジョン)に注意: 別の数 12345 でも各桁の合計は15、ハッシュ値2で同じ位置になる。実際のハッシュ表ではこの衝突をチェイン法(同じ位置に連結リスト)やオープンアドレス法(空くまで隣を探す)で解決する。本問では衝突は問われていないが、ハッシュ法の必須知識として押さえる。

ハッシュ法の理論

ハッシュ法はキー集合 K を配列インデックス集合 [0, m-1] へ写像する手法。理想的なハッシュ関数は 均等性(uniformity) を持ち、各バケットにほぼ均等にキーが分布する。平均探索時間は O(1+α)(αは負荷率 n/m)、最悪は O(n)(全衝突時)。

ハッシュ関数の設計原則

1. 除算法(division method): h(k) = k mod m。本問のスタイル。m は 2^x や 10^x を避け、素数を選ぶ のが定石(13が素数なのはこの設計通り)。これは、m が合成数だとキーの分布に偏りがあった場合、その偏りが直接ハッシュ値に伝播するため。

2. 乗算法(multiplication method): h(k) = ⌊m × (k×A mod 1)⌋。A=(√5-1)/2(黄金比の逆数)が経験的に良い分散を生む(Knuth推奨)。

3. 暗号学的ハッシュ: SHA-256, BLAKE3 等。ハッシュ表用には過剰だが、データ整合性検証で必須。

衝突解決法

• チェイン法(separate chaining): 各バケットに連結リスト。実装容易、削除しやすい。Java HashMap, C++ unordered_map で採用。
• オープンアドレス法: 線形探索/二次探索/ダブルハッシュ。メモリ局所性が良く高速だが削除が複雑(tombstone必要)。Pythonの dict, Rustの HashMap で採用。
• Robin Hood hashing: 探査距離を平準化する変種。最近の高性能実装で採用増加。
• Cuckoo hashing: 2つのハッシュ関数で2箇所候補、空くまで「追い出し」連鎖。O(1)最悪保証。

試験での位置づけ

データ構造の頻出単元。基本情報技術者試験では本問のような基本計算 + 衝突回数計算が定番。応用情報以降ではブルームフィルタ、コンシステントハッシュ法(分散システム)、HyperLogLog(基数推定)、Count-Min Sketch(頻度推定)など確率的データ構造へ展開。

選択肢の発展補足

• 桁数和ハッシュの弱点: アナグラム(54321 と 12345, 13524 等)が全て同じハッシュ値になり衝突多発。本問でもこの設計は教育用で、実用ではない。
• 負荷率(load factor) α = n/m: αが0.7を超えると性能が劣化する経験則。Javaの HashMap はα=0.75で自動リサイズ。
• DoS攻撃: 既知のハッシュ関数に対して衝突を狙ったキーを大量送信し、O(n)に劣化させる Hash flooding 攻撃。対策として SipHash など seed をランダム化したハッシュが標準化された(PHP 7+, Python 3.4+)。
• 完全ハッシュ法(perfect hashing): キー集合が静的なら衝突0のハッシュ関数を構築可能。コンパイラのキーワード認識、辞書アプリで活用。