CODEWITHSUNDEEP
javacollectionshashmapsethashset
Simo
Simo

Reputation: 2424

What is the subtype of Set that keySet() of HashMap returns?

I tried to check if the subtype of Set that keySet() method of HashMap returns, and check if it is instance of HashSet, but it's not.

Since I have a large set of keys and use keys.contains() heavily, so if it's not type of HashSet, the method can be expensive to use, and it did slow my program a lot.

So do you know what subtype that keySet() method returns? Any programmatic way to check the specific type of a "Set set" instance? I am thinking I might just turn it into a HashSet separately, but that would use more memory.

Edit: So I checked. It's AbstractSet, so what kind of mechanism does AbstractSet use in containsKey()? If it iterates over all elements and find the key, it's super expensive. Do you think creating a separate HashSet for they keys is a good idea?

Final edit: OK, checked the source code thoroughly. It does use hash mechanism to check the existence of a key. For those who wonder why I asked: my program takes forever to run :(. Trying to tune it up now.

Upvotes: 0

Views: 91

Answers (2)

arshajii
arshajii

Reputation: 129537

It's a private inner class defined within HashMap called KeySet, which you can see if you take a look.

The contains method of KeySet simply calls the map's containsKey (which is O(1) and not at all expensive):

896    public boolean contains(Object o) {
897        return containsKey(o);
898    }

Upvotes: 2

assylias
assylias

Reputation: 328765

HashMap#keySet javadoc explains that the set is a view on the map's keys. Since this map implementation guarantees constant time performance for get operations, you can safely expect the Set returned by keySet to provide similar performance guarantees.

If you don't trust common sense you can always call map.containsKey directly.

Upvotes: 2

Related Questions