リニア プローブ (ハッシュ テーブル) について、直感的に理解できないことが 1 つあります。結果をハッシュする key1 を配列インデックス 1 に配置すると、次に key2 -> 配列インデックス 2 を配置します。次に、key3 -> 再び配列インデックス 1 を配置すると、これは配列インデックス 3 に移動します。次に、key3 を検索するときに移動する必要があります私のものとまったく同じハッシュを持たないキーを含むインデックスを介して。これは無駄ではありませんか？シーケンスが非常に大きく、多くのキーが含まれている場合 (たとえば、20 個の要素があり、null の場合、配列インデックスが 0 から 20 になるキーについては、すべてのインデックスを調べなければなりませんが、それらは私のものと同じハッシュを持っていません)これは別の連鎖で排除できます)。
または、これは、ハッシュ関数 (十分に適切に記述されている場合) がキーをインデックス間で均等に分散し、配列のサイズを常に半分いっぱいになるように変更するという事実によって軽減されますか?