TreeMap集合查看迭代器的时间复杂度？

Question

HashMap(myHashMap.entrySet().iterator().next()和myHashMap.keySet().iterator().next()和myHashMap.values().iterator().next())的所有3个集合视图迭代器的时间复杂度在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应该与遍历红黑树具有相同的时间复杂度（对于前序中序或后序遍历）。所以时间复杂度应该是键（或值，或键值映射）计数O(n)。n

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