skip to content

How does a Java HashSet work internally: what does its backing HashMap store, what is PRESENT for, and what does add() return?

level: middleimportance: must knowfreq 68%

answer

  1. one field does the work
  2. elements live where keys live
  3. a single shared dummy value
  4. what does put hand back?
  5. add compares that result with null

basics

~20 s

HashSet delegates to one HashMap field: elements are its keys and every value is one shared PRESENT object. add() calls put and returns true only when put finds no earlier mapping, so a duplicate leaves the set unchanged.

solid answer

~40 s

At JDK 27 a `HashSet` holds one instance field, a package-private transient `HashMap<E,Object>` named `map`, and each element is a key in it. Every value is `PRESENT`, a single package-private `static final Object`, so there is one dummy object in total and each entry only refers to it. `add(e)` is `return map.put(e, PRESENT)==null;`: `put` returns the key's earlier value or `null`, and since every `put` in the class passes `PRESENT`, `null` can only mean the element is new. On a duplicate the map keeps the existing key object, rewrites the value with the same `PRESENT`, and `add` returns `false`. `remove(o)` is `map.remove(o)==PRESENT`, while `contains`, `size` and `iterator` go to the map's `containsKey`, `size` and `keySet().iterator()`. `LinkedHashSet` reuses all of this through a package-private constructor that puts a `LinkedHashMap` in `map`.

code

java · 19 lines
java
import java.util.HashSet;
import java.util.Set;

public class HashSetAddDemo {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        String first = new String("order-17");
        String second = new String("order-17");

        System.out.println(set.add(first));                  // true: put found no earlier mapping
        System.out.println(set.add(second));                 // false: put returned PRESENT
        System.out.println(set.size());                      // 1
        System.out.println(set.iterator().next() == first);  // true: the map kept the first key object

        System.out.println(set.add(null));                   // true: null is a key like any other
        System.out.println(set.add(null));                   // false: its value is PRESENT, not null
        System.out.println(set.remove("absent"));            // false: map.remove returned null
    }
}

go deeper

for a junior

Recall that a HashSet keeps its elements as the keys of a HashMap it holds, and that add returns true only when the element was not already there.

for a middle

Explain the chain: add calls put with the shared dummy value, put returns the earlier value or null, and add turns that into a boolean. Cover the duplicate case, including which key object survives.

for a senior

Reason from the delegation in production terms: each element costs a full map entry, so a set is no lighter per element than a map, and iteration order, fail-fast iterators and tuning all come from the map.

for a principal

Frame it as a design tradeoff: reusing one tested table by composition means less code to maintain, at the price of an unused value slot in every entry. Say when that price deserves measuring instead of assuming.

