In a chained hash table, why does inserting n colliding keys cost quadratic time?

## The insert that isn't O(1) A chained hash table stores each bucket as a linked list of entries. Insert looks like this: 1. compute the hash of the key and reduce it to a bucket index; 2. **walk that bucket's chain**, comparing the new key against each stored key, to find an existing entry; 3. if found, overwrite the value; otherwise attach a new node. Step 2 is where the cost hides. Map semantics require keys to be unique, so the duplicate check is not optional — it is the reason insert is proportional to the length of the chain it lands in, not to a constant. ## The series Suppose all n keys reduce to the same bucket. Chain length before the k-th insert is `k-1`, and the duplicate check walks all of it (no match is found, so it walks to the end). Total comparisons: ``` 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 ``` That is Theta(n^2). With n = 10,000 keys it is roughly 50 million key comparisons, each one a full comparison of two strings that were deliberately built to be long-ish and equal in their cheap prefix checks. A single request has turned into seconds of CPU. Notice the asymmetry that makes this an attack rather than a bug report: the attacker pays for n bytes, the server pays for n^2 work. Amplification is the whole point. ## Same hash versus same bucket Two different targets, both usable: - **Same bucket index.** The index is `hash(key)` reduced modulo a bucket count `m`, and `m` is small — thousands, not billions. Even against a strong unkeyed hash, an attacker can generate random candidate keys and keep the ones landing in the chosen bucket; roughly one in `m` candidates qualifies. Cheap, and it requires no weakness in the function at all. - **Same full hash value.** For simple polynomial or additive hashes over strings, colliding pairs can be *constructed* algebraically: find two short fragments with equal hash contribution, and every concatenation of choices from those two fragments collides, giving exponentially many colliding keys from a tiny search. This is the stronger version, and it survives resizing. That second point matters for a common wrong answer. "The table will resize and split the chain" is only true when the keys merely shared an index; if their full hash values are identical they collide again in the new table, and the resize has simply spent extra work rehashing them. ## Precompute once, replay forever An unkeyed hash function is deterministic and identical in every process on every machine running that software. So the collision set is computed **offline, once**, and then works against every deployment of that software forever. There is no per-target work, which is why published proof-of-concept payload files exist and why this scales to a mass attack. ## Does another collision-resolution scheme escape it? No — the failure is about bucket occupancy, not about the shape of the overflow storage. With open addressing and linear probing, n keys targeting one slot form one long occupied run; the k-th insert probes about k slots before finding space, and the total is again quadratic, with deleted-entry markers making it worse. Any scheme that resolves collisions by *searching* inherits the shape. The schemes that do not are the ones that bound the search: an over-long bucket promoted to a balanced search structure gives O(log n) per operation, so n inserts cost O(n log n) instead of O(n^2). That is a damage bound, not a prevention — it does not stop the collisions, it just makes them affordable. ## Reading the cost correctly Two precision points interviewers listen for: - The bound is on a **worst-case sequence**, and it is not "amortized away". Amortization covers the resizing cost of growth-doubling, which really is O(1) per insert averaged over a sequence. It says nothing about chain scanning, because there is no cheap-operation surplus to pay for the expensive ones — every insert in this sequence is expensive. - The dominant term is **comparisons**, not hashing. Hashing each key is linear in key length and happens once per insert; the quadratic term comes from repeated traversal, so profiling shows time inside equality comparison, which is a useful diagnostic fingerprint. Ecosystems diverged on the remedy for exactly this arithmetic: some mainstream runtimes (Python, Ruby, Perl) made the hash unpredictable per process, while others capped the number of accepted request parameters or bounded the bucket cost with an ordered fallback structure.