問題タブ [linear-probing]

ハッシュをよりよく理解するために、このStackOverflow の回答を調べていたところ、次のことがわかりました (一定時間でバケット サイズを取得する必要があるという事実に関して)。

線形プローブや二重ハッシュなどを使用する場合、同じ値にハッシュされたすべてのアイテムを見つけることは、値をハッシュする必要があることを意味し、テーブル内の空でないアイテムの「チェーン」を調べて、それらの数を見つけます同じ値にハッシュされます。ただし、同じ値にハッシュされたアイテムの数には線形ではありません。同じ値または衝突する値にハッシュされたアイテムの数には線形です。

これは、「同じ値または衝突する値にハッシュされたアイテムの数に比例する」とはどういう意味ですか? 線形プローブ中にすべての値を調べる必要がある可能性があるため、ハッシュテーブル内のアイテムの総数に線形ではありませんか? 衝突したものを通り抜けなければならない理由がわかりません。

たとえば、ハッシュテーブルで線形プローブ (ステップ サイズ 1) を使用していて、奇数インデックス スロットにマッピングするさまざまなキー (衝突していない、すべてのハッシュが一意の値) を持っている場合、すべてがハッシュされる1,3,5,7,9.....多くのキーを挿入したい2 までなので、すべての偶数インデックス スポットをそれらのキーで埋めます。2 にハッシュされるキーの数を知りたい場合、ハッシュ テーブル全体を調べる必要はありませんか? しかし、奇数のインデックス スロットは衝突していないため、同じ値または衝突する値にハッシュされたアイテムを反復処理しているだけではありません。

キーのインデックスを見つけるために線形プローブを行うハッシュマップを作成しています。キーが既にインデックスにある場合は、新しいインデックスに追加するのではなく、その値を増やしたいと考えています。

たとえば、文字列「five、five、five」の単語数を取得すると、出力は 5 3 ではなく、5 1、5 1、5 1 になります。

私のキーが既にマップにあるかどうかを確認するために get メソッドを使用するのは、私の containsKey メソッドに違いないと思います。以下は私の Hashmap.java クラスです。

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

または、これは、ハッシュ関数 (十分に適切に記述されている場合) がキーをインデックス間で均等に分散し、配列のサイズを常に半分いっぱいになるように変更するという事実によって軽減されますか?