Hashing, Collisions, Overflow, and Resizing in Hashtables

A hashtable collides when two distinct keys are squeezed by hash(key) mod capacity into the same bucket index — an unavoidable outcome of the pigeonhole principle once you map an unbounded key space onto a fixed-size array, and how you resolve that collision (probe elsewhere vs. chain) determines whether the table degrades gracefully or silently loses data.

Recognize the pattern

• Two keys with different values map to the same bucket index — e.g. hash(1011) % 10 == hash(1021) % 10 (both equal 1).
• A naive insert would overwrite the existing slot's data instead of preserving both entries.
• Lookup/insert times that were advertised as O(1) start creeping toward O(n) as the table fills up — a sign the load factor is high and collisions are compounding.
• The interviewer asks "what happens when the table gets full" or "how do you handle two keys hashing to the same slot" — that's the overflow / resizing / collision-resolution question cluster.

Brute force → optimal

Brute force (naive): a fixed array of size m where insert(key) writes directly to arr[hash(key) % m], silently overwriting whatever was there. This is O(1) only in the collision-free case, but it is incorrect — data loss on any collision, and it fails outright once more than m keys arrive (overflow).

Optimal: pair the hash function with a collision-resolution strategy (chaining or open addressing) and a resizing policy that rebuilds the table before the load factor climbs too high. This trades a small constant-factor overhead per operation for correctness and amortized O(1) behavior at any table size.

Collision resolution: two families

Chaining (open hashing)

Each bucket holds a small list (or tree, for very long chains) of all entries that hashed there. Insert appends to the bucket's list — O(1) to append, but a full lookup must scan the chain, costing O(chain length). Never overwrites; capacity is not a hard ceiling since chains can grow, though very long chains defeat the point of hashing.

Open addressing (closed hashing)

On collision, probe an alternate slot inside the same array using a deterministic sequence: linear probing ((h+i) % m), quadratic probing ((h+i²) % m), or double hashing ((h1 + i·h2) % m). Everything lives in the array itself — better cache locality than chaining, but the table has a hard capacity and clusters of filled slots ('primary clustering', specific to linear probing) make later probes longer. Quadratic probing reduces primary clustering but suffers milder 'secondary clustering'; double hashing approximates uniform probing and avoids both. Deletions need a 'tombstone' marker so later lookups don't stop probing too early.

Overflow and resizing

Overflow is not a corner case to patch after the fact — it is the reason resizing exists. Track load factor α = n / m (entries / capacity). When α crosses a threshold (commonly 0.7–0.75), allocate a new array of roughly double the capacity and rehash every existing key into it (bucket indices depend on m, so old slots are not simply copied). This single rehash costs O(n), but because doubling happens exponentially rarely, the amortized cost per insert stays O(1).

Complexity, derived

Chaining: with n keys in m buckets and a reasonably uniform hash, the expected chain length is α = n/m. Expected lookup/insert = O(1 + α); if the resize policy keeps α ≤ 1, that's O(1) expected. Space = O(n + m) for the array plus node overhead per entry.

Open addressing — the numbers depend on the probe sequence, not just on α: for linear probing specifically, Knuth's analysis gives expected probes for a successful search ≈ ½(1 + 1/(1−α)) and for an unsuccessful search ≈ ½(1 + 1/(1−α)²) — the squared term captures the extra cost of primary clustering. For double hashing, which closely approximates the idealized 'uniform hashing' assumption (each probe sequence is equally likely to be any permutation of slots), the results are meaningfully better: successful ≈ (1/α)·ln(1/(1−α)), unsuccessful ≈ 1/(1−α). Both families blow up as α → 1, which is why open addressing needs a lower resize threshold (~0.7) than chaining tolerates, but linear probing degrades fastest of the three schemes — the reason production hash maps that use open addressing (e.g. CPython's dict) favor perturbed/pseudo-random probing over plain linear probing. Space = O(m) — no per-node pointer overhead, but some slots are always wasted as headroom.

Resizing amortized cost: across a sequence of n inserts that trigger doublings at sizes 1, 2, 4, …, n, total rehash work = 1+2+4+…+n = O(2n) = O(n), i.e. O(1) amortized per insert — the classic geometric-series argument, identical to dynamic-array (ArrayList) growth analysis.

Worked example (chaining, m = 10)

Load factor after 5 inserts: α = 5/10 = 0.5, still healthy. Had this been open addressing with linear probing, inserting 1021 would instead scan bucket 1 (occupied) → bucket 2 (empty) and place it there, leaving bucket 1 holding only 1011.

Java: separate chaining with resize

class HashMapChain<K, V> {
    static class Node<K, V> { K key; V val; Node<K, V> next;
        Node(K k, V v, Node<K, V> n) { key = k; val = v; next = n; } }

    private Node<K, V>[] buckets;
    private int size = 0;

    @SuppressWarnings("unchecked")
    HashMapChain(int capacity) { buckets = new Node[capacity]; }

