CODEWITHSUNDEEP
javadata-structurestime-complexity
Tom
Tom

Reputation: 343

TreeMap values() method and keySet() method time complexity

I was trying to find the time complexity of the methods values() and keySet() implemented in the TreeMap data structure.

Can anyone please tell me what is the time complexity of those methods?

Thank you very much.

Tom

    public class SuperStruct<K,V> 
{
    private Map<K,V> mInternalKeyToValueMap;//all the keys and their values 
    public SuperStruct(){
            mInternalKeyToValueMap = new TreeMap<K,V>();
    }

    public Collection<V> values() {     
            return mInternalKeyToValueMap.values();
        }
    public Collection<K> keySet() {

            return mInternalKeyToValueMap.keySet();
        }
    }

Upvotes: 6

Views: 2202

Answers (2)

biziclop
biziclop

Reputation: 49714

I would expect both to be lazy structures, views backed by the actual map, so creating them would be O(1). And iterating across the entire collection would be O(n) (just as iterating across the map itself would be).

But that's just a reasonable assumption based on the contracts of the keySet() and values() methods (specifically the part that says that the structures returned must reflect changes in the underlying map and vice versa), there's no guarantee that I know of that they will behave this way.

(Though for the record, the Oracle implementation does exactly this, and it would be considerably more complicated to implement it any other way. However that's still not a cast-iron guarantee.)

Upvotes: 2

OldCurmudgeon
OldCurmudgeon

Reputation: 65793

keySet will almost certainly use Collections.newSetFromMap(this) as that is a very efficient method - so O(1) then.

It should be quite simple to create a Collection<V> from the entrySet of the map through a simple adaptor so I would suggest that it would be the same complexity as entrySet which could be either O(1) or O(n) but most likely O(1). Some browsing the source at GrepCode suggests O(1) - it is just creating a new object (if necessary), it is not growing a structure.

Upvotes: 1

Related Questions