HashSet Internal Working

A HashSet doesn't have its own hashing code. Inside, every HashSet holds a HashMap, and each element of the set is stored as a key of that map. Since map keys are unique, set elements are unique too. The value stored with each key is the same shared dummy object, called PRESENT. In this lesson, you will learn how add, contains and remove are passed on to the map, and you will build a small set of your own the same way.

How HashSet Uses a HashMap

The JDK source of HashSet boils down to this:

public class HashSet<E> {
    private transient HashMap<E, Object> map = new HashMap<>();
    private static final Object PRESENT = new Object();
 
    public boolean add(E e)         { return map.put(e, PRESENT) == null; }
    public boolean contains(Object o) { return map.containsKey(o); }
    public boolean remove(Object o) { return map.remove(o) == PRESENT; }
    public int size()               { return map.size(); }
}

• add(e) calls map.put(e, PRESENT). For a new key, put returns null, so add returns true. For an existing key, put returns the old value (PRESENT), so add returns false.
• contains(o) is just map.containsKey(o).
• remove(o) removes the key from the map.
• Iteration walks the map's keySet().

All the hashing, buckets, collisions and resizing described in "HashMap Internal Working" apply to HashSet unchanged.

Example: Building a Set on a HashMap

Let's see an example that rebuilds the idea in a few lines.

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
 
public class MiniSet<E> {
    private final Map<E, Object> map = new HashMap<>();
    private static final Object PRESENT = new Object();
 
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
 
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
 
    public Set<E> elements() {
        return map.keySet();
    }
 
    public static void main(String[] args) {
        MiniSet<String> set = new MiniSet<>();
        System.out.println(set.add("Navika"));
        System.out.println(set.add("Srihitha"));
        System.out.println(set.add("Navika"));
        System.out.println("contains Srihitha: " + set.contains("Srihitha"));
        System.out.println("size: " + set.elements().size());
    }
}

true
true
false
contains Srihitha: true
size: 2

Explanation: The first add("Navika") stores a new key, so put returns null and add returns true. The second finds the key already present, so put returns PRESENT and add returns false. That's the whole trick behind a HashSet.

The Other Sets Work the Same Way

Common Mistakes

Thinking HashSet stores elements in a list and searches it. It uses hashing, so contains is O(1) on average.

Expecting HashSet to call compareTo. It uses hashCode and equals; only TreeSet compares.

Interview Corner

Practice

1. Easy: Add a remove(Object o) method and a size() method to MiniSet.
2. Harder: Build a MiniTreeSet<E> backed by a TreeMap<E, Object> and check that it prints its elements sorted.

Key Takeaways