対象試験と出題頻度
ハッシュ表（ハッシュ法）は、基本情報技術者・応用情報技術者で出題されるテーマです。
科目Aでは「ハッシュ値の計算」「衝突が起こるキーの組合せ」、科目Bでは「チェイン法によるデータ格納プログラムの読み取り」など、知識・実装の両面から問われています。
詳細をクリックして確認
基本情報技術者
応用情報技術者
★★★☆☆
ランクB（標準）覚えておくと有利
用語の定義
情報処理試験を勉強していると、「ハッシュ表って何？ハッシュ関数とはどう違うの？」と混乱しがちです。
ハッシュ表（Hash Table）とは、一言で言うと
「ハッシュ関数を使ってキーから格納位置を直接計算し、データの検索・挿入・削除を高速に行えるデータ構造」
のことです。
イメージとしては、「社員番号から直接ロッカーの番号が決まるオフィスのロッカー室」です。
普通のロッカー室では空いている場所を順番に探しますが、「社員番号を5で割った余り＝ロッカー番号」というルールがあれば、番号を聞いた瞬間に開けるべきロッカーがわかる。
この「計算一発で場所が決まる」仕組みがハッシュ表の考え方です。
📊 ハッシュ表の基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Hash Table（hash＝切り刻む、table＝表） |
| 別名 | ハッシュマップ、散列表 |
| 探索の計算量 | 平均O(1)（衝突がない理想状態） |
| 最大の課題 | 衝突（コリジョン）への対処 |
解説
線形探索法はデータを先頭から順にたどるためO(n)、2分探索法はソート済みデータを半分ずつ絞り込むためO(log n)の時間がかかります。データ件数が増えるほど探索時間も増える点が共通の弱点です。
ハッシュ法は、キーの値からハッシュ関数で格納位置（インデックス）を直接算出するため、データ件数に関係なく一定時間で目的のデータにアクセスできます。この「件数に依存しない定数時間の探索」が最大の強みです。
ハッシュ表の動作の流れ
📐 ハッシュ表へのデータ格納イメージ
キー「54321」
↓
ハッシュ関数：mod(5+4+3+2+1, 13) = mod(15, 13) = 2
↓
| 位置 | 格納データ |
|---|---|
| 0 | ─ |
| 1 | ─ |
| 2 | 54321 ← ここに格納 |
| 3 | ─ |
| … | ─ |
| 12 | ─ |
※FE R元秋 問10・FEサンプル問題 問7の出題例をもとに作成
格納時も探索時もハッシュ関数でインデックスを算出する手順は同じです。
探索時にはキーからインデックスを計算し、その位置のデータを直接参照します。
衝突（コリジョン）と解決法
異なるキーから同じインデックスが算出されることがあります。これが衝突（コリジョン）です。
ここだけは確実に押さえてください。ハッシュ表を使う以上、衝突は避けられない問題であり、その解決法が2種類あります。
▶ チェイン法（連鎖法）の仕組み（クリックで展開）
同じインデックスに複数のデータが来た場合、そのインデックスにリスト（連結リスト）を用意し、衝突したデータをリストにつなげていく方法です。
インデックス0: → [データA] → null
インデックス1: → null
インデックス2: → [データB] → [データC] → null ← 衝突！リストでつなぐ
インデックス3: → [データD] → null
テーブルのサイズを超えてデータを格納できる柔軟性がある一方、リストが長くなると探索時間がO(1)から悪化します。AP H21春 午後問2ではこのチェイン法の実装が出題されました。
▶ オープンアドレス法の仕組み（クリックで展開）
衝突が起きたら、テーブル内の別の空きスロットを探して格納する方法です。最も単純な方式は「線形探査法」で、衝突が起きたら隣のスロット（インデックス+1）を順にチェックしていきます。
インデックス2: [データB] ← すでに埋まっている
インデックス3: [データC] ← 衝突！隣の空きに格納
リストが不要なためメモリ効率は良いですが、テーブルのサイズを超えるデータは格納できません。また、衝突が連鎖して塊（クラスタ）ができると探索効率が急激に低下します。
他の探索手法との比較
| 探索手法 | 前提条件 | 平均計算量 | 特徴 |
|---|---|---|---|
| 線形探索法 | なし（未整列でも可） | O(n) | 先頭から順に比較。単純だが遅い |
| 2分探索法 | データがソート済み | O(log n) | 中央と比較して半分ずつ絞り込む |
| ハッシュ法 | ハッシュ関数とテーブル | O(1) | キーから位置を直接計算。衝突の対処が必要 |
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 ハッシュ表の核心を3行で
・ハッシュ関数でキーから格納位置を直接計算するため、データ件数に依存しないO(1)の探索が可能
・異なるキーから同じ位置が算出される「衝突」への対処法として、チェイン法とオープンアドレス法がある
・線形探索O(n)、2分探索O(log n)、ハッシュ法O(1)の計算量の対比が整理のカギ
試験ではこう出る！
ハッシュ法は、科目A・科目Bの両方で繰り返し出題されています。出題パターンは大きく3つに分かれます。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| FE R6年度 科目A 問2 |
ASCIIコードの1の位をハッシュ関数として使用し、衝突が起こるキーの組合せを選ぶ問題。 | ・2つのキーの距離がテーブルサイズの倍数なら衝突 ・文字コードの連続性を利用した計算 |
| FE R元秋 午前 問10 |
mod関数をハッシュ関数としてデータの格納位置を計算する問題。 | ・mod演算の実行ができるか ・FEサンプル問7と同一構成の流用問題 |
| FE H30春 午前 問7 |
表探索におけるハッシュ法の特徴を選ぶ問題。 | ・「キーの関数値で格納場所を決める」が正解 ・探索時間が一定であること、衝突は起こりうること |
| AP H26春 午前 問19 |
ハッシュ表の探索時間をグラフで選ぶ問題。衝突なしの前提で水平な直線を選ぶ。 | ・データ件数が増えても探索時間は一定 ・R5春AP問19にも流用 |
| FE R5年度 科目B 問4 |
擬似言語でハッシュ表探索プログラムを読み取り、出力結果を問う問題。 | ・チェイン法の連結リスト操作の理解 ・科目Bのアルゴリズム読解力 |
📝 IPA試験での出題パターン
パターン1：「ハッシュ値を計算せよ」
mod関数や文字コードを使ったハッシュ関数が与えられ、具体的なキーの格納位置を求める形式。計算自体は四則演算と余り（mod）だけなので、落ち着いて代入すれば得点できる。
パターン2：「衝突するキーの組合せを選べ」
R6年度FEのように、同じハッシュ値になるキーの組合せを判定する形式。「2つのキーの差がテーブルサイズの倍数なら衝突」と覚えておけば即答できる。
パターン3：「探索時間の特徴を選べ」
線形探索・2分探索との比較で、ハッシュ法の探索時間が「データ件数に依存しない定数時間」であることを問う形式。グラフ問題では水平な直線を選ぶ。
試験では深追い不要です。「mod演算ができる」「衝突の意味を知っている」「探索時間はO(1)」の3点を押さえれば得点できます。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. ハッシュ法を用いた探索の特徴として、最も適切なものはどれでしょうか？
- A. データをあらかじめ昇順に整列しておき、中央の値と比較して探索範囲を半分ずつ絞り込むことで、O(log n)でデータを見つける。
- B. キーの値からハッシュ関数で格納位置を直接計算するため、表に格納されているデータの件数にかかわらず、ほぼ一定時間で探索できる。
- C. データを先頭から順に1件ずつ比較していき、目的のデータが見つかるか末尾に達するまで繰り返す。
正解と解説を見る
正解：B
解説：
ハッシュ法は、キーからハッシュ関数でインデックスを直接計算して格納位置を特定するため、データ件数に依存しない定数時間O(1)での探索が可能です。
選択肢Aは2分探索法の説明です。データが整列済みであることが前提で、計算量はO(log n)です。選択肢Cは線形探索法の説明です。先頭から順にたどるため計算量はO(n)であり、データ件数が増えるほど探索時間も増加します。
よくある質問（FAQ）
Q. チェイン法とオープンアドレス法のどちらが優れていますか？
用途によって使い分けます。チェイン法はテーブルサイズを超えるデータでも格納でき、削除も容易です。一方、オープンアドレス法はリスト用のポインタが不要なためメモリ効率が高く、テーブルサイズが十分に大きければ高速に動作します。実務ではチェイン法が広く採用されていますが、試験では両方の仕組みを区別できればOKです。
Q. ハッシュ表で使うハッシュ関数と、セキュリティで使うハッシュ関数は同じものですか？
目的が異なります。ハッシュ表で使うハッシュ関数は「キーをテーブル内のインデックスに変換する」ことが目的で、高速性と均等な分散が重視されます。セキュリティ分野のSHA-256などは「元データの復元を計算上不可能にする」一方向性と衝突耐性が重視されます。試験では文脈で判断できるため混同の心配は不要です。
Q. プログラミング言語でハッシュ表はどのように使えますか？
多くの言語で標準ライブラリとして提供されています。Pythonでは「辞書型（dict）」、Javaでは「HashMap」、JavaScriptでは「オブジェクト（Object）」や「Map」がハッシュ表を内部的に利用したデータ構造です。キーと値のペアを格納・検索する操作が日常的に使われるため、実務でも最も利用頻度の高いデータ構造の一つです。
Q. ハッシュ表のサイズはどう決めるのが適切ですか？
格納予定のデータ件数よりも十分に大きい素数を選ぶのが定石です。素数にすることでmod演算の結果が偏りにくくなり、衝突の発生を抑えられます。テーブルの使用率（負荷率）が70〜80%を超えると衝突が急増するため、実務ではその閾値でテーブルを拡張する「リハッシュ」が行われます。試験範囲では深掘りされない話題なので、参考程度で構いません。
