看一下哈希表的基本结构,我们知道它会根据负载因子或其他确定性参数进行调整大小。如果在插入过程中达到了调整大小的限制,我们需要创建一个更大的哈希表并将所有内容插入其中。这里有一件事情我不明白。
让我们考虑一个哈希表,其中每个桶都包含一个AVL平衡BST。如果我的哈希函数为每个键返回相同的索引,那么我将把所有内容存储在同一个AVL树中。我知道这个哈希函数会非常糟糕,不会被使用,但我在这里做一个最坏的情况。所以经过一段时间,假设已经达到了调整大小的因素。因此,为了调整大小,我创建了一个新的哈希表,并尝试将旧表中的每个元素插入其中。由于哈希函数将所有内容映射回一个AVL树中,我需要将所有N个元素插入到同一个AVL中。在AVL树上进行N次插入是N log N。那么为什么哈希表的最坏插入情况被认为是O(N)?
这里是向Avl树添加N个元素的证明是N log N:向空AVL树添加N个元素的运行时间。
让我们考虑一个哈希表,其中每个桶都包含一个AVL平衡BST。如果我的哈希函数为每个键返回相同的索引,那么我将把所有内容存储在同一个AVL树中。我知道这个哈希函数会非常糟糕,不会被使用,但我在这里做一个最坏的情况。所以经过一段时间,假设已经达到了调整大小的因素。因此,为了调整大小,我创建了一个新的哈希表,并尝试将旧表中的每个元素插入其中。由于哈希函数将所有内容映射回一个AVL树中,我需要将所有N个元素插入到同一个AVL中。在AVL树上进行N次插入是N log N。那么为什么哈希表的最坏插入情况被认为是O(N)?
这里是向Avl树添加N个元素的证明是N log N:向空AVL树添加N个元素的运行时间。