Why doesn't a hash map's expected O(1) lookup protect a service whose keys come from the client?
answer
- expected is an average over what?
- who gets to choose the keys here
- many distinct keys, one bucket
- a bucket is searched linearly
- averages promise nothing against a chooser
basics
~20 sExpected O(1) assumes keys were not chosen against the hash function. A client who can determine that function submits many keys that land in one bucket, so every insert and lookup there becomes a linear scan.
solid answer
~40 sThe O(1) on a hash table is an *expected* bound, and it rests on an assumption about the input: that keys spread roughly evenly over the buckets. That assumption is about the data, not about the structure, and when the keys arrive from a caller the caller controls it. If the hash function is fixed and publicly known, an attacker can select thousands of distinct strings that reduce to the same bucket; the table then behaves like one long list and each operation degrades toward O(n). Building such a map costs quadratic work, so a modest request body can burn seconds of CPU. That is hash flooding: an availability problem, not a correctness bug. Note that adding buckets is not the fix — the attacker simply recomputes collisions for whatever bucket count you choose.
go deeper
Be ready to say that expected O(1) is an average that assumes keys spread over buckets, and that a caller who picks the keys can defeat that average. Name the worst case out loud: a linear scan of one bucket.
An interviewer expects the mechanism: even bucket occupancy is what makes the average hold, colliding keys destroy it, and enlarging the table does not help because the attacker recomputes against the new bucket count.
Show you would audit where client-controlled text becomes a map key across a service, and treat what you find as an availability risk with a measurable CPU cost per request, not a style nit.
Own the framing that an availability property resting on an average over attacker-supplied input is not a property at all, and decide whether the remedy belongs in shared platform defaults or in each team's hands.
## What the O(1) actually claims A hash table keeps entries in `m` buckets. To store or find a key it computes `hash(key)`, reduces that to an index in `0..m-1`, and works inside that one bucket. If the entries are spread evenly, each bucket holds about `n/m` entries, and with `m` kept proportional to `n` that is a small constant — hence "expected O(1)". Read the qualifier carefully. The bound is **expected**, and the expectation is taken over an assumption of roughly uniform bucket occupancy. Nothing in the data structure enforces that. It is a property of the *keys you are given*, combined with the hash function you chose. The worst case has never gone away: if every key lands in one bucket, that bucket is scanned linearly and a lookup is O(n). ## Who supplies the keys Most of the time nobody is trying to hurt you, real-world keys spread acceptably, and the average holds. The picture changes the moment the keys are supplied by someone else — request parameter names, header names, fields of a submitted document, identifiers in a batch payload. Now the input distribution is not an act of nature; it is an input the other party gets to choose after reading how your hash function works. And it is not hard to read. Non-cryptographic hash functions used for tables are small, published, and stable across releases; even where the source is unavailable, the *bucket index* is only a value modulo a smallish `m`, so keys sharing a bucket can be searched for cheaply. Nothing exotic is needed. ## The shape of the attack A request arrives carrying a few thousand distinct parameter names. The server parses them into a map, as servers do. Every name has been chosen to hash into the same bucket. Each insert must first walk that bucket to see whether the key is already present, so the first insert walks nothing, the second walks one node, the thousandth walks 999. The total is an arithmetic series — quadratic in the number of keys. The economics are what make it an attack rather than a curiosity: the request is small and cheap for the attacker to send, while the server spends CPU proportional to the *square* of the key count. A handful of concurrent requests can saturate a core. This is called hash flooding, or a hash-collision denial of service. ## Why the intuitive fixes miss - **"Use a bigger table."** More buckets change which index the colliding keys land in, not the fact that they can be made to share one. The attacker recomputes. - **"Use a stronger hash."** Strength here means resistance to finding *equal digests*. But you only need equal *bucket indices*, and there are only `m` of them; a strong but unkeyed function still lets an attacker enumerate keys until enough share a bucket. - **"Rate-limit it."** Rate limits help with volume, but the point of the attack is amplification: each individual request is legitimate-looking and small. - **"Limit the request size."** This one genuinely helps, because it bounds the key count `n` and therefore `n^2` — but only at every layer that builds a map, and it is a cap on the damage rather than a removal of the mechanism. What actually removes the attacker's leverage is making the hash function unpredictable to them: a keyed hash whose secret key is drawn randomly per process, so collisions cannot be computed offline and replayed. That is the direction every mainstream response took after the attack was publicised — Python, Ruby and Perl adopted randomized seeded hashing, PHP added a hard cap on the number of accepted parameters, and the JVM's mainstream hash map later added an ordered-tree fallback so an over-long bucket costs O(log n) rather than O(n). Same threat, three different degrees of freedom. ## What this means for you The practical junior-level takeaway is a habit, not a formula: whenever text you did not create becomes a map key, the average-case guarantee is no longer a guarantee. Deduplication sets, memoization tables, caches keyed by client-supplied identifiers, and parsed object bodies all inherit the exposure, because the risk follows the untrusted data, not the type of container. When you state a complexity in an interview, say "expected O(1), O(n) worst case" and be ready to say what makes the worst case reachable on purpose.
- Which other parts of a service inherit this exposure?Anything keyed by a hash of untrusted text: deduplication sets, memoization and cache tables, header and session maps, and parsed document bodies. The exposure follows the data, not the container type, so the audit question is simply where client-controlled text becomes a key.
- Does keeping the hash function private remove the risk?No. Table hash functions in shipped software are readable or reconstructable, and a bucket index is only a value modulo a smallish bucket count, so same-bucket keys can be searched for by probing response times. Secrecy of code is not a defense; a secret per-process key is.
A ticket hall with ten windows is fast when arrivals spread out. If one person can send every arrival to the same window, the average queue length tells you nothing about the wait.
saying these in an interview costs you the question
- Hash lookups are O(1), so key content cannot matter
- Says a larger table or more buckets fixes it
- Treats it as possible only with homemade hash functions
- Claims a small request payload makes it harmless
- Confuses it with cryptographic collision resistance