java - TreeMap Collection View 迭代器时间复杂度？

Question

HashMap 的所有 3 个 Collection View 迭代器的时间复杂度(myHashMap.entrySet().iterator().next() 和 myHashMap.keySet( ).iterator().next() 和 myHashMap.values().iterator().next()) 在 javadoc 中有详细记录，它是 O(n +c) 对于所有这 3 个迭代器(n 是映射的数量，c 是哈希表中存储桶的物理数量的容量)。

但是 3 个相应的 TreeMap Collection View 的相应 3 个迭代器呢？官方 javadoc 中什么也没说。它们的复杂性是什么？我确实查看了 SE8 源代码，但我无法从那里做出判断。

Answer 1

尝试根据这些很棒的评论回答这个问题:

1. 与整个迭代过程相比，单个 next() 调用的时间复杂度完全不同。

2. Java 中的 TreeMap 基于红黑树，它是一种平衡的二叉搜索树。

引用https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html

1. 迭代整个 TreeMap 的时间复杂度应该与遍历红黑树相同(对于前序中序或后序遍历)。所以时间复杂度应该是 O(n)，其中 n 是键(或值，或键值映射)计数。

2. 对于单个next 调用，我们可以在O(1) 中完成。如果整个 O(n) 时间复杂度为真，这应该是微不足道的。