基本情報 平成25年度 秋期 問7｜テクノロジ系に関する問題

答えは d「A[9]」 です。

10個の場所（A[0]〜A[9]）に数字を入れていきます。ルールは「割り算の余りの場所に空きがあれば入れる、無ければ別の場所を試す」。

• 16 → 16÷10=余り6 → A[6] 空き → A[6] に格納
• 43 → 余り3 → A[3] 空き → A[3] に格納
• 73 → 余り3 → A[3] 埋まってる → 次の規則で別の場所へ
• 24 → 余り4 → A[4] 空き → A[4]
• 85 → 余り5 → A[5] 空き、と思いきや…

計算の結果、最後の85は A[9] に入ります（規則(3)が適用された結果）。

👉 覚え方：「ハッシュ法＝余りで場所を決め、空いてなければ次を試す（オープンアドレス法）」。

なぜこれが正解か

正解は d A[9]。本問はハッシュ法（オープンアドレス法）の典型問題で、規則を順次適用：

• (1) A[x mod 10] が空なら格納
• (2) ダメなら A[(x+1) mod 10] が空なら格納
• (3) それもダメなら A[(x+4) mod 10] が空なら格納

順次追跡：

• x=16：16 mod 10=6 → A[6]空き → A[6]=16
• x=43：43 mod 10=3 → A[3]空き → A[3]=43
• x=73：73 mod 10=3 → A[3]埋まり → (3+1) mod 10=4 → A[4]空き → A[4]=73
• x=24：24 mod 10=4 → A[4]埋まり → (4+1) mod 10=5 → A[5]空き → A[5]=24
• x=85：85 mod 10=5 → A[5]埋まり → (5+1) mod 10=6 → A[6]埋まり → (5+4) mod 10=9 → A[9]空き → A[9]=85

各選択肢の解説

• a A[3]：43の場所、85は規則(3)まで進む。
• b A[5]：24の場所、85はさらに次へ。
• c A[6]：16の場所、85は最終的にA[9]へ。
• d A[9]：規則(3)で +4 シフトの結果。

覚え方・ひっかけ注意

ハッシュ法は「衝突発生時のリハッシュ規則」が肝。本問は規則が(1)→(2)→(3)で段階的適用される設計。衝突解決方式には他に連鎖法（チェイン法）もある。値を表に書きながら順次トレースすれば確実に解ける。

理論的背景

ハッシュ法は、ハッシュ関数 h(key) で格納位置を直接計算する直接参照型データ構造で、平均O(1) の検索・挿入・削除を実現。本問は オープンアドレス法（open addressing） で、衝突時に別の位置を順次試行する方式。試行関数の取り方で：

• 線形探査法（linear probing）：h(k), h(k)+1, h(k)+2, ... と連続位置を試行（本問の規則(1)(2)）
• 二次探査法（quadratic probing）：h(k), h(k)+1², h(k)+2², ... と平方刻みで試行
• ダブルハッシュ法：別のハッシュ関数で間隔を決定

本問の規則(3)は +4 シフトで、線形と非線形の混合パターン。代替手法として 連鎖法（separate chaining） は衝突値を連結リストで保持。

実務での使われ方

ハッシュテーブルは現代の標準データ構造で、JavaのHashMap、PythonのDict、C++のunordered_map、JavaScriptのObjectなど。ハッシュ関数の質（一様分布性）が性能を左右し、MurmurHash、xxHash、SipHash等が実用ハッシュ関数。暗号学的用途ではSHA-256、SHA-3が使われる。ロードファクタ（使用率 = 要素数/配列サイズ）が0.7を超えると衝突急増のため、動的拡張（resize、rehash）で性能維持。

試験での位置づけ

FE・APアルゴリズム分野で頻出。ハッシュ関数、衝突解決法、オープンアドレス vs 連鎖法の比較、平均/最悪計算量、ロードファクタ、再ハッシュ条件が定番。応用情報・データベーススペシャリストではB木・B+木との比較、データベースインデックス（ハッシュインデックスvs B木インデックス）、分散ハッシュテーブル（DHT、コンセンサスハッシュ）まで踏み込む。

関連事項・発展補足

本問のような表形式の格納問題はトレース能力を直接測る出題で、規則の優先順位と現在の表状態の管理が解答の鍵。実務ではキャッシュ機構（Redis、Memcached）、データベースインデックス、ブルームフィルタ（確率的データ構造）でハッシュが基幹技術として使われる。セキュリティ分野では、パスワード保存にbcrypt/scrypt/Argon2等の遅いハッシュを用いることでブルートフォース耐性を確保。ハッシュ衝突攻撃（DoS用に大量の衝突を引き起こすキーを送信）対策として、ランダム化ハッシュ（SipHash）が標準化された。本問の数値追跡技能は実務でのデバッグ思考力と直結し、状態遷移を慎重に追う訓練として有用。