ハッシュをよりよく理解するために、このStackOverflow の回答を調べていたところ、次のことがわかりました (一定時間でバケット サイズを取得する必要があるという事実に関して)。
線形プローブや二重ハッシュなどを使用する場合、同じ値にハッシュされたすべてのアイテムを見つけることは、値をハッシュする必要があることを意味し、テーブル内の空でないアイテムの「チェーン」を調べて、それらの数を見つけます同じ値にハッシュされます。ただし、同じ値にハッシュされたアイテムの数には線形ではありません。同じ値または衝突する値にハッシュされたアイテムの数には線形です。
これは、「同じ値または衝突する値にハッシュされたアイテムの数に比例する」とはどういう意味ですか? 線形プローブ中にすべての値を調べる必要がある可能性があるため、ハッシュテーブル内のアイテムの総数に線形ではありませんか? 衝突したものを通り抜けなければならない理由がわかりません。
たとえば、ハッシュテーブルで線形プローブ (ステップ サイズ 1) を使用していて、奇数インデックス スロットにマッピングするさまざまなキー (衝突していない、すべてのハッシュが一意の値) を持っている場合、すべてがハッシュされる1,3,5,7,9.....多くのキーを挿入したい2 までなので、すべての偶数インデックス スポットをそれらのキーで埋めます。2 にハッシュされるキーの数を知りたい場合、ハッシュ テーブル全体を調べる必要はありませんか? しかし、奇数のインデックス スロットは衝突していないため、同じ値または衝突する値にハッシュされたアイテムを反復処理しているだけではありません。