TreeMap collection views iterators time-complexity?

Question

Time-complexity of all 3 collection view iterators for HashMap (myHashMap.entrySet().iterator().next() and myHashMap.keySet().iterator().next() and myHashMap.values().iterator().next()) is well-documented in javadoc, it is O(n+c) for all those 3 iterators (n is number of mappings, c is capacity that is physical number of buckets in hashtable).

But what about respective 3 iterators of 3 respective TreeMap collection views? Nothing is said in official javadoc. What are their complexities? I did look in SE8 source code but I cannot judge from there.

Severn

Federico Peralta Schaffner comment to this SO question #53667820 implies log(n) for all three TreeMap collection view iterators - as an opinion – Severn

@Holger I think he is talking about one next() call. – Hoi

@Hoi exactly. And that’s not what the Javadoc is talking about. – Reamy

For a TreeMap, forming the collection view will be O(n) and iterating over each element will be in total O(n). O(2n) will turn out to be O(n) in essence. Correct? (Considering Full iteration) – Maeve

@Ankur Creating the collection view is just creating object wrappers and setting up some links, so it's O(1). Then, as it's a view (i.e. not a copy of the actual entries), fetching each entry via iterator.next() might have some hidden costs. In the case of TreeMap, I think it would need to reach the lowest entry, i.e. the leftmost leaf of the tree, which would be O(logN) because the tree is balanced. Then, for the rest of the entries, it would be just a red-black tree traversal, which would yield O(1) for each fetched entry, totalling logN + N - 1 ~ O(N) for the whole traversal. – Leavening

Well I suspected the same about forming collection view, but not so sure about going to the left most leaf node first. That shouldn’t be required I think. – Maeve

Answer 1

Try to answer this based on these great comments:

1. One single next() call has a totally different time complexity compared with the whole iterating process.

2. TreeMap in Java is based on Red-Black Tree, which is a balanced binary search tree.

Refer to https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html

3. Iterating a whole TreeMap should have the same time complexity as traversing the Red-Balck Tree(For pre-order in-order or post-order traveral). So time complexity should be O(n) where n is the key(or value, or key-value mapping) count.

4. For a single next call, we can do it in O(1). If a whole O(n) time complexity is true, this should be trivial.

Hoi

There is no next() in TreeMap. Is there a linked tree map in which we can iterate to next element in O(1)? – Sima

@NathanB By saying next() , I mean iterator.next() on entrySet(), keySet(), and values(). There should be no linked tree map, we only have LinkedHashMap. – Hoi

The problem with LinkedHashMap is that it is not sorted by the key. – Sima

@NathanB That is true. Are you asking that why the time complexity is O(1) for the iterator.next() function? – Hoi