time-complexity - 为什么哈希表插入时间复杂度最坏的情况不是 N log N

Question

查看哈希表的基本结构。我们知道它会调整 WRT 负载因子或其他一些确定性参数的大小。我知道如果在插入中达到调整大小限制，我们需要创建一个更大的哈希表并在那里插入所有内容。这是我没有得到的东西。

让我们考虑一个哈希表，其中每个桶都包含一个 AVL 平衡的 BST。如果我的哈希函数为每个键返回相同的索引，那么我会将所有内容存储在同一个 AVL 树中。我知道这个散列函数将是一个非常糟糕的函数并且不会被使用，但我在这里做的是最坏的情况。因此，经过一段时间后，我们可以说已达到调整大小因子。所以为了调整大小，我创建了一个新的哈希表，并尝试在我之前的表中插入每个旧元素。由于哈希函数将所有内容映射回一个 AVL 树，因此我需要将所有 N 个元素插入同一个 AVL。 AVL 树上的 N 次插入是 N logN。那么为什么哈希表插入的最坏情况被认为是 O(N) 呢？

下面是将 N 个元素加入 Avl 三的证明是 N logN:
Running time of adding N elements into an empty AVL tree

Answer 1

总之 :这取决于存储桶的实现方式。使用链表，在特定条件下可以在 O(n) 中完成。对于将 AVL 树作为桶的实现，这确实会导致 O(n log n)。为了计算时间复杂度，应该知道桶的实现。

通常，bucket 不是用 AVL 树或一般的树实现的，而是用链表实现的。如果有引用last列表的条目，追加可以在 O(1) 中完成。否则我们仍然可以通过添加链表来达到 O(1)(在这种情况下，桶以相反的插入顺序存储数据)。

使用链表的想法是，使用合理散列函数的字典应该导致很少的冲突。通常一个桶有零个或一个元素，有时有两个或三个，但不多。在这种情况下，简单的数据结构会更快，因为更简单的数据结构通常每次迭代需要更少的周期。

一些哈希表使用开放寻址，其中桶不是分离的数据结构，但如果桶已经被占用，则使用下一个空闲桶。在这种情况下，搜索将因此迭代使用过的存储桶，直到找到匹配的条目，或者到达空存储桶。

Wikipedia article on Hash tables讨论如何实现存储桶。