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

答えは d です。

ハッシュ法でデータを配列に入れる問題。85を10で割った余りは5なので、まずA[5]を見ます。すでに埋まっていれば次のルール（@+1、@+4の余り）で別の場所を探します。順に試すと、A[5]→A[6]→A[9]の順で空きを探し、最終的にA[9]に格納されます。

👉 覚え方：ハッシュ衝突＝「ぶつかったら次の場所」を順に試す。

ほかの選択肢：a A[3]・b A[5]・c A[6] はそれぞれ16・43・73で先に埋まっているか、85には適用されない。

なぜこれが正解か

正解は d。順に格納していく：

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

よってA[9]に格納される。

各選択肢の解説

• a A[3]：43が格納済み。
• b A[5]：24が格納済み。
• c A[6]：16が格納済み。
• d A[9]：規則(3)で衝突解決の結果格納される正解。

覚え方・ひっかけ注意

オープンアドレス法の典型問題。規則(1)→(2)→(3)を順に試し、最初に空きが見つかった位置に格納する。順を機械的に追うのがコツ。1つでも順序を間違えると後の結果が全部ズレるので、表を作りながら解く。

理論的背景

ハッシュ法はキーを配列インデックスに変換するハッシュ関数 h(key) を使ってO(1)平均アクセスを実現するデータ構造。衝突（collision）が発生した際の解決法には①チェイン法（連結リストで連鎖）、②オープンアドレス法（別の場所を探す）があり、本問は後者。オープンアドレス法の探索方式には線形探査（linear probing、(h+i) mod m）、二次探査（quadratic probing、(h+i²) mod m）、二重ハッシュ（double hashing、(h1+i·h2) mod m）があり、本問は (h, h+1, h+4) と独自の探査列を使う変形。

実務での使われ方

ハッシュテーブルはPython dict、Java HashMap、C++ unordered_map、Goのmap、Rustのstd::collections::HashMapなど主要言語の連想配列の標準実装。データベースのインデックス（ハッシュインデックス）、キャッシュ（Redis、Memcached）、コンパイラのシンボルテーブル、ブロックチェーン（Merkle Tree）でも基本構造として使われる。

試験での位置づけ

基本情報のアルゴリズムとデータ構造分野で頻出。ハッシュ関数の設計（剰余法・乗算法・SHA等の暗号学的ハッシュ）、衝突解決法、ロードファクタ（充填率）と性能の関係、リハッシュ（rehashing）が出題される。応用情報・データベーススペシャリストではB-tree/B+treeとの使い分けが深掘りされる。

選択肢の発展補足

オープンアドレス法はクラスタリング（衝突要素が連鎖して塊になり性能劣化）が課題で、二次探査や二重ハッシュで緩和される。チェイン法はクラスタリングの影響が小さいが、メモリ局所性で劣る場合がある。負荷率（n/m、配列サイズに対する要素数の割合）が0.7を超えると性能が急激に劣化するため、リハッシュ（配列を2倍にして再配置）が必要。暗号学的ハッシュ関数（SHA-256等）は衝突困難性が要求され、本問のような剰余ベースの単純なハッシュとは設計目的が異なる。