オープンアドレス法

2025年10月22日

オープンアドレス法

英語表記: Open Addressing

概要

オープンアドレス法は、データ構造におけるハッシュテーブル（連想配列を実現するための基盤）で、異なるキーが同じ格納場所（インデックス）を指してしまう「衝突」（Collision）が発生した際に、その問題を解決するための主要な手法の一つです。これは、データ構造（リスト, スタック, キュー, ツリー）の分類の中でも、特にハッシュテーブルにおける「衝突解決法」という文脈で非常に重要な役割を果たしています。この手法の特徴は、衝突が発生しても、ハッシュテーブルの外部に新たなリスト（チェイン法）を作るのではなく、テーブル内部の空いている別の場所を探してデータを格納する点にあります。

詳細解説

オープンアドレス法は、ハッシュテーブルの効率を維持し、探索、挿入、削除といった操作を高速に行うことを目的とした衝突解決法です。データ構造の文脈では、配列（ハッシュテーブル）を効率的に利用しきるための工夫と理解することができます。

目的と動作原理

ハッシュテーブルは、キーをハッシュ関数にかけ、その結果得られたインデックスにデータを格納します。しかし、ハッシュ関数の性質上、異なるキー $K_1$ と $K_2$ が同じインデックス $i$ を生成する（$h(K_1) = h(K_2) = i$）衝突は避けられません。

オープンアドレス法では、衝突が発生すると、事前に定められた規則（プローブシーケンス）に従って、ハッシュテーブル内の次の空きセルを探索し始めます。この探索プロセスを「プロービング」（Probing）と呼びます。データが格納される場所は、常にハッシュテーブルの内部に限定されますので、ポインタや外部リストの管理が不要となり、メモリの局所性が高まる（キャッシュ効率が向上する）というメリットがあります。

主要なプロービング手法

オープンアドレス法の性能は、このプロービングの仕方によって大きく左右されます。主に以下の3つの手法が用いられます。

1. 線形プロービング (Linear Probing)

線形プロービングは最も単純な手法です。衝突が発生した場合、元のインデックス $i$ の次のセル $(i+1)$、その次のセル $(i+2)$、… と、一定間隔（通常は1）で順次探索していきます。

欠点（クラスター）: この方法は実装が簡単ですが、データが連続した塊（クラスター）として集まりやすいという重大な欠点があります。一度クラスターが形成されると、そのクラスターの末尾に到達するまで探索を続けなければならないため、探索効率が極端に悪化してしまいます。これは性能に直結するため、設計者はこの現象を避けるように心がける必要がありますね。

2. 二次プロービング (Quadratic Probing)

線形プロービングのクラスター問題を緩和するために考案されたのが二次プロービングです。衝突が発生した場合、探索間隔を二次関数的に広げていきます（例：$i+1^2, i+2^2, i+3^2, \dots$）。

効果: 探索間隔が非線形になるため、線形プロービングのような大きなクラスターの形成を防ぐことができます。しかし、元のハッシュ値が同じキー同士は、常に同じプローブシーケンスをたどるため、「二次クラスター」と呼ばれる別の種類のクラスター問題が発生する可能性が残ります。

3. 二重ハッシュ (Double Hashing)

二重ハッシュは、オープンアドレス法の中で最も洗練された手法の一つです。この方法では、衝突が発生した際のプロービングの「歩幅」を、キー $K$ ごとに、二つ目のハッシュ関数 $h_2(K)$ を使って動的に決定します。

仕組み: 最初のハッシュ関数 $h_1(K)$ で初期位置を決定し、衝突した場合、2番目のハッシュ関数 $h_2(K)$ の結果をステップサイズとして、テーブル内をジャンプしながら探索します。
利点: キーごとに異なるプローブシーケンスが生成されるため、クラスターの発生を効果的に抑え込み、探索性能を均一に保つことができます。実装は複雑になりますが、高い性能が求められるシステムでは非常に有用です。

データ構造としての特徴

オープンアドレス法は、データ構造の観点から見ると、メモリのオーバーヘッドが非常に小さいことが魅力です。チェイン法（外部チェイニング）では、各バケットにポインタやリストのノードといった付加的な情報が必要ですが、オープンアドレス法では、データそのものと、そのデータが「削除済み」（墓標/Tombstone）であることを示すフラグ以外は必要ありません。このシンプルさが、組み込みシステムやキャッシュなど、メモリ効率が最優先される場所で好まれる理由です。

