オープンアドレス法

2025年10月20日

オープンアドレス法

英語表記: Open Addressing

概要

オープンアドレス法は、アルゴリズムと計算量 → 探索アルゴリズム → ハッシュ探索という流れの中で、データ格納時に発生する「衝突（コリジョン）」を解決するための重要な手法の一つです。ハッシュ関数によって算出されたアドレスが既に埋まっていた場合、メモリ上の他の空いている場所を探し出してデータを格納する方式を採用しています。配列（テーブル）の空きスペースを「開いているアドレス」として見つけ出し、そこを利用することからこの名前がついています。

詳細解説

オープンアドレス法は、探索アルゴリズムの中でも特に高速なデータアクセスを実現するハッシュ探索の効率を維持するために不可欠な技術です。ハッシュ探索では、キー（鍵）を入力すると、ハッシュ関数がそのデータが格納されるべきアドレスを計算します。しかし、異なるキーにもかかわらず同じアドレスが算出されてしまう現象、すなわち「衝突」が避けられません。オープンアドレス法は、この衝突が発生した際の「次の行動」を規定するものです。

目的と動作原理

この手法の主な目的は、データをテーブル内に分散させ、探索時も効率よくデータを見つけ出すことです。衝突が発生した場合、オープンアドレス法では、データを格納するハッシュテーブルの配列構造を離れることなく、テーブル内の別の空きスロットを探索します。

具体的には、衝突が発生した最初の位置から、あらかじめ定められた規則に従って順次アドレスを走査（プロービング）していきます。そして、最初に見つけた空のスロットにデータを格納します。この「空きを探す」という動作が、オープンアドレス法の核心です。

主要な走査（プロービング）手法

オープンアドレス法には、空きスロットを探すための代表的な三つのルールが存在します。このルールの選択が、ハッシュ探索の性能に大きく影響するため、非常に興味深いポイントです。

1. 線形走査（Linear Probing）

衝突が発生したアドレス $H(k)$ の直後から、アドレスを一つずつ線形に（$H(k)+1, H(k)+2, \ldots$）確認していく最もシンプルな方法です。
* 利点: 実装が非常に簡単です。
* 欠点: データが連続して固まってしまう「クラスター化」が発生しやすいです。一度クラスターができると、新しいデータがそのクラスターの末尾に追加されやすくなり、探索効率が大幅に低下してしまいます。これは性能を考える上で大きな課題です。

2. 二次走査（Quadratic Probing）

線形走査の欠点であるクラスター化を避けるために考案されました。衝突が発生したアドレスから、探索間隔を二乗の順序（$H(k)+1^2, H(k)+2^2, H(k)+3^2, \ldots$）で離していく方法です。
* 利点: 線形走査よりもクラスター化を抑制できます。
* 欠点: 初期衝突アドレスが同じキー群（シノニム）は、同じ探索シーケンスをたどってしまい、「二次クラスター化」と呼ばれる現象を引き起こす可能性があります。

3. ダブルハッシング（Double Hashing）

最も洗練された手法の一つで、衝突が発生した場合、探索間隔を固定値ではなく、別のハッシュ関数（第二ハッシュ関数）を使って計算します。
* 動作: $H(k) + i \times H'(k)$ のように、探索ステップ幅 $H'(k)$ がキー $k$ ごとに異なります。
* 利点: キーによって探索シーケンスが完全に異なるため、クラスター化を最も効果的に防ぐことができます。非常に高い探索効率を維持できるため、高性能を求める場合に採用されることが多いです。

ハッシュ探索における位置づけ

オープンアドレス法は、ハッシュテーブルの全要素を一つの連続したメモリ領域（配列）内に保持します。これに対し、衝突解決のもう一つの主要な手法である「チェイン法」は、衝突した要素をリスト構造（リンクリスト）で繋いで管理します。

オープンアドレス法は、ポインタ（リンク）を使用しないため、メモリの局所性が高く、CPUのキャッシュメモリを効率よく利用できるという大きなメリットがあります。これは、アルゴリズムと計算量の観点から見ると、実測値としてのパフォーマンス向上に直結する重要な特徴と言えるでしょう。

