One Bucket, 10,000 Keys — The Attack Hiding in O(1)

Introduction

Every engineer learns hash maps the same way: constant-time lookups, constant-time inserts, constant-time deletes. It's one of the first "magic tricks" you see in a data structures course, and it becomes such a deeply held assumption that most of us stop questioning it. That assumption is exactly what makes algorithmic complexity attacks so dangerous — they don't exploit a bug in your code, they exploit a gap between what a hash map promises on average and what it actually guarantees in the worst case.

This matters for two very different reasons. First, it's a real production failure mode — the kind that shows up as "everything was fine until it wasn't," no stack trace, no obvious root cause, just a server pinned at 100% CPU. Second, it's a favorite systems-design and senior-level interview topic, because it tests whether you understand why a hash map is fast, not just that it's fast. Interviewers who ask "what happens when every key hashes to the same bucket?" are checking whether you've internalized the difference between average-case and worst-case complexity — a distinction that separates people who memorized Big-O tables from people who understand what's underneath them.

Problem Overview

At its core, this isn't a "solve for x" coding problem — it's a systems question: can an attacker who controls the input to a hash map force it to behave like a linked list instead of a hash table, and if so, what stops them?

A hash map stores key-value pairs by running each key through a hash function, squeezing the result down to fit a fixed-size array of buckets, and storing the value at that bucket. Because there are always more possible keys than buckets, some keys are mathematically guaranteed to land in the same bucket — this is the pigeonhole principle, and it applies to every hash map ever built. When that happens, it's called a collision, and it's handled by chaining: the bucket becomes a small list, and colliding keys get appended to it.

Under normal, random traffic, collisions are rare and chains stay short, so lookups stay close to O(1). But if an attacker can predict or reverse-engineer your hash function, they can deliberately craft thousands of keys that all collide into the same bucket. Send those keys as input — say, as JSON field names used directly as dictionary keys — and one bucket balloons into a chain of thousands. Every operation touching that bucket now has to walk the entire chain, degrading from O(1) to O(n). This is the algorithmic complexity attack: turn your fastest data structure into your slowest one, using nothing but well-chosen input.

Example

Imagine an API endpoint that accepts a JSON body and stores each field as a key in a Python dictionary — something like a request-metadata cache keyed by whatever field names the client sends.

Normal traffic:

{"user_id": 42, "session": "abc123", "region": "us-east"}

Three keys, three different buckets (almost certainly), lookups stay fast.

Crafted attack payload:

{"AaAa": 1, "AaBB": 1, "BBAa": 1, "BBBB": 1, ...repeated thousands of times}

If these strings are constructed to produce colliding hash values under the target hash function (a known technique against older, unseeded hash implementations), every one of them lands in the same bucket. One dictionary insert that should take nanoseconds now inserts into — and later scans — a chain thousands of entries long.

The output isn't wrong data. That's what makes it sneaky. The values are stored and retrieved correctly. What breaks is time: response latency climbs from milliseconds to seconds, and CPU usage spikes, because every lookup on that bucket now walks the whole chain instead of jumping straight to the value.

Intuition

Here's how an experienced engineer reasons about this, without jumping to code first.

Start with the promise: "hash map lookups are O(1)." Immediately ask — O(1) on average, or O(1) always? The honest answer is average case. The worst case, when every key collides into one bucket, is O(n) — you've built an expensive linked list wearing a hash map's clothes.

Next question: what determines which bucket a key lands in? The hash function. If that function is deterministic and its internals are knowable (open source language runtimes, publicly documented algorithms), an attacker with a local copy of the same runtime can precompute inputs offline that collide, then fire them at your server without ever touching it during the search.

That reframes the problem. It's not "how do we make hashing faster" — average case is already fast. It's "how do we make the worst case unreachable, or at least uneconomical, for someone who doesn't know a secret we hold." That's the seed of every real defense: keep something about the hash function unpredictable, cap how bad a single bucket can get, and change the underlying strategy when a bucket does get bad.

Brute Force Solution

The "brute force" here isn't a slower algorithm — it's the naive hash map: fixed, public hash function, no bucket-size limits, no fallback strategy.

Idea: Use whatever the language's default hash function is, directly, on untrusted input, with no additional safeguards.

