リニアプローブ

線形プローブは、ハッシュ テーブル(キーと値のペアのコレクションを維持し、特定のキーに関連付けられた値を検索するためのデータ構造)内の衝突を解決するためのコンピュータ プログラミングのスキームです。1954 年にGene Amdahl、Elaine M. McGraw、Arthur Samuelによって発明され、1963 年にDonald Knuthによって初めて分析されました。

二次プロービングや二重ハッシュ法とともに、線形プロービングはオープン アドレッシングの一形態です。これらの方式では、ハッシュ テーブルの各セルに 1 つのキーと値のペアが格納されます。ハッシュ関数が、ハッシュ テーブル内の別のキーがすでに占有されているセルに新しいキーをマッピングすることで衝突が発生すると、線形プロービングはテーブル内で最も近い次の空き位置を検索し、そこに新しいキーを挿入します。検索は同様に実行され、ハッシュ関数によって指定された位置から始めて、一致するキーを持つセルまたは空のセルが見つかるまでテーブルを順番に検索します。

Thorup & Zhang (2012) は、「ハッシュ テーブルは最も一般的に使用される重要なデータ構造であり、標準ハードウェアでの最も一般的な実装は高速かつシンプルな線形プローブを使用している」と書いています。^{[1]線形プローブは}参照の局所性が 優れているため、高いパフォーマンスを提供できますが、他の衝突解決スキームよりもハッシュ関数の品質に敏感です。ランダム ハッシュ関数、5 独立ハッシュ関数、またはタブレーション ハッシュを使用して実装した場合、検索、挿入、または削除ごとに一定の予想時間がかかります。MurmurHashなどの他のハッシュ関数でも実際には良好な結果が得られます。^[2]

線形プローブは、ハッシュ テーブルを使用して辞書問題を解決するためのオープン アドレッシングスキームのコンポーネントです。辞書問題では、データ構造はキーと値のペアのコレクションを保持し、コレクションからペアを挿入または削除する操作、または特定のキーに関連付けられた値を検索する操作の対象となります。この問題に対するオープン アドレッシング ソリューションでは、データ構造は配列T (ハッシュ テーブル) であり、そのセルT [ i ] (空でない場合) にはそれぞれ 1 つのキーと値のペアが格納されます。ハッシュ関数は、各キーをそのキーが格納されるTのセルにマッピングするために使用されます。通常、キーをスクランブルして、同様の値を持つキーがテーブル内で互いに近くに配置されないようにします。ハッシュ関数がキーを別のキーで既に占有されているセルにマッピングすると、ハッシュ衝突が発生します。線形プローブは、新しいキーを最も近い次の空のセルに配置することで衝突を解決する戦略です。^{[3] [4]}

与えられたキーxを検索するには、 Tのセルが調べられます。まず、インデックスh ( x ) ( hはハッシュ関数) のセルから始めて、隣接するセルh ( x ) + 1、h ( x ) + 2、... まで調べられ、空のセルまたはキーがxであるセルが見つかるまで続きます。キーを含むセルが見つかった場合、検索はそのセルの値を返します。そうでない場合、空のセルが見つかった場合、キーはテーブル内に存在しません。なぜなら、キーは、まだ検索されていない後のセルよりも優先してそのセルに配置されているからです。この場合、検索の結果として、キーが辞書に存在しないことが返されます。^{[3] [4]}

キーと値のペア( x、v ) をテーブルに挿入するには (同じキーを持つ既存のペアを置き換えることも可能)、挿入アルゴリズムは検索と同じセルのシーケンスをたどり、空のセルまたは格納されているキーがxであるセルが見つかるまで続けます。次に、新しいキーと値のペアがそのセルに配置されます。^{[3] [4]}

挿入によってテーブルの負荷係数（占有セルの割合）が事前に設定されたしきい値を超えて増加する場合、動的配列のように、テーブル全体が新しいハッシュ関数を持つ定数倍大きい新しいテーブルに置き換えられることがあります。このしきい値を 0 に近く設定し、テーブル サイズの増加率を高くすると、しきい値が 1 に近く増加率が低い場合よりもハッシュ テーブル操作が高速になりますが、メモリ使用量は多くなります。一般的な選択は、負荷係数が 1/2 を超える場合はテーブル サイズを 2 倍にして、負荷係数を 1/4 から 1/2 の間に抑えることです。^[5]

