ハッシュ表（ハッシュ法）とは？はっしゅひょう
ハッシュ表（ハッシュ法）とは、キーをハッシュ関数に通して格納位置を直接計算する表。件数が増えても比較回数がほとんど増えず、探索・追加・削除が平均O(1)で済む。比較を繰り返して絞り込むのではなく、計算1回で位置が決まる点が線形探索や二分探索との構造的な違いになる。
最終更新：2026-10-06
この語が出る過去問を解く →背景
表を先頭から見る方式は件数に比例して遅くなり、整列して二分探索してもlog nの比較が要る。キーそのものから位置を計算してしまえば、件数と探索時間の関係を切り離せる。組込みでこれが効くのは、受信したコマンドコードから処理関数を引く、機器IDから設定を引くといった、件数が決まっていて頻繁に引く用途である。
具体例
受信したコマンドIDから処理関数を引く表なら、表の大きさを16としてID 0x41は0x41 mod 16 = 1の位置に登録しておく。受信のたびに同じ剰余を求めるだけで飛び先が決まるため、対応コマンドが増えてもif文の連鎖が伸びない。
試験での引っ掛け
常にO(1)ではない。衝突が続けば同じ位置に連なった要素をたどることになり最悪はO(n)まで劣化するため、最悪実行時間を保証したい実時間処理では扱いに注意が要る。順序も保持しないので範囲検索や整列取り出しには向かない。衝突自体は欠陥ではなく、チェイン法やオープンアドレス法で処理する。
関連用語
出た過去問
出典：平成29年度 春期 エンベデッドシステムスペシャリスト試験 午前Ⅱ 問8（IPA）
ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。
正解：データ1個当たりの探索時間が、表の中のデータの個数に関わらず一定（横一直線）のグラフ
要点：衝突なしのハッシュ表は件数によらず探索時間が一定
ハッシュ表は、キーをハッシュ関数で計算して格納位置を直接求める方式なので、格納されているデータの数を1件ずつ調べる必要がない。衝突が起きない前提であれば、1件を探すのに要する時間は表の中の件数に左右されず一定になる。すなわち計算量はO(1)で、グラフは横軸に対して水平になる。
出典：令和3年度 秋期 エンベデッドシステムスペシャリスト試験 午前Ⅱ 問10（IPA）
ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。
正解：横軸を表の中のデータの個数、縦軸をデータ1個当たりの探索時間としたとき、データの個数によらず探索時間が一定（水平）のグラフ
要点：衝突がなければハッシュ表の探索時間は件数によらず一定
ハッシュ表では、キーにハッシュ関数を適用して格納位置を直接計算するため、表を順に走査する必要がない。衝突が起きない前提なら、探索はハッシュ値の計算と1回のアクセスで完了するので、データ件数が増えても1件当たりの探索時間は変わらない。計算量でいえばO(1)であり、グラフは横軸に平行な直線になる。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。