HashSet vs HashMap: One Is Built Out of the Other

The stock answer to this question is that a HashSet stores values and a HashMap stores key-value pairs. That is true, and it explains nothing — least of all the three follow-ups an interviewer will actually ask, which are all about hashCode.

There is a better answer, and you do not have to take anyone's word for it. Ask the JDK:

javap -p java.util.HashSet

(javap ships with the JDK, so if you have one you can run this now — installing Java 21 covers it if you do not.)

transient java.util.HashMap<E, java.lang.Object> map;
static final java.lang.Object PRESENT;

A HashSet holds a HashMap. Every element you add becomes a key in that map, and every value in it is the same single object, PRESENT, existing only because a map needs a value and a set has none to give.

That is the whole relationship, and everything below follows from it.

What follows, without memorising anything

If a set is a map with dummy values, then:

• set.add(e) is map.put(e, PRESENT)
• set.contains(e) is map.containsKey(e)
• set.remove(e) is map.remove(e)
• a set has no get(), because there is nothing to get — you already have the element if you can ask about it

The cost of a set operation is therefore a map operation plus one method call, which is what the measurements show. A million entries:

HashSet.add   53 ms
HashMap.put   49 ms

Four milliseconds across a million operations. There is no performance reason to prefer one; there is only whether you have a value to store.

Note

This is also why HashSet has six constructors that all look like HashMap's. They are — each one builds the internal map, including the ones taking an initial capacity and load factor, which are properties of the map and meaningless to a set on its own.

The memory you pay for the lookup

Hashing is not free. Measured one collection per JVM with -XX:+UseSerialGC, holding a million Integer elements:

HashSet    54 MB of live heap
ArrayList  21 MB

Two and a half times, for the same data. Each entry is a node object holding the hash, the key, the value and a link to the next node in its bucket, and the bucket array itself has slack in it by design — a full table would collide constantly.

That trade is obviously right when you are asking is this in here? against a large collection, and obviously wrong when you are holding a few dozen things and iterating them. A List with a linear scan beats a HashSet at small sizes and costs a third of the memory. This is heap you share with everything else in the JVM, and a set you built out of habit is a real cost.

A bad hashCode does not fail, it crawls

Here is where the shared machinery starts to matter. Two Java records, identical except that one overrides hashCode to return a constant:

record BadKey(int id)  { @Override public int hashCode() { return 1; } }
record GoodKey(int id) {}

Inserting 50,000 of each into a HashSet:

GoodKey      4 ms
BadKey    5724 ms

Fourteen hundred times slower, and nothing is broken. Every method returns the right answer. equals is still correct, the set still contains what it should, no exception is thrown anywhere.

What happened is that a hash table routes an entry to a bucket by its hash, and every BadKey claims the same bucket. The bucket becomes a list, and every insert scans it to check for duplicates. A structure with O(1) lookup degraded to a linear scan because of a one-line method, and the only symptom is that things got slow.

The hashCode contract does not require distinct objects to have distinct hashes — a constant is a legal implementation. It is legal and catastrophic, which is an unusual combination and the reason this bug survives review.

Common mistake

Writing hashCode by hand, or worse, overriding equals and not hashCode at all. The second one is more common and has the opposite failure: two objects that are equals land in different buckets, so the set happily holds both. Let the compiler generate it — a record does this correctly for free, which is most of the argument for using records as keys.

The rescue almost nobody knows about

Now the same broken key, unchanged except that the record implements Comparable:

record BadCmp(int id) implements Comparable<BadCmp> {
    @Override public int hashCode() { return 1; }
    @Override public int compareTo(BadCmp o) { return Integer.compare(id, o.id); }
}

All three, measured in one warmed run:

proper hashCode                   4 ms
constant hashCode              5724 ms
constant hashCode + Comparable   31 ms

From 5,724 ms to 31 ms, with the hash still constant. The HashMap javadoc explains it: using many keys with the same hashCode slows any hash table, and to ameliorate the impact, when keys are Comparable the class may use comparison order among keys to help break ties. An overloaded bucket stops being a list it has to scan and becomes something it can search.

Tip

This is a safety net, not a fix. It is worth knowing because it costs one interface on a key you control, and because it explains why two systems with equally bad hash functions can perform wildly differently. But a key with a real hashCode was still a hundred and forty times faster than the rescued one.

The bug that makes contains() lie

This is the one worth being able to demonstrate, because it looks impossible.

static class Mutable {
    int v;
    @Override public int hashCode() { return v; }
    @Override public boolean equals(Object o) { return o instanceof Mutable m && m.v == v; }
}

Mutable k = new Mutable(1);
Set<Mutable> set = new HashSet<>();
set.add(k);
k.v = 2;                       // the key's hash just changed

What the run prints:

contains before mutation : true
contains after  mutation : false
set still reports size   : 1
and iterating finds it   : 2

Read those four lines together. The set contains one element. Iterating the set hands you that element. And asking the set whether it contains that very object — the same reference — says no.

Nothing is corrupted. The element was filed in the bucket for hash 1, and contains now computes hash 2 and looks in a different bucket, which is empty. The object is in the collection and unreachable by lookup, and it will stay that way.

This is why a key must be immutable, or at least immutable in the fields its hashCode reads. The same rule reaches further than collections: anything that partitions data by a key's hash depends on that hash not moving, which is exactly why Kafka partitions by key and expects those keys to be stable.

Nulls, and the one each allows

Both are unusually tolerant here, which surprises people who have been told that hash collections reject nulls:

HashSet, null added twice     -> size 1
HashMap, null key put twice   -> size 1, value = the second one

A HashSet holds at most one null element. A HashMap holds at most one null key, and a duplicate put overwrites as it would for any other key.

Worth knowing mostly as a warning about what comes next. Code downstream of a map is often less relaxed — Collectors.toMap throws IllegalStateException on a duplicate key rather than overwriting, which is the opposite of put's behaviour and a surprise in the other direction.

Choosing between them

The only question is whether you need to look something up.

• Membership — "have I seen this id?", "is this word a stopword?" → HashSet
• Association — "what is the user for this id?" → HashMap

If you are building a HashMap whose values you never read, you wanted a set. If you are keeping a HashSet alongside a List to answer both questions, you wanted a LinkedHashMap, which keeps insertion order as well.

And for the interview, three sentences beat the stock answer:

1. A HashSet is implemented as a HashMap with a shared dummy value — add is put, contains is containsKey.
2. Both depend on hashCode being correct and stable; a bad one degrades lookup to a scan, and a changing one makes contains return false for an object the set is holding.
3. So keys should be immutable, and a record is the cheapest way to get that right.