Course contentsShow
← Java
Lesson 1055 of 2,87025. Set ImplementationsFree lesson

Memory Overhead: HashMap Values in HashSet

Understanding the memory cost of storing dummy values for every element in the backing HashMap.

Memory Overhead: HashMap Values in HashSet

What You'll Learn

You'll understand why HashSet consumes more memory than you might expect due to its internal use of dummy values in the backing HashMap.

The Hidden Cost of Convenience

Remember that HashSet is implemented as a wrapper around HashMap, where your elements become keys and every key needs a corresponding value. Since HashSet doesn't actually need those values—it only cares about the keys—it stores the same dummy PRESENT object for every single entry.

This design creates memory overhead:

The Per-Entry Cost

For each element you add to a HashSet, the backing HashMap stores:

  1. Your actual element (the key)
  2. A reference to the PRESENT dummy object (the value)
  3. Internal HashMap.Entry overhead (hash code cache, next pointer for collision chains)

Even though all entries share the same PRESENT object reference, you still pay for storing that reference in every HashMap entry. It's like paying for a parking spot that holds only an "occupied" sign instead of useful cargo.

Comparing to a Hypothetical Set Implementation

If Java had a dedicated hash-based Set implementation that didn't use HashMap internally, it could theoretically:

  • Store just the element and hash metadata
  • Skip the value reference field entirely
  • Save approximately one pointer's worth of memory per element (4-8 bytes depending on JVM and heap size)

For a HashSet with millions of elements, this overhead adds up to megabytes of wasted memory—though in practice, the convenience and code reuse usually outweigh this cost.

Key Takeaway:
HashSet's reliance on HashMap means every element carries a dummy value reference, adding memory overhead compared to a theoretical pure-set implementation—a trade-off for code simplicity and consistency.