cs *_*guy 5 hashtable time-complexity
查看哈希表的基本结构。我们知道它会调整 WRT 负载因子或其他一些确定性参数的大小。我知道，如果在插入中达到调整大小限制，我们需要创建一个更大的哈希表并将所有内容插入其中。这是我不明白的事情。
让我们考虑一个哈希表，其中每个桶都包含一个 AVL 平衡 BST。如果我的哈希函数为每个键返回相同的索引，那么我会将所有内容存储在同一个 AVL 树中。我知道这个哈希函数将是一个非常糟糕的函数并且不会被使用，但我在这里做了最坏的情况。因此，一段时间后，我们可以说已经达到了调整大小因子。因此，为了调整大小，我创建了一个新的哈希表，并尝试将所有旧元素插入到以前的表中。由于哈希函数将所有内容映射回一棵 AVL 树，因此我需要将所有 N 个元素插入到同一个 AVL 中。AVL 树上的 N 次插入是 N logN。那么为什么哈希表的最坏插入情况被认为是 O(N) 呢？
下面是向AVL中添加N个元素的证明，三是N logN： 向空AVL树中添加N个元素的运行时间
简而言之：这取决于桶是如何实现的。使用链表，在某些条件下可以在O(n)内完成。对于使用 AVL 树作为存储桶的实现，在最坏的情况下，这确实会导致O(n log n)。为了计算时间复杂度，应该知道桶的实现。
通常，桶不是用 AVL 树或一般的树来实现的，而是用链表来实现的。如果存在对列表条目的引用，则可以在O(1)last中完成追加。否则，我们仍然可以通过添加链表来达到O(1) （在这种情况下，存储桶以相反的插入顺序存储数据）。
使用链表的想法是，使用合理的散列函数的字典应该导致很少的冲突。通常，一个桶有零个或一个元素，有时有两个或三个，但不多。在这种情况下，简单的数据结构可能会更快，因为更简单的数据结构通常每次迭代需要的周期更少。
一些哈希表使用开放寻址，其中存储桶不是分隔的数据结构，但如果该存储桶已被占用，则使用下一个空闲存储桶。在这种情况下，搜索将迭代使用的存储桶，直到找到匹配的条目，或者到达空存储桶。