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