algorithm - チェーンを使用してハッシュ テーブルにデータを入力するための最悪の場合と最良の場合の時間は?

Question

明らかに最良のケースは O(n) ですが、明らかに最悪のケースは O(n ² ) ですが、これはわかりません。ハッシュ テーブルをリンクされたリストの配列として実装する場合、最悪のケースはすべてのハッシュが同じ場所に移動することだと思います。

リンクされたリストにアイテムを追加することは、エンド/フロントにノードを貼り付けるだけの問題であるため、各アイテムをまだO(1)に配置していませんか? 最悪の場合、空のバケットの配列 + サイズ n のバケット 1 つになるのでしょうか? ここで何が欠けていますか？

Answer 1

彼らは、挿入する前にハッシュテーブルに要素が存在するかどうかをチェックする実装を想定していると思います（ハッシュテーブルは通常、理論的にセットを表すため、これは一般的です）。その実装では、新しい要素を挿入する前に、リストの各要素をチェックする必要があります。