ハッシュ表（連想配列）とは？はっしゅひょう
ハッシュ表（連想配列）とは、キーそのものから格納位置を計算で求め、比較を繰り返さずに1回で目的の要素へ到達するデータ構造。平均の探索・挿入・削除がいずれもO(1)で、件数が増えても劣化しないのが最大の利点。反面、格納順序は保たれず範囲検索には向かない。
最終更新：2026-10-06
この語が出る過去問を解く →背景
探索の高速化は長らく「比較の回数を減らす」方向で発展し、2分探索や2分探索木は範囲を半分ずつ捨ててlog nまで縮めた。それでも比較を行う限り件数の影響からは逃れられない。位置を計算で決めてしまえば比較そのものが要らなくなる——この転換がハッシュ法であり、応用情報では計算量の比較とシノニム対策の理解までが問われる。
具体例
PythonのdictやJavaのHashMapは内部がハッシュ表で、Redisやmemcachedのキー値参照も同じ原理。DBのオプティマイザが等価結合で選ぶハッシュジョインも、片方の表をハッシュ表に載せて突き合わせている。
試験での引っ掛け
異なるキーが同じ位置に落ちるシノニムの扱い（チェイン法・オープンアドレス法）が定番の出題で、集中すると最悪O(n)まで落ちる。O(1)は平均であって最悪ではない。整列済みの列を返す用途や範囲検索は2分探索木側の役割で、ハッシュ表では代替できない。
関連用語
出た過去問
出典：平成30年度 秋期 応用情報技術者試験 午前 問8（IPA）
探索表の構成法を例とともにa〜cに示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。
正解：ア：a=2分探索，b=線形探索，c=ハッシュ表探索
要点：整列順は2分探索、頻度順は線形探索、計算位置はハッシュ表探索。
探索表の格納方法によって最適な探索法は変わる。コード順に整列して格納されている表は、中央と比較して範囲を半分に絞れるので2分探索が有効である。使用頻度の高い順に並べた表は先頭から順に見ると早く見つかるため線形探索が適し、コードから計算した位置に飛び飛びに格納した表はハッシュ表探索が適する。
出典：令和元年度 秋期 応用情報技術者試験 午前 問7（IPA）
自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n とすると、任意のキーaとbが衝突する条件は…
正解：a-bがnの倍数
要点：同じ剰余になる条件は、2つのキーの差がnの倍数であること
衝突とは異なるキーのハッシュ値が一致することなので、a mod n = b mod n が条件です。これは a と b を n で割った余りが等しい、すなわち a-b が n で割り切れる（nの倍数である）ことと同値です。合同式で書けば a≡b (mod n) です。
出典：令和4年度 秋期 応用情報技術者試験 午前 問5（IPA）
自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x)＝x mod n とすると、任意のキーaとbが衝突する条件はどれ…
正解：a－bがnの倍数
要点：ハッシュ衝突は差がハッシュ表サイズの倍数になるとき
衝突するのは h(a) = h(b)、つまり a と b を n で割った余りが等しいときです。余りが等しいことは差 a − b が n で割り切れることと同値なので、a − b が n の倍数であることが条件になります。
出典：令和5年度 春期 応用情報技術者試験 午前 問19（IPA）
ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。
正解：データ数によらず探索時間が一定（水平線）のグラフ
要点：衝突がなければハッシュ表の探索時間はデータ数に依存せず一定
ハッシュ表では、キーからハッシュ関数で格納位置を直接計算して1回のアクセスで目的のデータに到達する。衝突が起こらない前提であれば、格納されているデータの個数が増えても1件あたりの探索時間は変わらない。したがってグラフは横軸に平行な水平線となる。
出典：令和6年度 秋期 応用情報技術者試験 午前 問6（IPA）
自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n とすると、任意のキーaとbが衝突する条件は…
正解：a－bがnの倍数
要点：ハッシュ衝突はa≡b(mod n)、すなわちa−bがnの倍数のとき
衝突とはh(a)=h(b)、つまりa mod n = b mod nが成り立つことである。これは、aとbをnで割った余りが等しいということなので、差a－bがnで割り切れる（nの倍数である）ことと同値になる。合同式ではa≡b (mod n)と表す関係である。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。