DSA Hashing

Hash Sets

A courier app must know whether a package ID was already scanned today. A list check grows with every stop. A hash set answers in when load and hashing stay healthy.

A hash set stores one representative of each equality-distinct value. Collisions and still matter: worst case remains Θ(n).

What happens first?

Question shape

Presence only, or do you need a payload?

Stable values; equal ⇒ same hash.

Does first-occurrence order matter?

Average vs worst

Expected O(1); Θ(n) under collisions.

What actually happens

Naive idea: keep scanned IDs in a list and scan for each new package. Correct. At stop 10⁴ with a growing list, each check costs thousands of comparisons.

Better idea: store IDs in a hash set. Add and contains hash to a bucket, resolve collisions, confirm equality. Under controlled , each check is expected O(1).

The set still fails as a multiset (it cannot count duplicates), when iteration order is assumed without an ordered set, when keys mutate, or when collisions degenerate to Θ(n). Pair with a map when you need counts or first-index payloads.

Invariant

The structure contains exactly one representative for each equality-distinct value inserted and not removed. Membership is true iff that representative is reachable via hash + collision policy + equality. The equality–hash contract holds for every resident value.

How to choose a hash set

1. Presence only? Hash set. Need counts, indices, or objects? Hash map.

2. Order or ranges? Insertion-ordered set, sorted tree set, or sort keys on output. Do not rely on incidental hash iteration order.

3. Dense integer universe? Bitset or boolean array can beat a general hash set on memory and constants.

Quantitative check

10⁴ scans against a growing list: roughly 10⁴ × 5×10³ ≈ 5×10⁷ comparisons on average. Same workload with a hash set: about 10⁴ expected-constant checks. If all IDs collide into one chain of length 10⁴, you are back to linear scans: average vs worst case is the whole story.

Logical model

A mathematical set: every value is either present or absent.

Typical API

add · contains · remove · size · iterate

Expected update

O(1), amortized across occasional table resizes

Worst case

O(n) when many keys require the same collision path

Interactive hash set demo

Try adding duplicates and watch membership stay unique.

ℹ️ Ready to use Hash Set!

Apple

Hash: 2

Banana

Hash: 1

Cherry

Hash: 5

Membership semantics, step by step

Buckets explain how a hash set works. This trace explains what its public API must guarantee, including duplicate adds and missing removals.

Collection semantics laboratory

What does each API operation promise?

Follow logical state changes independently of buckets, capacity, and collision strategy.

start with ∅

Step 1 / 8

Logical set state

size = 0

∅ · empty set

Display order is illustrative; a hash set's iteration order is guaranteed only when its API says so.

Return / effect

size = 0

Contract

A set stores membership, not a count of how many times a value was submitted.

Set algebra

A = {Ada, Grace, Linus} · B = {Grace, Ken, Linus}

A ∩ B = {Grace, Linus}

Jump to operation

Duplicates are no-ops

Apple

Added

Banana

Added

Apple

No-op · duplicate

When you add “Apple” again, the set uses its hash to find a candidate bucket and then checks equality. An equal value already exists, so the operation is a no-op. A matching hash alone is only a collision, not proof that two values are equal.

The equality–hash contract

a == b ⇒ hash(a) == hash(b)

Equal values must produce equal hashes. The reverse is not required: two unequal keys may collide, so the table must still run an equality check inside the selected bucket or probe sequence.

A usable hash-key contract needs

Reflexive: a equals itself.
Symmetric: a = b implies b = a.
Transitive: a = b and b = c imply a = c.
Stable key behavior: equality and hash do not change while the value is stored.

Mutable-key hazard: if a field used by hash or equality changes after insertion, a later lookup searches the new bucket while the object remains in the old one. The entry can appear “lost” even though iteration still reveals it.

Use case: filtering

A set removes duplicates, but a plain set conversion may not preserve the input order. Track seen while scanning when “first occurrence wins” is part of the contract.
unique = list(dict.fromkeys(items))

Expected constant-time checks

Checking if x in my_set is expected O(1); scanning a list is O(n). For one tiny collection a list may be simpler and more cache-friendly, but repeated membership queries are where a set usually wins.

Set algebra is executable vocabulary

Union · A ∪ B

Values in either set

a | b

Intersection · A ∩ B

Values in both sets

a & b

Difference · A − B

Values in A but not B

a - b

Symmetric diff · A △ B

Values in exactly one set

a ^ b

With hash sets, union is expected O(|A| + |B|). Intersection can use expected O(min(|A|, |B|)) membership work by iterating the smaller side. Computing A − B is expected O(|A|) when testing each member of A, plus output materialization. A bitset performs the same algebra word-by-word.

Implementation