Someone reading `HashSet.java` for the first time usually stops at two lines: a dummy object named `PRESENT`, and an `add` method that ends in `==null`. Both make sense once you see how little of the class is a set in its own right. Everything below describes **JDK 27**. ## What a HashSet actually holds A **`HashMap`** maps **keys** to **values**: each key appears once, and looking one up returns its value. `HashSet` uses one as its storage rather than building a table of its own. - **One instance field:** `transient HashMap<E,Object> map`. It has no access modifier, so it is **package-private**, visible only inside `java.util`. - **Elements are keys.** A set's uniqueness is the map's rule that a key appears once. - **Values are filler.** A map entry needs a value, so each one gets `PRESENT`, declared as `static final Object PRESENT = new Object()`. It is package-private too, and `LinkedHashSet` passes it in `addFirst` and `addLast`. - **One object, many references.** `static` means the field belongs to the class, so there is one `PRESENT` however many sets and elements exist. The apparent dummy object per entry is really one reference per entry to that single object. ## What add() does, step by step ```java public boolean add(E e) { return map.put(e, PRESENT)==null; } ``` 1. `add` calls `HashMap.put` with the element as the key and `PRESENT` as the value. There is no `contains` call first: `put` does the lookup and the write in one call. 2. The map looks for an existing key equal to the element, judging equality by the element's `hashCode` and `equals`. Hashing and buckets are the map's machinery, and `HashSet` contains none of it. 3. **New key:** the map creates an entry and `put` returns `null`, so `add` returns `true`. 4. **Existing key:** the map leaves the key object in place, overwrites the value with the argument and returns the old value. That value is `PRESENT`, so `add` returns `false`. The overwrite in step 4 writes the same reference over itself, so nothing observable changes. Because the old key object stays, adding a second, equal object does not swap it in: the set keeps the object it received first. ## Why the filler is an object and not null `HashMap.put` returns the previous value, or `null` when the key had no mapping, and its documentation warns that `null` can also mean the key was mapped to `null`. If every value were `null`, `put` would return `null` for new keys and duplicates alike, and `add` would report `true` every time. `remove` would have the same problem. Every `put` in `HashSet` and `LinkedHashSet` passes `PRESENT`, so here `null` has one meaning. The source comment on the field says only that it is a dummy value, so this reasoning is what the code needs, not a rationale the source states. ## How the other methods delegate | Method | Body at JDK 27 | What it reports | |---|---|---| | `add(e)` | `map.put(e, PRESENT)==null` | `true` if there was no earlier mapping | | `remove(o)` | `map.remove(o)==PRESENT` | `true` if an entry was removed | | `contains(o)` | `map.containsKey(o)` | `true` if the key is present | | `size()` | `map.size()` | the number of keys | | `iterator()` | `map.keySet().iterator()` | walks the keys | `HashMap.remove` returns the removed entry's value, or `null` when nothing matched, so comparing the result with `PRESENT` answers whether anything was removed. ## What this design explains - **Duplicates change nothing.** The size stays the same, the stored object stays the same and `add` returns `false`. - **One null element is allowed.** The map accepts a `null` key, and a key appears once. Its value is still `PRESENT`, so a second `add(null)` returns `false` like any other duplicate. - **No ordering guarantee.** Iteration walks the map's keys in whatever order the map holds them. - **No memory saving per element.** Each element costs a full map entry, including a value slot that only points at `PRESENT`, so a set is no lighter per element than a map with the same keys. - **Tuning passes straight through.** The constructor arguments for initial capacity and load factor go directly to the map. ## LinkedHashSet: the same code with another map `LinkedHashSet` extends `HashSet`, declares no instance field of its own and inherits `add`, `remove` and `contains`. Its constructors call a package-private constructor, `HashSet(int, float, boolean dummy)`, whose body is `map = new LinkedHashMap<>(initialCapacity, loadFactor)`. The `boolean` is ignored and exists only to give that constructor a different signature. `LinkedHashMap` extends `HashMap`, so it fits the same field, and it supplies the insertion order while `add` runs the identical line. Calling `add` with an element already present returns `false` and does not move it; only `addFirst` and `addLast`, added in Java 21, relocate an existing element.

  • Why does HashSet use a dummy object instead of storing null as every value in its map?
    `HashMap.put` returns the key's previous value, or `null` when there was none. With `null` as every value, `put` would return `null` for a duplicate too, so `add` would report `true` every time. A non-null `PRESENT` gives `null` one meaning. The source comment calls it only a dummy value, so this is what the code needs, not a stated rationale.
  • Can a HashSet hold a null element, and what does adding it twice return?
    Yes, one. The null element is a key, and `HashMap` accepts one null key. Its value is still `PRESENT`, not `null`, so the first `add(null)` returns `true` because `put` found no mapping, and the second returns `false` because `put` returned `PRESENT`. Null as an element and null as `put`'s result are different things.
  • Does adding an element already in a HashSet during a for-each over that set throw ConcurrentModificationException?
    Not at JDK 27. `HashMap.putVal` returns on the existing-key path before it increments `modCount`, so the iterator sees no structural change. Adding a new element does count, and the following `next()` normally throws. The Javadoc calls fail-fast behaviour best effort, so build on neither outcome.
  • Why is HashSet's map field transient, and what do the values become after deserialization?
    `transient` makes default serialization skip the field. `HashSet.writeObject` writes capacity, load factor, size and then each element, with no values. `readObject` builds a new map and calls `map.put(e, PRESENT)` per element, so the values are the receiving JVM's own static `PRESENT`, and `remove`'s `==PRESENT` check still holds.

Picture a two-column ledger used as a plain list of names. The form insists on something in column two, so every row gets the same rubber stamp. There is one stamp, not one per row, and a row already stamped tells you the name was there.

  • HashSet allocates a separate new dummy object for every element it stores.
  • HashSet has its own hash table, written independently of HashMap.
  • Adding a duplicate replaces the stored object with the new equal one.
  • add() calls contains first and then inserts, so it always does two lookups.
  • HashSet could store null as every value and add() would still detect duplicates.
  • At JDK 27, HashSet's map and PRESENT fields are declared private.

HashSet
Java 1.2

Assumes JDK 27; the package-private visibility of map and PRESENT is as that release's source declares it.

context