では、線形プローブを使用するハッシュマップがあるとします。
最初に値 X をキー X で挿入します。これは、たとえば、5 番目の場所にハッシュされます。
次に、キー Y を持つ値 Y を挿入します。これも 5 にハッシュされます。場所は 6 になります。
次に、キー Z を持つ値 Z を挿入します。これも 5 にハッシュされます。場所は 7 になります。
次にYを削除すると、メモリは「X、null、Z」のようになります
次に、キー Z で値を挿入しようとすると、5 がチェックされ、それが取得されたことを確認し、6 がチェックされ、そこに空として挿入されます。ただし、キー Z を持つエントリが既に存在するため、キー Z を持つエントリが 2 つあり、不変条件に反します。
したがって、値自体が見つかるまでマップ全体を調べる必要はありません。見つからない場合は、最初のヌル スペースに挿入できます。したがって、特定のキーへの初回挿入はすべて O(N) ではないでしょうか?
いいえ。
あなたが直面している問題は、あなたが誤って行った削除が原因です。
実際、リニア プローブを使用してテーブルから削除するのはやや困難です。リニア プローブを使用して構築された多くのテーブルは、削除をまったくサポートしていません。
つまり、少なくとも理論的には、ハッシュ テーブルに対するほぼすべての操作は、最悪の場合 (挿入、削除、ルックアップなど) は線形になる可能性があります。作成したハッシュ関数がどれほど巧妙であるかに関係なく、ハッシュできる入力は無限にあります。特定の出力に。十分に不幸な入力の選択 (または単に貧弱なハッシュ関数) を使用すると、任意のパーセンテージですべて同じハッシュ コードを生成することになります。
編集:線形プローブで削除をサポートすることを主張する場合、基本的な考え方は、エントリの各「チェーン」が連続したままであることを確認する必要があるということです。したがって、キーをハッシュしてから、そこから次の空のバケットまでずっと歩きます。これらの各エントリのハッシュ コードを確認し、穴の前の位置にハッシュされた最後の連続した項目で「穴」を埋めます。これにより、作成中の穴の前の位置にハッシュされた最後のアイテムで埋めなければならない別の穴が作成される可能性があります (再帰的に)。