ハッシュ表（連想配列）とは？
ハッシュ表（連想配列）とは、キーをハッシュ関数で変換した値を添字として使い、データを格納・検索するデータ構造。理想的な条件下では、データ件数によらずほぼ一定時間（O(1)）で検索できる。
応用情報技術者試験の過去問では5回出題されています（2018年度〜2024年度）。
はっしゅひょう
ハッシュ表（連想配列）の意味
キーをハッシュ関数で変換した値を添字として使い、データを格納・検索するデータ構造。理想的な条件下では、データ件数によらずほぼ一定時間（O(1)）で検索できる。
ハッシュ表（連想配列）の具体例
社員番号をキーに氏名を格納するとき、社員番号をハッシュ関数で変換した位置に直接データを格納すれば、木構造での探索よりさらに高速に検索できる。
ハッシュ表（連想配列）は試験でどう引っ掛けられる？
ハッシュ値の衝突が多発すると、実際の検索性能が線形探索に近づいて低下することがある。
ハッシュ表（連想配列）と関連する用語
ハッシュ表（連想配列）が出た過去問
探索表の構成法を例とともにa〜cに示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。
正解：ア：a=2分探索，b=線形探索，c=ハッシュ表探索
要点：整列順は2分探索、頻度順は線形探索、計算位置はハッシュ表探索。
探索表の格納方法によって最適な探索法は変わる。コード順に整列して格納されている表は、中央と比較して範囲を半分に絞れるので2分探索が有効である。使用頻度の高い順に並べた表は先頭から順に見ると早く見つかるため線形探索が適し、コードから計算した位置に飛び飛びに格納した表はハッシュ表探索が適する。
出典：平成30年度 秋期 応用情報技術者試験 午前 問8（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) です。
出典：令和1年度 秋期 応用情報技術者試験 午前 問7（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 の倍数であることが条件になります。
出典：令和4年度 秋期 応用情報技術者試験 午前 問5（IPA）ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。
正解：データ数によらず探索時間が一定（水平線）のグラフ
要点：衝突がなければハッシュ表の探索時間はデータ数に依存せず一定
ハッシュ表では、キーからハッシュ関数で格納位置を直接計算して1回のアクセスで目的のデータに到達する。衝突が起こらない前提であれば、格納されているデータの個数が増えても1件あたりの探索時間は変わらない。したがってグラフは横軸に平行な水平線となる。
出典：令和5年度 春期 応用情報技術者試験 午前 問19（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)と表す関係である。
出典：令和6年度 秋期 応用情報技術者試験 午前 問6（IPA）
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。