私はハッシュテーブルの概念にかなり慣れていません。さまざまな種類のハッシュテーブルのルックアップと挿入の手法について読んでいます。
線形プロービング、連鎖、および2次プロービングの時間計算量の違いは何ですか？
私は主にハッシュテーブルのノードの挿入、削除、検索に興味があります。では、プロセス（挿入/検索/削除プロセス）ごとのシステム時間とプロセス番号をグラフ化すると、グラフはどのように異なりますか？
私は次のように推測しています：-二次プロービングは検索の最悪の場合のO（nlogn）またはO（logn）になります-線形プロービングは検索の最悪の場合のO（n）になります-わからないが、O（n ^ 2 ）連鎖用
誰かがこれを確認できますか？ありがとう！
さまざまな理由から、これらのさまざまなハッシュスキームをすべて正確に分析することは実際には驚くほど困難です。まず、ハッシュ関数について非常に強い仮定をしない限り、ハッシュ関数のタイプが異なればパフォーマンスも異なる可能性があるため、これらのハッシュスキームの動作を正確に分析することは困難です。第2に、プロセッサキャッシュとの相互作用は、理論的にわずかに悪い特定のタイプのハッシュテーブルが、アクセスパターンが優れているため、理論的にわずかに優れているハッシュテーブルよりも実際に優れている可能性があることを意味します。
ハッシュ関数が真にランダムな関数のように見え、ハッシュテーブルの負荷率を最大で一定に保つ場合、これらのハッシュスキームはすべてO（1）ルックアップ時間を想定しています。言い換えると、各スキームは、予想どおり、特定の要素を見つけるために一定数のルックアップを実行するだけで済みます。
理論的には、線形プロービングは、ハッシュ関数が強力な理論的特性を持たない限り、要素が互いに近くにクラスター化する傾向があるため、2次ハッシュおよび連鎖ハッシュよりも少し劣ります。ただし、実際には、参照の局所性のために非常に高速になる可能性があります。すべてのルックアップは互いに近くなる傾向があるため、発生するキャッシュミスは少なくなります。二次プロービングは衝突が少なくなりますが、局所性はそれほど良くありません。連鎖ハッシュは衝突が非常に少ない傾向がありますが、連鎖要素が連続して格納されないことが多いため、参照の局所性が低くなる傾向があります。
最悪の場合、これらのデータ構造はすべて、ルックアップを実行するのにO（n）時間かかる可能性があります。これが発生する可能性は非常に低いです。線形プロービングでは、これにはすべての要素をギャップなしで継続的に保存する必要があり、最初の要素の1つを検索する必要があります。二次ハッシュを使用すると、この動作を実現するために、非常に奇妙に見えるバケットのセットが必要になります。連鎖ハッシュを使用すると、ハッシュ関数は、絶対的な最悪の場合の動作を取得するために、すべての要素を同じバケットにダンプする必要があります。これらすべてが指数関数的に発生する可能性は低いです。
つまり、これらのデータ構造のいずれかを選択した場合、非常に悪いハッシュ関数がない限り、深刻な火傷を負う可能性はほとんどありません。チェーンハッシュはパフォーマンスが高く、最悪の場合の動作に頻繁に影響しないため、デフォルトとしてチェーンハッシュを使用することをお勧めします。優れたハッシュ関数があることがわかっている場合、または小さなハッシュテーブルがある場合は、線形プロービングが適切なオプションになる可能性があります。
お役に立てれば！