辞書からキーと値のペアを削除することもできます。ただし、セルを空にするだけでは不十分です。これは、空になったセルより前のハッシュ値を持ち、空になったセルより後の位置に格納されている他のキーの検索に影響します。セルが空になっていると、それらの検索でキーが存在しないという誤った報告が発生します。

代わりに、セルiが空になると、別の空のセルまたはセルiに移動できるキー(つまり、ハッシュ値がiと等しいかそれより前のキー) が見つかるまで、テーブルの次のセルを前方に検索する必要があります。空のセルが見つかった場合、セルi を空にすることは安全であり、削除プロセスは終了します。ただし、検索でセルiに移動できるキーが見つかった場合は、この移動が実行されます。これにより、移動されたキーの後の探索が高速化されますが、同じ占有セル ブロック内の別のセルも空になります。移動可能なキーの検索は、新しい空のセルに対して同様に続けられ、すでに空だったセルに到達して終了します。キーを前のセルに移動するこのプロセスでは、各キーは 1 回だけ検査されます。したがって、プロセス全体を完了する時間は、削除されたキーを含む占有セル ブロックの長さに比例し、他のハッシュ テーブル操作の実行時間と一致します。^[3]

あるいは、キーと値のペアを削除する際に、その値を、削除されたキーを示す特別なフラグ値に置き換えるという遅延削除戦略を使用することもできます。ただし、これらのフラグ値はハッシュ テーブルの負荷要因に寄与します。この戦略では、配列の大部分が削除されたキーで占められるようになったら、配列からフラグ値を消去し、残りのキーと値のペアをすべて再ハッシュする必要があるかもしれません。^{[3] [4]}

線形プロービングは参照の局所性が優れているため、1 回の操作でキャッシュされていないメモリへのアクセスがほとんど必要ありません。このため、低から中程度の負荷係数では非常に高いパフォーマンスが得られます。ただし、他のオープン アドレッシング戦略と比較すると、1 つの衝突が近くの衝突をさらに引き起こす傾向にあるプライマリ クラスタリングが原因で、高負荷係数ではパフォーマンスが急速に低下します。 ^[3]さらに、この方法で優れたパフォーマンスを実現するには、他の衝突解決方式よりも高品質のハッシュ関数が必要です。^[6]入力分布の不均一性を排除できない低品質のハッシュ関数を使用する場合、線形プロービングは、2 番目のハッシュ関数によって間隔が決定されるセルのシーケンスをプローブするダブル ハッシュや、プローブシーケンス内の位置に応じて各ステップのサイズが変化する二次プロービングなどの他のオープン アドレッシング戦略よりも遅くなる可能性があります。^[7]

線形プローブを使用すると、辞書操作は一定の期待時間で実装できます。言い換えれば、ハッシュテーブルの負荷係数が1未満の定数である限り、挿入、削除、検索操作はO(1)で実装できます。 ^[8]

より詳しくは、特定の操作 (検索、挿入、または削除) にかかる時間は、操作が開始される占有セルの連続ブロックの長さに比例します。N 個のセルを持つハッシュ テーブルで、すべての開始セルが等しく発生する可能性がある場合、k 個の占有セルの最大ブロックには、検索の開始位置が含まれる確率が k / N になり、開始位置である場合は常にO ( k )の時間がかかります。したがって、操作の予想時間は、これら 2 つの項の積O ( k ² / N )として計算でき、テーブル内のすべての連続セルの最大ブロックについて合計します。同様に、ブロック長の二乗の合計から、ランダム ハッシュ関数 (ハッシュ テーブルの特定の状態へのランダム開始位置ではなく) の予想時間境界が得られます。これは、存在する可能性のあるすべてのブロック (テーブルの特定の状態で実際に存在するブロックではなく) を合計し、各潜在的なブロックの項に、ブロックが実際に占有されている確率を掛けることによって得られます。つまり、ブロック( i , k )を、インデックスiから始まる長さkの占有セルの最大連続ブロックが存在するイベントと定義すると、操作あたりの予想時間は

${\displaystyle E[T]=O(1)+\sum _{i=1}^{N}\sum _{k=1}^{n}O(k^{2}/N)\operatorname {Pr} [\operatorname {Block} (i,k)].}$