Algorithm: Standard hashing and chaining — hash the key, mod by table size, append to that bucket's list.

Advantages: Simplest possible implementation, fastest average-case performance, zero overhead.

Disadvantages: No protection against crafted input. A single request with adversarial keys can degrade one bucket to O(n), and repeated requests can degrade many buckets simultaneously, taking down the whole service.

Complexity:

• Average case: O(1) time per operation, O(n) space for n entries.
• Worst case (under attack): O(n) time per operation on the compromised bucket, same O(n) space.

Optimal Solution

Real hash map implementations (CPython's dict, Java's HashMap, Ruby's Hash) combine three independent defenses. None of them is sufficient alone — together, they close the gap.

Defense	What it does	Why it works
Randomized seeding	Mix a random, per-process seed into the hash function at startup	An attacker can't precompute colliding keys without knowing your seed, since it changes every run
Treeifying	Convert an overloaded bucket from a linked list to a balanced tree once its chain crosses a threshold	Worst case per bucket drops from O(n) to O(log n)
Load-factor limits	Resize and rehash the entire table before any bucket can grow unchecked	Keeps the average chain length bounded, so collisions stay rare even under sustained load

Think of it as layered defense, not a single fix. Seeding stops the attacker from planning the attack in advance. Load-factor limits keep chains short under normal growth. Treeifying is the safety net for the case both of the above still let something through — it caps how bad the worst case can get even if a bucket does grow.

Python Code

CPython already randomizes string hashing by default (PYTHONHASHSEED), which is the built-in version of defense #1. The code below simulates the vulnerability and the fix explicitly, so the mechanism is visible rather than hidden behind the interpreter.

import os
import hashlib


class VulnerableBucketMap:
    """A minimal hash map with a fixed, public hash function."""

    def __init__(self, size=16):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def _hash(self, key: str) -> int:
        # Deterministic, public function -> predictable by an attacker.
        digest = hashlib.md5(key.encode()).hexdigest()
        return int(digest, 16) % self.size

    def insert(self, key: str, value):
        bucket = self.buckets[self._hash(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key: str):
        bucket = self.buckets[self._hash(key)]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

    def max_chain_length(self) -> int:
        return max(len(b) for b in self.buckets)


class SeededBucketMap(VulnerableBucketMap):
    """Same map, with a random per-instance seed mixed into hashing."""

    def __init__(self, size=16):
        self.seed = os.urandom(16)
        super().__init__(size)

    def _hash(self, key: str) -> int:
        digest = hashlib.md5(self.seed + key.encode()).hexdigest()
        return int(digest, 16) % self.size

Code Walkthrough

• VulnerableBucketMap._hash hashes the key with MD5 alone — deterministic and identical on every run, which means an attacker running the same code offline can precompute colliding keys.
• insert and get implement standard separate chaining: find the bucket, scan it for a matching key.
• max_chain_length is the diagnostic that reveals the attack — under normal traffic it stays near 1; under a crafted payload it spikes.
• SeededBucketMap overrides only _hash, prepending a random seed generated once per instance with os.urandom. Because the seed isn't known ahead of time, keys crafted against one instance won't collide against another — this is exactly what CPython does for str and bytes hashing since Python 3.3.

Dry Run

Attack keys ["AaAa", "AaBB", "BBAa", "BBBB"] are crafted so their MD5 digests happen to collide mod 16 in VulnerableBucketMap (this is the illustrative premise — real attacks target the actual runtime's hash algorithm, not MD5, but the mechanics are identical).

1. insert("AaAa", 1) → hashes to bucket 7 → buckets[7] = [("AaAa", 1)]
2. insert("AaBB", 1) → also hashes to bucket 7 → buckets[7] = [("AaAa", 1), ("AaBB", 1)]
3. insert("BBAa", 1) and insert("BBBB", 1) land in bucket 7 too → chain length 4
4. get("BBBB") now scans 4 entries instead of 1 — with 10,000 crafted keys, that's a 10,000-entry scan on a single lookup.

Run the same four keys through SeededBucketMap twice, with two different random seeds, and they land in different buckets each time — the collision the attacker relied on simply doesn't reproduce.

Complexity Analysis

• Time: O(1) average per operation for both maps under normal traffic; O(n) worst case for VulnerableBucketMap under crafted input, versus O(1) average maintained for SeededBucketMap because the seed makes crafting colliding keys infeasible without prior knowledge of the random value.
• Space: O(n) for both, where n is the number of stored entries — the fix changes the attacker's leverage, not the memory footprint.
• These bounds hold because the seed is generated fresh per process (os.urandom) and never exposed, so an attacker has no way to compute it offline, removing the precondition the attack depends on.

Alternative Solutions

Rate-limiting or input validation at the API layer (capping the number of keys accepted per request, or rejecting non-alphanumeric field names) reduces exposure but doesn't fix the underlying data structure — it's a mitigation, not a solution, and it breaks down against slow, distributed attacks. Switching to a cryptographic hash like SipHash (what Python actually uses internally) instead of MD5 raises the cost of finding collisions even further, since SipHash is specifically designed to be a keyed pseudorandom function resistant to this exact attack class. In practice, production systems combine input limits and a properly seeded hash function — defense in depth, not either/or.

Edge Cases

• Empty map: no buckets are populated, max_chain_length should be handled gracefully (guard against max() on an empty sequence if size were 0).
• Single key repeated: inserting the same key many times should update, not chain — verify duplicate-key handling doesn't silently grow a bucket.
• All keys pre-collided by design (attack case): confirms the seeded version distributes them across buckets while the naive version does not.
• Table resized mid-attack: load-factor-triggered resizing must rehash every existing key with the same seed, or entries become unreachable.
• Very small table size: with few buckets, natural collisions look identical to attack traffic — treeifying and load-factor limits matter most here, since seeding alone can't compensate for a tiny table.

Common Mistakes

1. Assuming hash map operations are O(1) in the worst case, not just on average — this misunderstanding is the root of the whole vulnerability.
2. Using untrusted, unbounded input directly as dictionary keys without validating count or structure.
3. Rolling a custom hash function for "performance" without realizing it removes the runtime's built-in seeding protection.
4. Fixing the symptom (adding a rate limiter) without understanding the mechanism, then being surprised when a slower, distributed version of the same attack still lands.
5. Forgetting that a fixed seed baked into config or environment variables (rather than generated at random per process) reintroduces the exact vulnerability seeding was meant to close.

Interview Questions

• Why is hash map lookup described as O(1) if collisions are mathematically unavoidable?
• How would you detect that a hash map is under an algorithmic complexity attack in production, using only metrics you already have?
• What's the tradeoff between treeifying a bucket versus simply resizing the whole table more aggressively?
• If you couldn't change the hash function, what application-level mitigations would you add?
• How does this same class of attack apply to other structures built on hashing, like sets or Bloom filters?

Similar Problems

• Design a HashMap (LeetCode 706) — building the underlying chaining structure this whole video depends on.
• Group Anagrams — relies on hashing well-distributed keys; a good exercise in seeing collisions as a feature rather than a threat.
• LRU Cache (LeetCode 146) — combines a hash map with a linked list, another place where bucket/node degradation matters.
• Design a Rate Limiter — a natural mitigation to pair with this topic, since it addresses the attack from the input side.

Key Takeaways

Collisions are guaranteed by the pigeonhole principle — every hash map will hit them, and that's not a defect. What's not guaranteed is that chains stay short. An unbounded chain is a design choice, usually the default until someone explicitly tunes against it, and that gap is exactly what an algorithmic complexity attack targets. Randomized seeding, treeifying, and load-factor limits close that gap by making the worst case either unreachable or cheap enough not to matter.

Watch the Video

This walkthrough pairs with the full video breakdown, including a live look at chain growth under simulated attack traffic: {LINK}

About the Series

This lesson is part of Fun with Learning Technology, a series that opens the hood on the tools developers use every single day — not just what they do, but why they're built the way they are, and where the guarantees quietly stop holding.

Call To Action

If this connected the dots on something you'd used for years without questioning, the video walks through the live degradation in real time — worth watching on YouTube. Subscribe there for the next teardown, subscribe to the Substack for the written deep dives, and drop a comment with what you'd want opened up next.

---

@app.route("/track", methods=["POST"])
def track():
    data = request.get_json()
    counts = {}
    for key in data:          # attacker-controlled keys
        counts[key] = counts.get(key, 0) + 1
    return jsonify(counts)