HashSet

Hash table backing mechanics, the equals and hashCode contract, and collision treeification

HashSet<E> is the default set implementation. It is backed internally by a HashMap<E, Object>, where each set element is stored as a map key paired with a static dummy PRESENT object.

The `equals()` and `hashCode()` Contract

HashSet relies strictly on hashing to locate bucket indices. If a custom object does not override both equals() and hashCode(), lookups silently fail:

ConsistentStudent.java

class Student {
    int id;
    String name;

    Student(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Student other)) return false;
        return id == other.id && Objects.equals(name, other.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

The Hashing Invariant: If o1.equals(o2) == true, then o1.hashCode() == o2.hashCode() must always be true. If unequal hash codes are returned, HashSet searches the wrong bucket index and fails to detect duplicates.

Complexity & Null Handling

Operation	Time Complexity	Notes
`add(e)`	`O(1)` average	Returns `false` if element already present
`contains(e)`	`O(1)` average	Constant-time bucket lookup
`remove(e)`	`O(1)` average	Deletes element from bucket

Null Allowance: HashSet allows exactly one null element, stored at bucket index 0.
Thread Safety: Not thread-safe. Use Collections.synchronizedSet() or ConcurrentHashMap.newKeySet() for multi-threaded environments.

HashSet

The equals() and hashCode() ContractCopy Anchor Link

Complexity & Null HandlingCopy Anchor Link

On this page

The `equals()` and `hashCode()` Contract

Complexity & Null Handling