TreeMap集合视图迭代器的时间复杂性

Question

HashMap的所有3个集合视图迭代器(myHashMap.entrySet().iterator().next()、myHashMap.keySet().iterator().next()和myHashMap.values().iterator().next()(的时间复杂性在javadoc中有很好的记录，所有这3个迭代器的时间复杂性都是O(n+c((n是映射的数量，c是容量，是哈希表中存储桶的物理数量(。

但是，3个TreeMap集合视图的3个迭代器又如何呢？官方javadoc中没有任何内容。它们的复杂性是什么？我确实看过SE8的源代码，但我不能从中判断。

Answer 1

试着根据以下伟大的评论来回答这个问题：

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

2. Java中的TreeMap是基于红黑树的，这是一个平衡的二进制搜索树。

请参阅https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html

3. 迭代整个TreeMap的时间复杂性应与遍历Red Balck Tree的时间复杂性相同(对于订单中的预购或订单后的旅行(。所以时间复杂度应该是O(n)，其中n是密钥(或值，或键值映射(计数。

4. 对于单个next调用，我们可以在O(1)中执行。如果一个完整的O(n)时间复杂性是真的，那么这应该是微不足道的。