具体例・活用シーン

オープンアドレス法の具体的な動作をイメージするために、駐車場のアナロジーを考えてみましょう。

アナロジー：予約駐車場の衝突解決

あなたは巨大な駐車場（ハッシュテーブル）に車を停めようとしています。車のナンバー（キー）を駐車場管理システム（ハッシュ関数）に入れると、「P5」（インデックス5）に停めなさい、という指示が出ました。

衝突なし（成功）: P5に行ってみると、空いていました。そこに車を停めます（データを格納）。
衝突発生: P5に行ってみると、すでに別の車が停まっています（衝突）。

線形プロービングの場合

管理人は「P5がダメなら、すぐに隣のP6を探しなさい。P6もダメならP7を探しなさい」と指示します。あなたは順番にP6, P7, P8…と歩いていき、最初に空いている場所を見つけてそこに駐車します。

問題点: もし多くの車がP5周辺に集中して指示された場合、P5, P6, P7, P8…という一連の駐車スペースが埋まってしまいます。これがクラスターです。新しく来た車は、この長蛇の列（クラスター）の最後尾まで歩いていかなければならず、駐車場を探す時間がどんどん長くなってしまいます。

二重ハッシュの場合

管理人は「P5がダメなら、あなたの車のナンバーに基づいて、次に探すべき場所の『歩幅』を計算しなさい」と指示します。

車Aのナンバーは「歩幅3」を計算しました。P5がダメなら、次はP8を探します。
車Bのナンバーは「歩幅7」を計算しました。P5がダメなら、次はP12を探します。

この方法なら、たとえ初期位置（P5）が同じでも、次に探す場所が車によってバラバラになります。これにより、特定の場所に車が集中して渋滞を引き起こす（クラスターを形成する）のを防ぎ、駐車場全体の効率が保たれます。二重ハッシュは、この「バラバラに探す」という点が非常に優れており、現実の高性能なハッシュテーブルでよく採用されるのもうなずけますね。

活用シーン

オープンアドレス法は、特にデータ構造の配列部分を最大限に活用したい場合に利用されます。

キャッシュメモリ: CPUのキャッシュなど、非常に高速なアクセスが求められ、メモリのオーバーヘッドを極力避けたい環境で利用されることがあります。ポインタの参照による間接的なアクセスは速度低下を招くため、テーブル内で完結するオープンアドレス法が有利です。
言語処理系: Pythonの辞書型（Dictionary）の実装など、多くのモダンな言語処理系内部で、オープンアドレス法やその派生形が使われています。これは、メモリ効率と平均的な高速性を両立できるからです。

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

ITパスポート、基本情報技術者、応用情報技術者などの試験では、ハッシュ法の衝突解決に関する問題は頻出です。特にオープンアドレス法とチェイン法（セパレートチェイニング）の比較は重要視されます。

| 項目 | 詳細な知識と出題パターン |
| :— | :— |
| 定義の理解 | 「衝突が発生した際に、ハッシュテーブルの空きセルを探索する方法」として正しく定義できるかを確認されます。「外部リストを使用しない」点がチェイン法との決定的な違いです。 |
| プロービングの種類 | 線形プロービング、二次プロービング、二重ハッシュの3種類は必ず覚えてください。特に線形プロービングの欠点である「クラスター（Primary Clustering）」の概念は、知識問題として頻繁に出題されます。 |
| チェイン法との比較 | オープンアドレス法は、一般に「メモリ効率が良い（ポインタが不要）」が、「データ密度が高くなると性能が急激に低下する（ロードファクタに敏感）」という特徴を問われます。チェイン法は性能の安定性に優れますが、メモリオーバーヘッドがあります。 |
| 削除処理の注意点 | オープンアドレス法でデータを削除する際、単純にセルを空にしてしまうと、そのセルを飛び越えて格納された後のデータの探索に失敗してしまいます。そのため、論理的に削除されたことを示す「墓標（Tombstone）」を設置する必要がある、という仕組みは応用情報技術者試験レベルで問われることがあります。 |
| 探索のメカニズム | データの探索時も、挿入時と同じプローブシーケンスをたどる必要があります。目的のキーが見つかるか、または空のセルに到達するまで探索を続ける、というプロセスを理解しておきましょう。 |