オープンアドレス

オープンアドレッシング、またはクローズドハッシュは、ハッシュテーブルにおける衝突解決法です。この方法では、ハッシュ衝突はプローブ、つまり配列内の代替位置（プローブシーケンス）を検索することで解決され、ターゲットレコードが見つかるか、未使用の配列スロットが見つかるまで続きます。未使用の配列スロットは、テーブル内にそのようなキーが存在しないことを示します。^[1]よく知られているプローブシーケンスには次のものがあります。

リニアプローブ

プローブ間の間隔は固定されており、多くの場合 1 に設定されます。

二次プロービング

プローブ間の間隔が線形に増加する（したがって、インデックスは二次関数で記述される）。

ダブルハッシュ

プローブ間の間隔はレコードごとに固定されていますが、別のハッシュ関数によって計算されます。

これらの方法の主なトレードオフは、線形プロービングはキャッシュ パフォーマンスが最も優れているものの、クラスタリングの影響を最も受けやすいのに対し、二重ハッシュはキャッシュ パフォーマンスが低いものの、クラスタリングはほとんど発生しないという点です。二次プロービングは、両方の点で中間に位置します。二重ハッシュでは、他の形式のプロービングよりも多くの計算が必要になる場合もあります。

ホップスコッチハッシュ、 ロビンフッドハッシュ、ラストカムファーストサーブハッシュ、カッコウハッシュなどのオープンアドレス方式では、 配列内の既存のキーを移動して新しいキーのためのスペースを確保します。これにより、プローブに基づく方法よりも最大検索時間が短縮されます。 ^{[2] [3] [4] [5] [6]}

オープン アドレッシング ハッシュ テーブルのパフォーマンスに重大な影響を与えるのは、負荷係数、つまり、使用される配列内のスロットの割合です。負荷係数が 100% に近づくにつれて、特定のキーを検索または挿入するために必要なプローブの数が劇的に増加します。テーブルがいっぱいになると、プローブ アルゴリズムが終了しなくなることもあります。ハッシュ関数が優れていても、負荷係数は通常 80% に制限されます。貧弱なハッシュ関数は、特に最も単純な線形アドレッシング方法では、著しいクラスタリングを生成するため、非常に低い負荷係数でもパフォーマンスが低下する可能性があります。一般に、ほとんどのオープン アドレッシング方法での典型的な負荷係数は 50% ですが、個別のチェーンでは通常、最大 100% を使用できます。

次の疑似コードは、線形プローブと単一スロット ステップを使用したオープン アドレス指定ハッシュ テーブルの実装です。これは、ハッシュ関数が適切である場合に効果的な一般的なアプローチです。lookup、set、およびremoveの各関数は、共通の内部関数find_slotを使用して、指定されたキーが含まれているか含まれているはずの配列スロットを検索します。

レコードペア { キー、値、占有フラグ（最初は未設定） }
変数ペア slot[0]、slot[1]、...、slot[num_slots - 1]

関数find_slot(キー)
    i := hash(key) modulo num_slots
    // キーが見つかるか、空のスロットが見つかるまで検索します。
    while (slot[i] is filled) and (slot[i].key ≠ key)
        i := (i + 1) num_slotsを法として
    戻る​

関数lookup(キー)
    i := find_slot(キー)
    slot[i] が使用されている   場合// キーはテーブル内にあり、
         slot[i].value
    を返します。そうでない場合                     // キーはテーブル内になく、
        見つかりませんを
返します。

関数set(キー, 値)
    i := find_slot(キー)
    slot[i]が占有されている   場合// キーが見つかった
        スロット[i].値:=値
        
    テーブルがほぼ満杯の場合に返す
        テーブルを大きく再構築する（注1）
        i := find_slot(キー)
    スロット[i]を占有済みとしてマークする
    スロット[i].key := キー
    スロット[i].値:=値

注1

テーブルを再構築するには、より大きな配列を割り当て、set操作を再帰的に使用して、古い配列のすべての要素を新しい大きな配列に挿入する必要があります。配列のサイズを指数的に増やすのが一般的です。たとえば、古い配列のサイズを 2 倍にします。

関数削除(キー)
    i := find_slot(キー)
    スロット[i]が空いている
        場合はreturn    // キーはテーブルにありません
    スロット[i]を空としてマークする
    j := i
    ループ （注2）
        j := (j + 1) num_slotsを法として
        スロット[j]が空いている
            場合はループを終了する
        k := hash(slot[j].key) num_slotsを法とする
        // k が (i,j] に循環的に含まれているかどうかを判断します
        // i ≤ j: | i..k..j | 
        // i > j: |.k..j i....| または |....j i..k.| 
        if i ≤ j
             if (i < k) and (k ≤ j)
                ループを続行
        else 
            if (k ≤ j) or (i < k)
                ループを続行
        スロット[i]を占有済みとしてマークする
        スロット[i].キー := スロット[j].キー
        スロット[i].値 := スロット[j].値
        スロット[j]を空としてマークする
        私 := j

注2

クラスター内のすべてのレコードについて、自然なハッシュ位置と現在の位置の間に空きスロットがあってはなりません (そうでない場合、レコードが見つかる前に検索が終了します)。擬似コードのこの時点で、i は空きスロットであり、クラスター内の後続のレコードに対してこのプロパティが無効になる可能性があります。jはそのような後続のレコードです。kは、衝突がない場合にjのレコードがハッシュ テーブルに自然に置かれる生のハッシュです。このテストは、 iが空になったため、 jのレコードがクラスターの必須プロパティに対して無効な位置にあるかどうかを尋ねています。

削除のための別の手法は、単にスロットを削除済みとしてマークすることです。ただし、この方法では、削除されたレコードを削除するためだけにテーブルを再構築する必要があります。上記の方法では、O (1) の更新と既存レコードの削除が提供され、テーブル サイズの上限が大きくなると、ときどき再構築が行われます。

上記のO (1)削除方法は、単一スロットステップで線形プローブされたハッシュテーブルでのみ可能です。1回の操作で多数のレコードを削除する場合は、削除するスロットをマークして後で再構築する方が効率的です。

• 遅延削除- オープン アドレス指定を使用してハッシュ テーブルから削除する方法。