Python

python

def unique_in_order(items):
    seen = set()
    output = []

    for item in items:
        if item in seen:       # expected O(1)
            continue
        seen.add(item)
        output.append(item)
    return output

a = {1, 2, 3}
b = {3, 4}
print(a | b)  # union: {1, 2, 3, 4}
print(a & b)  # intersection: {3}
print(a - b)  # difference: {1, 2}

a.discard(9)  # missing value: no-op
# a.remove(9) # would raise KeyError

Java

java

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

public class Main {
    static <T> List<T> uniqueInOrder(List<T> items) {
        Set<T> seen = new HashSet<>();
        List<T> output = new ArrayList<>();
        for (T item : items) {
            if (seen.add(item)) output.add(item);
        }
        return output;
    }

    static <T> void removeOrThrow(Set<T> set, T value) {
        if (!set.remove(value)) throw new NoSuchElementException(String.valueOf(value));
    }

    public static void main(String[] args) {
        Set<Integer> a = new LinkedHashSet<>(List.of(1, 2, 3));
        Set<Integer> b = new LinkedHashSet<>(List.of(3, 4));

        Set<Integer> union = new LinkedHashSet<>(a);
        union.addAll(b);
        Set<Integer> intersection = new LinkedHashSet<>(a);
        intersection.retainAll(b);
        Set<Integer> difference = new LinkedHashSet<>(a);
        difference.removeAll(b);

        System.out.println(union);        // [1, 2, 3, 4]
        System.out.println(intersection); // [3]
        System.out.println(difference);   // [1, 2]

        boolean discarded = a.remove(9); // false; missing value is a no-op
        assert !discarded;
        // removeOrThrow(a, 9);            // would throw NoSuchElementException
    }
}

Choose the representation by the query

Structure	Membership	Update	Order / range	Best fit
Hash set	Expected O(1)	Expected O(1)	Usually unspecified	General membership and dedupe
Balanced-tree set	O(log n)	O(log n)	Sorted; range queries	floor, ceiling, predecessor
Sorted array	O(log n)	O(n)	Sorted; cache-friendly	Mostly-static small sets
Bitset	O(1) bit test	O(1) bit update	Integer universe order	Dense keys in 0..U−1
Boolean array	O(1)	O(1)	Index order	Tiny known universe; simplest visited flags

Complexity ledger

Operation	Expected / amortized	Worst case	What drives it?
contains	O(1)	O(n)	Hash, probe/chain length, equality cost
add	O(1) amortized	O(n)	Duplicate check; occasional resize/rebuild
remove	O(1)	O(n)	Locate equal key, then repair bucket/probe state
iterate	Θ(n)	Θ(n + capacity)	Implementation may scan unused table slots
build from n items	O(n)	O(n²)	n expected-constant inserts vs pathological collisions

Hashing and equality are not necessarily O(1): hashing a long string can inspect its characters unless the runtime caches the result.

Patterns that naturally produce a set

Seen-before detection

While streaming values, test membership before inserting. This powers duplicate detection and longest-consecutive-sequence solutions.

Graph reachability

Mark a node visited when it is discovered, not after processing, to prevent duplicate work and cycles.

Sliding-window uniqueness

Keep exactly the values inside the current window; if multiplicity matters, graduate to a frequency map.

Constraint and exclusion lists

Forbidden states, occupied coordinates, reserved names, and Sudoku row/column/box checks are membership facts.

Failure modes and design checks

Do not rely on incidental iteration order. Choose an explicitly ordered set when order is part of the result.
Do not confuse a set with a multiset. A set cannot tell whether a value occurred twice; use value → count for that.
Keep stored keys hash-stable. Prefer immutable values or hash only immutable identity fields.
Expect collision defenses to vary. Some runtimes randomize selected hashes, treeify long chains, or use other strategies; none changes the abstract API.
Mind memory overhead. Spare capacity buys short probes. A bitset or sorted vector can be much smaller for the right domain.

Exercises

Stream 10⁵ package IDs with ~1% duplicates. Compare total membership comparisons for list-vs-set seen. When would a bitset be even better?
Explain why set(items) can change order relative to input, and write an order-preserving dedupe that still uses expected O(1) membership.
Give a counterexample where a set is the wrong structure for “exactly two occurrences.” Which map shape fixes it?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): hash tables as the engine behind set membership.
Python set / frozenset docs: algebra operators and hashability rules.
Java HashSet / LinkedHashSet documentation: uniqueness and iteration-order contracts.

Takeaway

Hash sets answer “have I seen this before?” in expected constant time when load and hashing cooperate; worst case is still linear. Pair them with maps when you also need payloads (counts, first index, graph adjacency).