データ構造におけるオーバーフロー処理

新しいペア（キー、要素）のホームバケットがいっぱいになると、オーバーフローが発生します。

オーバーフローに対処する可能性があります

ハッシュテーブルを体系的に検索して、いっぱいになっていないバケットを探します。

• 線形プロービング（線形オープンアドレス法）。
• 二次プロービング。
• ランダムプロービング。

各バケットがホームバケットであるすべてのペアのリストを保持できるようにすることで、オーバーフローを排除します。

• 配列線形リスト。
• チェーン。

オープンアドレス法は、すべての要素がハッシュテーブルに直接格納されるようにするために実行されるため、さまざまなメソッドを実装して衝突を解決しようとします。

線形プロービングは、データをテーブルの次の空きスロットに配置することによって衝突を解決するために実行されます。

線形プロービングのパフォーマンス

• 最悪の場合の検索/挿入/消去時間はθ（m）です。ここで、mはテーブル内のペアの数として扱われます。
• これは、すべてのペアが同じクラスターにある場合に発生します。

線形プロービングの問題

• 識別子は一緒にクラスター化する傾向があります
• 隣接するクラスターは合体する傾向があります
• 検索時間を延長または強化

二次プロービング

線形プロービングはバケットを検索します（H（x）+ i2）％b; H（x）はxのハッシュ関数を示します

二次プロービングは、増分としてiの二次関数を実装します

バケットH（x）、（H（x）+ i2）％b、（H（x）-i2）％bを調べ、1 <=i <=（b-1）/ 2

bは4j+3の形式の素数として示され、jは整数です

ランダムプロービング

ランダムプロービングは、乱数を組み込んで実行します。

H(x):= (H’(x) + S[i]) % b
S[i] is a table along with size b-1
S[i] is indicated as a random permutation of integers [1, b-1].