HashSet Internals

Direct Answer

HashSet is backed by a HashMap internally: each element you add becomes a key, paired with a constant dummy value (PRESENT). So it inherits HashMap's O(1) average performance, allows one null element, and requires correct equals() and hashCode().

Code Example

This snippet shows the behaviour that falls out of the HashMap backing: duplicate rejection, one null, and the equals/hashCode contract for custom objects.

import java.util.*;

public class OrderIdSet {
    public static void main(String[] args) {
        var orderIds = new HashSet<Long>();

        // Behind the scenes: map.put(101L, PRESENT)
        System.out.println(orderIds.add(101L)); // true  (new key)
        System.out.println(orderIds.add(101L)); // false (key already there)

        orderIds.add(null);                     // allowed: one null key
        System.out.println(orderIds.contains(null)); // true

        // Custom object needs correct hashCode/equals
        record Order(Long id, String item) {}   // record auto-generates both
        var orders = new HashSet<Order>();
        orders.add(new Order(101L, "Laptop"));
        System.out.println(orders.contains(new Order(101L, "Laptop"))); // true
    }
}

The record gets correct equals/hashCode for free, so a freshly built equal Order lands in the same bucket and contains() finds it.

Common Mistakes & Pitfalls

• Mutating an element after adding it: change a field that feeds hashCode, and the element's hashCode now points at a different bucket. It still sits in the old one, so the set can no longer find or remove it — the entry is effectively lost.
• Overriding only equals: with hashCode left alone, two equal objects can hash to different buckets, so contains() returns false even though the element is there. Override both together.
• Assuming an iteration order: HashSet makes no order guarantee. Code that expects insertion or sorted order breaks when the internal HashMap resizes — use LinkedHashSet or TreeSet instead.