具体例・活用シーン

オープンアドレス法がどのように機能するかを理解するために、身近な例で考えてみましょう。これは、ハッシュ探索という抽象的な概念を理解するための強力な手助けになります。

アナロジー：集合住宅の宅配ロッカー

ある集合住宅に、居住者専用の宅配ロッカーが100個あると想像してください。これがハッシュテーブル（配列）です。

ハッシュ関数の適用: 宅配業者は、部屋番号（キー）をロッカー番号（アドレス）に変換するルールを持っています。例えば、「部屋番号の下二桁」がロッカー番号だとしましょう。
衝突の発生: 部屋番号105号室のAさんと、部屋番号205号室のBさんの荷物が同時に届きました。ハッシュ関数を適用すると、どちらもロッカー番号「05番」を指定します。ここに「衝突」が発生しました。
オープンアドレス法の適用（線形走査）:
- Aさんの荷物は先に届いたので、05番に格納されました。
- Bさんの荷物が届き、05番が埋まっていることを確認しました。
- 宅配業者はオープンアドレス法に従い、05番の次、次、次と順番に空きを探し始めます（線形走査）。
- 06番が埋まっている、07番が埋まっている……と確認し、運良く08番が空いていたとします。
- Bさんの荷物は08番に格納されました。

探索時の動作

後日、Bさんが荷物を取りに来ました。
1. Bさんは部屋番号205号室（キー）をロッカー管理システムに入力します。
2. システムはハッシュ関数を適用し、まず05番を探します。
3. 05番にはAさんの荷物が入っています（キーが一致しません）。
4. システムはオープンアドレス法のルール（線形走査）に従い、06番、07番……と確認を続け、最終的に08番でBさんの荷物（キーが一致）を発見し、取り出しが完了します。

このように、オープンアドレス法は「衝突しても諦めず、テーブル内で次の空きを探す」という、非常に律儀なルールに基づいているのです。もし衝突が多発すると、探しに行く回数が増え（プローブ回数が増加）、探索効率が落ちてしまうことが、このアナロジーからもよく理解できますね。

活用シーン

キャッシュメモリ管理: 高速なアクセスが求められるCPUキャッシュやデータベースのインメモリキャッシュなどで、オープンアドレス法が利用されることがあります。ポインタのオーバーヘッドがない点が有利に働きます。
組み込みシステム: メモリが限られた環境や、単純なデータ構造で高速な検索を実現したい場合に適しています。

資格試験向けチェックポイント

IT系の資格試験、特に基本情報技術者試験や応用情報技術者試験では、アルゴリズムと計算量 → ハッシュ探索の分野から、オープンアドレス法とその比較に関する問題が頻出します。以下の点を重点的にチェックしてください。

衝突解決手法の二大巨頭: オープンアドレス法とチェイン法（セパレートチェイニング）の違いを明確に理解することが必須です。
- オープンアドレス法：テーブル内にデータを直接格納する（配列のみ使用）。
- チェイン法：衝突したデータをリンクリストでつなぐ（ポインタを使用）。
線形走査の欠点: 「クラスター化」という用語と、それが探索効率を著しく低下させる理由を説明できるようにしておきましょう。クラスター化を避けるために二次走査やダブルハッシングが使われる、という流れも重要です。
ダブルハッシングの仕組み: ダブルハッシングが「二つのハッシュ関数」を使うことで、最も衝突を分散させる効果が高い、という点を覚えておいてください。これは理論的な性能を示す指標としてよく問われます。
削除時の注意点: オープンアドレス法では、データを単純に削除してしまうと、そのデータよりも後に格納されたデータを探索できなくなる可能性があります。そのため、削除時にはそのスロットを「削除済み」とマークする特殊な処理（レイジーデリート）が必要になる、という知識も応用情報技術者試験レベルでは問われることがあります。
負荷率（ロードファクタ）: テーブルの利用率が高くなるほど（負荷率が高まるほど）、衝突が発生しやすくなり、オープンアドレス法の性能が急速に悪化します。テーブルの拡張（リハッシュ）が必要となるタイミングを理解しておくことも、アルゴリズムと計算量の視点からは重要です。