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

Question

看一下哈希表的基本结构，我们知道它会根据负载因子或其他确定性参数进行调整大小。如果在插入过程中达到了调整大小的限制，我们需要创建一个更大的哈希表并将所有内容插入其中。这里有一件事情我不明白。

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

这里是向Avl树添加N个元素的证明是N log N：向空AVL树添加N个元素的运行时间。

- cs guy

---

通常情况下，桶不包含AVL树，而只是一个链表（例如前置）。这个想法是碰撞非常罕见，使用树并不划算。 - Willem Van Onsem

Answer 1

简而言之：这取决于桶的实现方式。使用链表，可以在某些条件下以O(n)的时间复杂度完成操作。对于使用AVL树作为桶的实现，最坏情况下可能会导致O(nlogn)的时间复杂度。为了计算时间复杂度，需要了解桶的实现方式。

通常，桶不是使用AVL树或其他树结构实现的，而是使用链表。如果列表有指向最后一个条目的引用，则可以在O(1)的时间内进行追加操作。否则，通过将链表进行“预置”（在这种情况下，桶按反向插入顺序存储数据），仍然可以达到O(1)。

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

有些哈希表使用开放地址法（open addressing），其中桶不是独立的数据结构，而是在情况下如果桶已经被占用，则使用下一个空闲的桶。在这种情况下，搜索将遍历已使用的桶，直到找到匹配的条目，或者达到空桶。 维基百科关于哈希表的文章讨论了桶如何实现。

- Willem Van Onsem