    void put(K key, V val) {
        int i = idx(key, buckets.length);
        for (Node<K, V> n = buckets[i]; n != null; n = n.next)
            if (n.key.equals(key)) { n.val = val; return; }
        buckets[i] = new Node<>(key, val, buckets[i]);
        size++;
        if ((double) size / buckets.length > 0.75) resize();
    }

    V get(K key) {
        for (Node<K, V> n = buckets[idx(key, buckets.length)]; n != null; n = n.next)
            if (n.key.equals(key)) return n.val;
        return null;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        Node<K, V>[] old = buckets;
        buckets = new Node[old.length * 2];
        for (Node<K, V> head : old)
            for (Node<K, V> n = head; n != null; n = n.next) {
                int i = idx(n.key, buckets.length);
                buckets[i] = new Node<>(n.key, n.val, buckets[i]);
            }
    }

    private int idx(K key, int cap) { return (key.hashCode() & 0x7fffffff) % cap; }
}

Security: Hash Collision DoS (Denial of Service)

In production applications, hash maps are frequently used to parse user-supplied data (such as JSON API payloads or HTTP query parameters). This exposes a severe security vulnerability known as a Hash Collision DoS attack:

• The Vulnerability: Many standard library hash maps (including Java 7's HashMap, Ruby, and Python before 3.3) traditionally used deterministic, polynomial rolling hash functions for strings. If an attacker knows the hash algorithm, they can pre-calculate thousands of different strings that all hash to the same value (e.g., yielding identical key.hashCode() % capacity).
• The Attack: The attacker sends a single HTTP request containing 10,000 colliding string keys. The server parses this request into a hash map. Because all keys collide, the hash map's internal buckets degrade from average O(1) operations to worst-case O(N) linear scans. Parsing the single request now takes minutes of 100% CPU utilization, browning out the application server.
• The Production Remedies:
  1. Randomized Hashing (SipHash): Modern programming languages and runtimes (including Rust's default hash map, Go, Ruby, and Python 3.3+) use cryptographic-strength, non-collision-prone hash algorithms like SipHash or hardware-accelerated AES-hash, initialized with a random seed key generated per process. Since the seed is random and secret, an external attacker cannot predict or construct colliding keys.
  2. Tree-fication of Chains: In Java 8+, the standard HashMap mitigates this by automatically converting a bucket's linked list chain into a balanced Red-Black Tree once the chain length exceeds 8 (and the total table capacity is at least 64). This bounds the worst-case collision lookup to O(log N) instead of O(N), neutralizing the DoS attack vector.

Pitfalls

• Overwriting on collision instead of chaining/probing — silent data loss (the exact bug in the naive book-table implementation).
• Using hash % m with a poor hash function and a power-of-two m — low bits of a bad hash repeat, causing clustering even with few keys.
• Deleting from an open-addressed table without tombstones — later lookups stop early at the hole and report false negatives.
• Resizing too late (high threshold) — probe/chain lengths blow up right before the resize, causing latency spikes.
• Forgetting that resizing is O(n) — in latency-sensitive systems a single insert can trigger a full rehash; incremental resizing amortizes this instead of pausing.
• Quoting linear-probing's probe-count formulas as if they applied to open addressing in general — double hashing under the uniform-hashing assumption performs meaningfully better, so the choice of probe sequence changes the actual complexity, not just a constant factor.
• Unsalted hashing in public APIs (Hash Collision DoS): Neglecting randomized hashing allows attackers to craft colliding string payloads, forcing maps into linear scans (O(N)) and browning out CPU cores.

When to use / when not, vs. alternatives

Chaining — use when key sizes are unpredictable, deletions are frequent, or the load factor may exceed 1; the trade-off is pointer-chasing overhead and worse cache locality per lookup.

Open addressing — use when memory locality matters and load factor is kept below ~0.7 (e.g. CPython's dict, which uses open addressing with a pseudo-random probe sequence rather than plain linear probing to avoid primary clustering); the trade-off is a hard capacity, trickier deletion, and clustering risk under a weak hash/probe sequence.

Named alternative — balanced BST (e.g. TreeMap): gives O(log n) worst-case guaranteed (no pathological O(n) collision chains) and sorted-order iteration, at the cost of losing average O(1) access. Choose a hashtable when you need average-case O(1) and don't need ordering; choose a BST when adversarial inputs or ordered traversal matter.

Takeaways

• Collisions are guaranteed by the pigeonhole principle, not a bug — the design question is how you resolve them (chain vs. probe).
• Load factor α is the dial that connects collisions to performance; resizing at a fixed α threshold keeps operations amortized O(1).
• Chaining trades memory/cache locality for simplicity and tolerance of α > 1; open addressing trades a hard capacity for better locality — and within open addressing, the probe sequence itself (linear vs. quadratic vs. double hashing) materially changes the expected-probe-count formula, not just a constant.

Recall: Why does resizing a hashtable at capacity m require rehashing every key instead of just copying old slots into a bigger array?

Adapted and expanded from the Hashing, Collisions, Overflow, and Resizing course notes for interview-prep depth (mechanism, complexity derivation, worked trace, and trade-off analysis added).