ハッシュ表（ハッシュ法）とは？

ハッシュ表（ハッシュ法）の意味

キーをハッシュ関数で計算して格納位置（添字）を直接求める方式。データ量が増えても比較回数がほとんど増えず、理想的には探索・追加・削除がO(1)で行える。FEではハッシュ関数の計算結果を求める問題と、衝突が起きたときの動作が問われる。

ハッシュ表（ハッシュ法）の具体例

ハッシュ関数を「キーを7で割った余り」とすると、キー23は23 mod 7 = 2なので添字2の位置へ格納する。探索時も同じ計算をするだけで位置が分かるため、表の中を順に見ていく必要がない。

ハッシュ表（ハッシュ法）は試験でどう引っ掛けられる？

「常にO(1)」ではない。衝突が多発すると同じ位置に連なったデータを順にたどることになり、最悪はO(n)まで劣化する。また、ハッシュ表は順序を保持しないので、範囲検索や整列順の取り出しには向かない。異なるキーが同じ値になること自体は関数の欠陥ではなく、チェイン法（同じ位置に連結リストをぶら下げる）やオープンアドレス法（空きを探して置く）で処理する。

ハッシュ表（ハッシュ法）と関連する用語

• 計算量とO記法（オーダ記法）

ハッシュ表（ハッシュ法）が出た過去問

• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。

  正解：データ1個当たりの探索時間が、表の中のデータの個数に関わらず一定（横一直線）のグラフ

  要点：衝突なしのハッシュ表は件数によらず探索時間が一定

  ハッシュ表は、キーをハッシュ関数で計算して格納位置を直接求める方式なので、格納されているデータの数を1件ずつ調べる必要がない。衝突が起きない前提であれば、1件を探すのに要する時間は表の中の件数に左右されず一定になる。すなわち計算量はO(1)で、グラフは横軸に対して水平になる。

  出典：平成29年度 春期 エンベデッドシステムスペシャリスト試験 am2 問8（IPA）

• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。

  正解：横軸を表の中のデータの個数、縦軸をデータ1個当たりの探索時間としたとき、データの個数によらず探索時間が一定（水平）のグラフ

  要点：衝突がなければハッシュ表の探索時間は件数によらず一定

  ハッシュ表では、キーにハッシュ関数を適用して格納位置を直接計算するため、表を順に走査する必要がない。衝突が起きない前提なら、探索はハッシュ値の計算と1回のアクセスで完了するので、データ件数が増えても1件当たりの探索時間は変わらない。計算量でいえばO(1)であり、グラフは横軸に平行な直線になる。

  出典：令和3年度 秋期 エンベデッドシステムスペシャリスト試験 am2 問10（IPA）