プライマリクラスタリング

コンピュータ プログラミングにおいて、プライマリ クラスタリングは、線形プローブ ハッシュ テーブルのパフォーマンス低下を引き起こす現象です。この現象は、線形プローブ ハッシュ テーブルに要素が追加されると、それらの要素が長いラン (つまり、空きスロットのないハッシュ テーブルの連続した長い領域) に集まる傾向があることを示しています。ハッシュ テーブルが、あるパラメータ に対しての負荷係数である場合、特定の要素を含むランの予想される長さはです。これにより、線形プローブ ハッシュ テーブルでの 挿入と否定クエリに予想される時間がかかります。${\displaystyle 1-1/x}$${\displaystyle x\geq 2}$${\displaystyle u}$${\displaystyle \Theta (x^{2})}$${\displaystyle \Theta (x^{2})}$

プライマリ クラスタリングには 2 つの原因があります。

• 勝者は勝ち続ける:実行が長くなればなるほど、追加の要素を蓄積する可能性が高くなります。これにより、クラスタリング効果に寄与する正のフィードバックループが発生します。ただし、これだけでは二次爆発は発生しません。^{[1] [2]}
• ランの結合: 1 回の挿入により、そのランの長さが 1 つ増加するだけでなく、すでに比較的長い 2 つのランが結合されることもあります。これが、予想されるランの長さが 2 乗的に増加する原因です。^[1]

プライマリ クラスタリングを理解するもう 1 つの方法は、ハッシュ テーブル内の特定の領域にハッシュされるアイテムの数の標準偏差を調べることです。^[2]サイズ のハッシュ テーブルのサブ領域を考えます。領域にハッシュされるアイテムの予想数は です。一方、そのようなアイテムの数の標準偏差は です。したがって、確率 で、領域にハッシュされるアイテムの数は領域のサイズを超えます。直感的に、これは サイズの領域はオーバーフローすることが多いが、より大きな領域は通常オーバーフローしないことを意味します。この直感は、プライマリ クラスタリングの正式な分析の出発点としてよく使用されます。^{[2] [3] [4]}${\displaystyle x^{2}}$${\displaystyle (1-1/x)x^{2}=x^{2}-x}$${\displaystyle \Theta (x)}$${\displaystyle \オメガ (1)}$${\displaystyle x^{2}}$${\displaystyle \Theta (x^{2})}$

プライマリクラスタリングは、線形プローブハッシュテーブルでの挿入とクエリの両方でパフォーマンスの低下を引き起こします。挿入は実行の最後まで移動する必要があるため、予想時間がかかります。^[1]負のクエリ（存在しないことが判明した要素を検索するクエリ）も実行の最後まで移動する必要があるため、予想時間がかかります。^[1]正のクエリは、検索している要素が見つかるとすぐに終了できます。その結果、ハッシュテーブル内のランダムな要素をクエリするのに予想される時間は です。^[1]ただし、最近挿入された要素（たとえば、挿入されたばかりの要素）に対する正のクエリには、予想時間がかかります。^[1]${\displaystyle \Theta (x^{2})}$${\displaystyle \Theta (x^{2})}$${\displaystyle \Theta (x)}$${\displaystyle \Theta (x^{2})}$

これらの境界は、ハッシュテーブルが半頻繁に再構築され（そしてトゥームストーンがクリアされる）、遅延削除（つまり、削除にトゥームストーンを使用する）による線形プローブにも当てはまります。挿入ごとに少なくとも1回このような再構築を実行すれば十分です。^[2]${\displaystyle n/(2x)}$

多くの教科書では、勝者が勝ち続ける効果（連続が長くなるほど、追加要素を獲得する可能性が高くなる）がプライマリクラスタリングの唯一の原因であると説明されています。^{[5] [6] [7] [8] [9] [10] [11]}しかし、Knuthが指摘しているように、^[1]これはプライマリクラスタリングの主な原因ではありません。

いくつかの教科書では、正のクエリの予想実行時間はであると述べており、^{[11] [12]}通常は Knuth を引用しています。^[1]これはランダムな要素へのクエリには当てはまります。ただし、一部の正のクエリでは、予想実行時間がはるかに長くなる場合があります。たとえば、要素を挿入し、すぐにその要素をクエリする場合、クエリには挿入と同じ時間がかかり、これは予想どおりです。 ${\displaystyle \Theta (x)}$${\displaystyle \Theta (x^{2})}$

順序付き線形プロービング^[13]（ロビンフッドハッシュ^[14]とも呼ばれる）は、プライマリクラスタリングがクエリに与える影響を軽減する手法である。順序付き線形プロービングは、各実行内の要素をハッシュでソートする。したがって、クエリは、クエリ対象の要素よりもハッシュが大きい要素に遭遇するとすぐに終了することができる。この結果、正のクエリと負のクエリの両方が予想どおりの時間がかかる。 ${\displaystyle O(x)}$

墓地ハッシュ法は順序付き線形プローブの変形で、すべての操作でプライマリクラスタリングの漸近効果を排除します。^[2]墓地ハッシュ法は、将来の挿入で利用できるように実行内にギャップを戦略的に残します。これらのギャップは、墓石（遅延削除によって作成されるものなど）と考えることができ、半定期的な再構築中にテーブルに挿入されます。ギャップは、次の半定期的な再構築が発生するまで行われる挿入を高速化します。墓地ハッシュテーブルでのすべての操作には、予想時間がかかります。 ${\displaystyle O(x)}$

多くの情報源では、一次クラスタリングの影響を経験的に回避する線形プロービングの代替として、 二次プロービングの使用を推奨しています。