Java HashSet

›Short versionOpen if you only have a minute.

HashSet is a set on a hash table. add, remove, and contains are average constant time.
If a.equals(b), then a.hashCode() must equal b.hashCode(). Unequal objects may still collide.
The hash code picks a bucket. equals decides among the objects in that bucket.
Override equals and hashCode together, from the same fields. Records do this for you.
Changing those fields after insertion hides the element. Later contains and remove miss it.
Iteration order is unspecified. One null element is allowed.

A is the default set: distinct elements, fast membership, no order. It works only while the holds for every element you put in.

chooses a . finishes the test. Skip either half and the set stores duplicates or loses elements you know are there.

What a broken contract looks like

Suppose two Ids compare equal because their value strings match, and hashCode stays the identity hash from Object. The second Id can land in another bucket. add returns true. The set now holds two objects that equals says are the same, which is exactly what a set is for refusing.

The other failure is a . You add an Id, then change its value. The node does not move. The lookup hashes the new value and searches an empty bucket. The element is still in the set if you iterate, and invisible if you ask for it.

String, the boxed numbers, and records already follow the contract. Custom classes need both methods, or they need to stay out of hash sets.

ℹ️ Ready to modify the HashSet!

Apple

Banana

Cherry

A key the set can find again

IdSet.java

final class Id {
    private final String value;
    Id(String value) { this.value = value; }

    @Override public boolean equals(Object obj) {
        return obj instanceof Id other && value.equals(other.value);
    }

    @Override public int hashCode() {
        return value.hashCode();
    }
}

Set<Id> ids = new HashSet<>();
ids.add(new Id("u-1"));
ids.contains(new Id("u-1")); // true, average O(1)

equals is correct, and hashCode returns 42 for every Id. Does contains still return the right answer? What happened to the cost?

contains still finds the element, because equal objects share the code 42 and equals runs inside that single bucket. Every element shares the bucket, so the expected constant time has become a linear scan.