HashSet contains: Leveraging HashMap containsKey
What you'll learn: How HashSet achieves O(1) lookup performance by delegating its contains() method directly to HashMap's containsKey().
The Delegation Pattern in Action
When you call contains() on a HashSet, you're not invoking some special set-specific logic. Instead, HashSet simply forwards the request to its internal HashMap and asks whether that element exists as a key.
Remember, HashSet is essentially a wrapper around HashMap where your elements are stored as keys (and each key has that dummy PRESENT value). This means checking if a set contains an element is identical to checking if the map contains that key.
How It Works
The HashSet.contains(Object o) method implementation looks something like this conceptually:
public boolean contains(Object o) {
return map.containsKey(o);
}
That's it! The HashMap's containsKey() method:
- Computes the hash code of the object
- Uses that hash to find the correct bucket
- Checks if the key exists in that bucket
Because HashMap uses hashing with proper bucket distribution, this lookup happens in O(1) average time—constant time, regardless of how many elements are in the set.
Why This Matters
This design means HashSet inherits all the performance characteristics of HashMap's key lookup mechanism. You get fast membership testing "for free" simply by reusing the already-optimized hash table implementation.
Key Takeaway: HashSet.contains() is just a thin wrapper around HashMap.containsKey(), giving you O(1) average-case lookup by leveraging the internal hash table's efficient key-checking mechanism.