この式は、 Block( i , k )を、より単純な必要条件Full( k )、つまり少なくともk個の要素が長さkのセルのブロック内に存在するハッシュ値を持つイベントに置き換えることで簡略化できます。この置き換えの後、合計内の値はiに依存せず、1/ N係数は外部合計の N項をキャンセルします。これらの簡略化により、境界が次のように導かれます。

${\displaystyle E[T]\leq O(1)+\sum _{k=1}^{n}O(k^{2})\operatorname {Pr} [\operatorname {Full} (k)].}$

しかし、チェルノフ境界の乗法形式により、負荷係数が1から離れると、長さkのブロックに少なくともk個のハッシュ値が含まれる確率はkの関数として指数的に小さくなり、この合計はnに依存しない定数で制限される 。^{[3]チェルノフ境界の代わりに}スターリング近似を使用して同じ分析を実行し、ブロックに正確にk 個のハッシュ値が含まれる確率を推定することもできる。^{[4] [9]}

負荷係数αに関しては、ランダムキーでの検索成功の予想時間はO（1 + 1 /（1− α））であり、検索失敗（または新しいキーの挿入）の予想時間はO（1 + 1 /（1− α）²）である。^[10] 負荷係数が一定の場合、高い確率で、最長のプローブシーケンス（テーブルに格納されているすべてのキーのプローブシーケンスの中で）の長さは対数的である。^[11]

線形プローブハッシュテーブルは、要素が長い連続したランにグループ化されるプライマリクラスタリングと呼ばれる問題を抱えています。 ^{[12] [10]負荷係数}αに関して、特定の要素を含むランの予想される長さは です。^[10]このため、ユニフォームプローブやダブルハッシュなどの他のオープンアドレスハッシュテーブルでは実行時間が であるのに対し、挿入には時間がかかります。^[10]プライマリクラスタリングは、挿入と同様にランの最後まで移動する必要があるため、失敗した検索にも影響します。^[10]線形プローブのいくつかのバリエーションでは、プライマリクラスタリングを軽減する手法を使用して、失敗した検索と挿入の境界をより適切に設定できます。^[13]${\displaystyle \Theta (1+1/(1-\alpha )^{2})}$${\displaystyle \Theta (1+1/(1-\alpha )^{2})}$${\displaystyle \Theta (1+1/(1-\alpha ))}$

線形プロービングは不均一に分布したハッシュ値に特に敏感であるため、^[7]そのような不規則性を生成しない高品質のハッシュ関数と組み合わせることが重要です。

上記の分析では、各キーのハッシュが他のすべてのキーのハッシュとは独立した乱数であると仮定しています。この仮定は、ハッシュのほとんどのアプリケーションでは非現実的です。ただし、オブジェクトを値ではなく ID でハッシュする場合は、ランダムまたは疑似ランダムのハッシュ値を使用できます。たとえば、これはJava コレクション フレームワークの IdentityHashMap クラスによる線形プローブを使用して行われます。^[14] このクラスが各オブジェクトに関連付けるハッシュ値 (identityHashCode) は、オブジェクトの存続期間中は固定されていることが保証されていますが、それ以外は任意です。^{[15] identityHashCode はオブジェクトごとに 1 回だけ作成され、オブジェクトのアドレスまたは値に関連付けられている必要がないため、その作成には、ランダムまたは}疑似乱数ジェネレーターの呼び出しなどの低速の計算が必要になる場合があります。たとえば、Java 8 では、これらの値を作成するためにXorshift疑似乱数ジェネレーターを使用します。^[16]

ハッシュのほとんどのアプリケーションでは、オブジェクトの作成時に一度ではなく、ハッシュされるたびに各値のハッシュ関数を計算する必要があります。このようなアプリケーションでは、乱数や疑似乱数をハッシュ値として使用することはできません。同じ値を持つ異なるオブジェクトが異なるハッシュを持つことになるからです。また、暗号ハッシュ関数(真のランダム関数と計算上区別がつかないように設計されている) は通常、ハッシュ テーブルで使用するには遅すぎます。^[17]代わりに、ハッシュ関数を構築するための他の方法が考案されました。これらの方法はハッシュ関数を迅速に計算し、線形プローブでうまく機能することが証明されています。特に、線形プローブは、小さなランダム シードから初期化され、任意のk組の異なるキーを任意のk組のインデックスにマッピングする可能性が等しいハッシュ関数のクラスであるk独立ハッシュのフレームワークから分析されています。パラメータkはハッシュ関数の品質の尺度と考えることができます。kが大きいほどハッシュ関数の計算にかかる時間は長くなりますが、完全にランダムな関数に似た動作をします。線形プロービングの場合、5独立性があれば操作ごとに一定の予想時間を保証できますが、^[18] 一部の4独立性ハッシュ関数はパフォーマンスが悪く、操作ごとに最大で対数時間がかかります。^[6]

