求含HashMap操作的嵌套循环伪代码的时间复杂度

以下是两层嵌套循环的伪代码，内层循环包含HashMap的containsKey操作：

for loop {
    initialize new hashmap 
    for loop {
        if (hashmap.containsKey(i))
             map.put(something)
    }
}

我原本认为其时间复杂度为O(n²)，但又担心containsKey操作会使其变为O(n³)，希望有人能为我解答。

核心结论 #

这段代码的时间复杂度是O(n²)，不会变成O(n³)，具体分析如下：

HashMap操作的时间特性 #

HashMap的containsKey和put操作，平均情况下时间复杂度是O(1)。这是因为它基于哈希表实现，通过哈希函数直接定位元素所在的桶，只要哈希冲突不严重，就能在常数时间内完成查找和插入。

只有在极端最坏情况（比如所有元素都哈希到同一个桶，且未触发红黑树优化）下，这些操作的时间复杂度才会退化为O(k)（k是当前HashMap中的元素数量），但这种场景在实际开发中几乎不会遇到。

具体拆解 #

假设外层循环执行n次，内层循环每次也执行n次：

• 外层循环每次都会新建一个空HashMap，内层循环的操作只针对当前这个新Map，和其他迭代的Map无关。
• 平均情况下，每次containsKey和put都是O(1)，内层循环总耗时为n*O(1)=O(n)，外层循环执行n次后，总时间就是n*O(n)=O(n²)。

就算退到极端最坏情况：

• 假设内层循环中每次containsKey都返回true，且每次操作都触发哈希冲突，此时每次操作的时间是O(k)（k从1增长到n），内层循环总耗时是O(1+2+...+n)=O(n²)，外层循环n次后总时间是O(n³)。但现代HashMap（比如Java 8及以上版本）会在桶内元素过多时自动把链表转成红黑树，此时操作时间复杂度降为O(log k)，内层循环总耗时变为O(n log n)，外层循环后总时间是O(n² log n)，远达不到O(n³)。而且合理的哈希函数几乎不会让所有元素都哈希到同一个桶，这种极端情况可以忽略。

内容的提问来源于stack exchange，提问作者Rattla