最終更新日：2026年7月30日

fe fe-technology data-structure algorithm

まず結論

ハッシュ表とは、キーをハッシュ関数に入力し、データを格納するアドレスを求めるデータ構造です。

基本情報技術者試験では、次の関係を最初に押さえます。

キー
  ↓ ハッシュ関数
格納先のアドレス

試験では、キーからアドレスを求める計算だけでなく、同じアドレスが求められる衝突も問われます。

直感的な説明

たくさんの引き出しが並んだ棚を考えます。

普通にデータを探す場合は、先頭から一つずつ確認することがあります。

一方、ハッシュ表では、キーから引き出し番号を計算します。

会員番号 55550
  ↓ 計算
引き出し番号 0260

引き出し番号がすぐに分かれば、先頭から順番に探す必要がありません。

ただし、異なるキーから同じ引き出し番号が求められることがあります。これが衝突です。

定義・仕組み

ハッシュ表では、キーとデータを対応させて管理します。

用語 意味
キー データを識別する値
ハッシュ関数 キーからアドレスを求める計算規則
ハッシュ値 ハッシュ関数によって得られた値
ハッシュ表 求めたアドレスを使ってデータを格納する表
衝突 異なるキーから同じアドレスが求められること

基数変換法

基数変換法は、キーを別の進数として扱い、10進数へ変換した結果からアドレスを求める方法です。

例えば、キー 55550 を11進数とみなして10進数へ変換する場合は、次のように計算します。

55550₍11₎
= 5×11⁴ + 5×11³ + 5×11² + 5×11¹ + 0×11⁰
= 80520

その後、問題文の指示に従って下4桁を取り出し、係数を掛けます。

80520の下4桁 → 0520
0520 × 0.5 → 0260

このような問題では、次の順番を崩さないことが大切です。

1. 指定された進数として読む
2. 10進数へ変換する
3. 指定された桁を取り出す
4. 係数を掛ける
5. 必要なら切り捨てる

進数変換そのものを復習したい場合は、16進小数の変換も参考になります。

除算法

除算法は、キーを表の大きさなどで割り、その余りをアドレスとして使う方法です。

アドレス = キー mod 表の大きさ

例えば、キーが123、表の大きさが10なら、余り3をアドレスとして使います。

衝突への対応

異なるキーから同じアドレスが求められると、そのままでは同じ場所へ格納できません。

代表的な対応には、次の方法があります。

方法 考え方
チェイン法 同じアドレスのデータを連結して管理する
オープンアドレス法 空いている別の場所を探して格納する

チェイン法は、連結リストの考え方と関係します。

このテーマは、基本情報技術者試験の「データ構造」と「アルゴリズム」に関係する内容です。公式の出題範囲やシラバスは、IPA：基本情報技術者試験から確認できます。

科目Aでどう出る？

科目Aでは、ハッシュ関数の計算手順や、用語の役割を選ばせる問題が中心です。

問題文の表現 選ぶ用語・考え方
キーから格納先を計算する ハッシュ関数
キーとデータをアドレスで対応させる ハッシュ表
異なるキーが同じアドレスになる 衝突
キーを別の進数とみなして変換する 基数変換法
キーを割った余りを使う 除算法

計算問題では、ハッシュ表の大きさやアドレス範囲も確認します。

アドレス範囲が0000〜4999
→ 得られた値が範囲内か確認する

また、次の2つを混同しないことが大切です。

進数を変換する
→ 計算の途中手順

キーから格納先を決める
→ ハッシュ関数の目的

科目Bでどう使う？

科目Bでは、配列をハッシュ表として使う疑似言語や、衝突時の処理を追う問題に関係します。

読むときは、次の点を順番に確認します。

1. キーから最初のアドレスをどう求めるか
2. その場所が空いているか
3. 衝突したときに次の場所をどう探すか
4. 探索をどの条件で終了するか

オープンアドレス法では、衝突後にアドレスを一つずつずらす処理などが使われます。

最初のアドレスが使用中
  ↓
次のアドレスを確認
  ↓
空きが見つかるまで繰り返す

このとき、配列の添字、繰返し回数、表の末尾に達した後の戻り方を追うことがポイントです。

探索方法との違いも整理しておきましょう。線形探索は先頭から順番に探し、二分探索は整列済みデータを半分ずつ絞り込みます。ハッシュ法は、キーから格納先を直接計算する考え方です。

よくある誤解・混同

誤解1：ハッシュ関数は暗号化のためだけに使う

ハッシュという言葉は情報セキュリティでも使われますが、ハッシュ表では、キーから格納先を求めることが目的です。

ハッシュ表
→ データの格納・探索

暗号学的ハッシュ関数
→ 改ざん検知など

同じ「ハッシュ」でも、問題文の目的を確認します。

誤解2：基数変換法は進数変換だけの問題だと思う

10進数へ変換したところで終わりではありません。

10進数へ変換
  ↓
指定された桁を取り出す
  ↓
係数を掛ける
  ↓
アドレスを決める

最後に何をアドレスとして使うのかまで確認します。

誤解3：異なるキーなら必ず異なるアドレスになる

ハッシュ表のアドレス数には限りがあるため、異なるキーから同じアドレスが求められることがあります。

異なるキー
  ↓
同じアドレス
  → 衝突

誤解4：ハッシュ法なら必ず1回で見つかる

衝突がなければ高速にアクセスできますが、衝突が多いと追加の探索が必要になります。

そのため、ハッシュ関数の選び方や衝突への対応が重要です。

まとめ（試験直前用）

  • ハッシュ表は、キーから格納先アドレスを求めてデータを管理する
  • キーからアドレスを求める計算規則がハッシュ関数
  • 基数変換法は、キーを指定された進数として10進数へ変換して使う
  • 異なるキーが同じアドレスになることを衝突という
  • 進数変換で終わらず、桁の抽出・係数・切捨てまで問題文どおりに行う

© 2024-2026 stemtazoo. All rights reserved.