高品質かつ実用的な速度でハッシュ関数を構築するもう 1 つの方法は、タブレーション ハッシュです。この方法では、キーの各バイトを乱数テーブル (バイト位置ごとに異なるテーブル) のインデックスとして使用して、キーのハッシュ値が計算されます。次に、これらのテーブル セルの数値をビット単位の排他的論理和演算で結合します。この方法で構築されたハッシュ関数は 3 独立のみです。ただし、これらのハッシュ関数を使用した線形プローブでは、操作ごとに一定の予想時間がかかります。^{[4] [19]}タブレーション ハッシュと 5 独立ハッシュ関数を生成する標準的な方法は、どちらも固定ビット数のキーに限定されます。文字列やその他の種類の可変長キーを処理するには、キーを中間値にマップするより単純なユニバーサル ハッシュ手法と、中間値をハッシュ テーブル インデックスにマップするより高品質の (5 独立またはタブレーション) ハッシュ関数を作成することができます。 ^{[1] [20]}

実験的な比較で、Richter らは、ハッシュ関数の Multiply-Shift ファミリー ( と定義) が「すべてのハッシュ スキームと統合した場合、最も高速なハッシュ関数であり、つまり、最高のスループットと優れた品質を実現する」のに対し、集計ハッシュは「最低のスループットを実現する」ことを発見しました。^[2] 彼らは、各テーブル検索に複数のサイクルが必要であり、単純な算術演算よりもコストがかかることを指摘しています。彼らはまた、MurmurHashが集計ハッシュよりも優れていることも発見しました。「Mult と Murmur によって提供された結果を研究することにより、集計による のトレードオフは (...) 実際にはそれほど魅力的ではないと考えられます」。 ${\displaystyle h_{z}(x)=(x\cdot z{\bmod {2}}^{w})\div 2^{wd}}$

データのアドレスではなく値でアクセスできる連想配列のアイデアは、1940年代半ばのコンラッド・ツーゼとヴァネヴァー・ブッシュの研究にまで遡りますが、^{[21]ハッシュテーブルは1953年に}ハンス・ピーター・ルーンがIBMのメモで初めて説明されました。ルーンは線形プローブではなく、連鎖という異なる衝突解決方法を使用しました。^[22]

クヌース (1963) は、線形プロービングの初期の歴史を要約している。これは最初のオープン アドレッシング方式であり、もともとオープン アドレッシングと同義であった。クヌースによると、この方式は1954 年にジーン アムダール、エレイン M. マグロウ(旧姓ベーメ)、アーサー サミュエルによってIBM 701コンピュータのアセンブラプログラムで初めて使用された。^[8]線形プロービングに関する最初の公開された記述はピーターソン (1957) によるもので、^[8]ピーターソンもサミュエル、アムダール、ベーメを功績として挙げているが、「このシステムは非常に自然であるため、その前またはそれ以降に他の人によって独立して考え出された可能性が非常に高い」と付け加えている。^[23]この方式に関する別の初期の公開は、1958 年にソ連の研究者アンドレイ エルショフによって行われた。 ^[24]

線形プロービングの最初の理論的分析は、ランダムハッシュ関数を使用した場合、1回の操作あたりに一定の期待時間がかかることを示したもので、クヌースによって行われました。^[8] セジウィックはクヌースの研究を「アルゴリズムの分析における画期的な」ものと呼んでいます。^[10]その後の重要な開発には、実行時間の確率分布のより詳細な分析、 ^{[25] [26]}および線形プロービングが、以前の分析で想定された理想的なランダム関数ではなく、実際に使用可能なハッシュ関数を使用した場合、1回の操作あたり一定時間で実行されることの証明が含まれます。^{[18] [19]}