algorithm - 使用链接填充哈希表的最坏情况和最佳情况时间？

Question

显然最好的情况是 O(n)，但显然最坏的情况是 O(n ² )，我不明白。如果您将哈希表实现为链表数组，我假设最坏的情况是每个哈希都到同一个地方。

所以不是把每个项目仍然是 O(1)，因为将项目添加到链表只是在末端/前面粘贴一个节点的问题？在最坏的情况下，你最终会得到一个空桶数组 + 一个大小为 n 的桶？我在这里想念什么？

Answer 1

我猜他们假设一个实现会在插入之前检查哈希表中是否存在元素（这是典型的，因为哈希表通常在理论上代表集合）。该实现必须在插入新元素之前检查列表的每个元素。