hashtable - ハッシュテーブル内のハッシュテーブルの検索の複雑さ?

Question

サイズ m のハッシュテーブルがあり、各バケットにサイズ p のハッシュテーブルを格納するとします。最悪のケース/平均的なケースの検索の複雑さは?

ハッシュ関数の計算は依然としてアトミックであるため、唯一の最悪のシナリオは、値がサイズ p のハッシュテーブルのリンク リストの最後にある場合、O(n)?

このシナリオの平均的なケースを計算する方法がわかりません。ポインタをいただければ幸いです。

Answer 1

はい、リンクされたリストに追加することで競合が解決された場合、最悪の場合でも線形です。n第 1 レベルと第 2 レベルにスロットを持つ 2 レベルのハッシュテーブルは、スロットpを持つ単一レベルのハッシュテーブルと同じですnp。追加するすべての要素が同じ第 2 レベルのスロットに配置されたり、すべてが同じリンク リストに追加されたりする可能性があります。この観察に基づくと、平均ケースの複雑さはnp、衝突を解決するためのリンクされたリスト。