Introduction to HashSets

A HashSet stores each element by computing its hash code, mapping that hash to one of a fixed number of buckets (index = hash mod capacity), and short-circuiting insert/lookup/delete to that single bucket instead of scanning the whole collection — uniqueness and O(1) average operations are both side effects of this addressing scheme, not separate features bolted on.

Recognize the pattern

• The problem asks "has this been seen before?", "does this exist?", or "remove duplicates" — with no need to preserve insertion order or associate extra data.
• You need membership testing repeated many times inside a loop (classic tell: nested loop doing contains that you want to collapse to O(1)).
• You only care about presence, not a value attached to a key (if you need a value too, that's a HashMap, not a HashSet).

Brute force vs. optimal

Brute force: keep elements in an array/list; to check membership or insert-if-absent, linearly scan every existing element. Insert-if-absent costs O(n) per call because you must scan before you know it's new; n insertions cost O(n²) total.

Optimal (HashSet): compute hash(x), jump directly to bucket hash(x) % capacity, and compare only against the few elements colliding in that bucket. Insert-if-absent becomes O(1) average; n insertions cost O(n) total.

Complexity, derived

Let n = number of elements, m = number of buckets (capacity). The load factor α = n/m. Java's HashSet (backed by HashMap) resizes (doubles m) whenever α would exceed 0.75, keeping α bounded.

Assume a good hash function distributes keys uniformly. Expected chain length in any bucket = α, a constant once α is bounded (≤0.75). So:

• add / contains / remove: O(1) hash computation + O(α) = O(1) amortized average. Worst case (all keys collide into one bucket, e.g. adversarial hashing or a broken hashCode()) degrades to O(n) — Java 8+ HashMap converts a long chain (≥8 entries) to a red-black tree, capping worst case at O(log n) per bucket op — but only once the table itself has ≥64 buckets (MIN_TREEIFY_CAPACITY); below that, a long chain triggers a resize instead of treeification.
• resize: doubling and rehashing m→2m costs O(n), but happens O(log n) times total across n inserts, so amortized cost per insert stays O(1) (same argument as dynamic array doubling).
• space: O(n) for elements + O(m) for the bucket array, m = O(n) since α is bounded — so O(n) overall, with a constant-factor overhead (~1.33x due to 0.75 load factor, plus per-entry object/pointer overhead in Java).

Traced example — dedup a stream

Insert [7, 3, 7, 5, 3] into a HashSet with capacity m = 4 (indices 0-3), hash = value % 4:

Final set: {7, 3, 5} — order not guaranteed to match insertion order.

Reference implementation

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DedupExample {
    public static List<Integer> firstOccurrences(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        List<Integer> result = new ArrayList<>();
        for (int n : nums) {
            if (seen.add(n)) {
                // add() returns true only the first time n is seen
                result.add(n); // keep first occurrences, in input order
            }
        }
        return result;
    }
}

Pitfalls

• Mutable elements: mutating an object after inserting it into a HashSet changes its hash code, so it becomes unfindable (lookup hashes the new state and lands in the wrong bucket) — never mutate fields used in hashCode()/equals() while the object lives in a set.
• Broken hashCode()/equals() contract: if two equal objects return different hash codes, duplicates slip through; if hashCode() always returns the same value, every element collides and performance degrades to O(n).
• Assuming order: iterating a HashSet gives no guarantee of insertion or sorted order — use LinkedHashSet or TreeSet if you need that.
• Autoboxing pitfalls in Java: Integer caching only covers -128..127; comparing boxed types with == instead of relying on equals()/hashCode() inside custom logic causes subtle bugs.

When to use / when not — trade-offs

Takeaways

• Uniqueness and O(1) average lookup both come from the same mechanism: hash → bucket index → localized comparison.
• Load factor is the knob that trades memory (lower α, more buckets, less collision) for time; Java resizes at α > 0.75.
• Worst case is O(n) per op under hash collisions unless the underlying map treeifies long chains (Java 8+ caps it at O(log n), once chain ≥8 and table capacity ≥64).
• A HashSet's power collapses if hashCode()/equals() is wrong or if stored objects mutate in place.

Recall: Why does resizing a HashSet (doubling capacity and rehashing all elements) still keep amortized insertion at O(1), even though a single resize costs O(n)?

Synthesized from standard HashSet/HashMap internals (Java Collections Framework docs and algorithm literature on hashing with chaining) and the original page's HashSet vs. HashTable framing.