Hashing and Hash Tables Questions

Direct answer

At 10 billion documents, no exact structure can cheaply answer "have I seen this before": a Bloom filter (a fixed-size bit array plus k hash functions, that can only ever say "definitely new" or "possibly seen before", never "definitely seen before") is the right first-line gate, because it collapses each average-2 KB document down to a handful of bit checks regardless of document size. Every positive from the filter (true duplicate or false positive) then gets verified against a persisted exact index keyed by a cryptographic content hash, which is what actually decides duplication. Sharding that whole pipeline by consistent hashing (so each node owns a disjoint, resizable slice of the 10-billion-document keyspace) is what lets the design hit 50,000 docs/sec and stay incrementally updatable without a global rebuild.

Structured elaboration

Hashing strategy. Two roles for hashing, deliberately kept separate. First, the Bloom filter itself needs k hash functions per document to set/check k bits; rather than implementing k independent hash functions, use the standard Kirsch-Mitzenmacher trick of deriving all k from just two: g_i(x) = h1(x) + i * h2(x) mod m. Second, and separately, every document is reduced to a cryptographic content hash (SHA-256 of its normalized content) that becomes its actual dedup key in the persistent exact-index; a 256-bit cryptographic hash makes a genuine collision between two different documents astronomically unlikely, so content-hash equality can be trusted as ground truth for "these are the same document" without a full byte-for-byte comparison.

Sharding by consistent hashing (distributed ownership). Partition the 10-billion-document keyspace across shard nodes using consistent hashing on the content hash, not a plain hash mod N. The difference matters operationally: adding or removing a shard node under consistent hashing only reassigns roughly 1/N of the keyspace, versus a full reshuffle under plain modulo hashing, which is what lets the ingest fleet scale elastically at 50,000 docs/sec without a stop-the-world repartition. Each shard then only has to size its own Bloom filter for its own fraction of the 10 billion documents, not the whole corpus.

Storage choices, layered for the latency target. Each shard holds three tiers: (1) a small in-memory LRU (least-recently-used) cache of the most recently ingested hashes, so a burst of near-simultaneous duplicates never even reaches the filter; (2) the shard's Bloom filter, the main membership gate; (3) a persistent exact-index (a key-value store keyed by content hash, backed by a log-structured merge tree, a write-optimized on-disk structure that batches writes and merges them in the background rather than updating in place) that is the actual source of truth, used both for verification and for full-filter rebuilds. In a memory-constrained deployment, a Count-Min Sketch (CMS, a small fixed-size frequency-estimating structure) can drive the admission and eviction policy for tier (1), promoting keys that are being seen repeatedly and evicting ones that are not, the same admission-policy idea used by modern cache designs, so the bounded RAM budget is spent on the keys most likely to be checked again soon rather than on whichever key happened to arrive most recently.

Collision handling and verification. A Bloom filter's "possibly seen" answer is never proof; every positive must be verified against the persistent exact-index before being counted as a real duplicate, and only a verified hit is treated as a duplicate for the 5% duplicate-fraction accounting the question states. This is also why sizing the filter's false-positive rate matters operationally: every false positive costs one wasted verification read against the persistent store, on top of the verification reads every true duplicate legitimately needs.

Memory estimates, worked at the stated scale. Sizing a single Bloom filter for all n = 10,000,000,000 documents at a target false-positive rate p = 1e-6 uses the standard formulas:

m = -n * ln(p) / (ln 2)^2
k = (m / n) * ln 2

That gives m about 287,551,751,321 bits (about 35.94 GB) and k = 20 (rounding the computed 19.93 to the nearest integer), which achieves a false-positive rate of essentially 1e-6 when checked directly. At 5% true duplicates, that is 500,000,000 genuine duplicate verifications expected, against roughly 10,000 expected false-positive verifications at this achieved rate, wasted verification traffic is about 0.002% of the genuine verification volume, well controlled. Sharded across nodes, each shard's bit array shrinks proportionally: 4.49 GB at 8 shards, 2.25 GB at 16 shards, 1.12 GB at 32 shards, and at 16 shards each node only needs to sustain about 3,125 docs/sec of the 50,000 docs/sec target, comfortably within the sub-second per-document budget since a Bloom filter check is k = 20 cheap hash-and-bit-test operations.

The 4 GB-RAM-constrained variant. If a single node's RAM budget is capped at 4 GB, running the full 10-billion-item filter on one node is not an option (35.94 GB needed) and naively truncating it to 4 GB on one node collapses accuracy: at n = 10,000,000,000 and m capped to a 4 GB bit array (32,000,000,000 bits), the achieved false-positive rate blows up to about 21.6%, useless against a 1e-6 target. The fix is exactly the sharding-by-consistent-hashing design above, not a bigger machine: splitting the corpus across 9 shards, each holding its own 4 GB filter sized for its own roughly 1.11 billion documents, achieves a per-shard false-positive rate of about 9.8e-7, back in line with the global 1e-6 target, because each shard's filter only has to be accurate for its own slice of the keyspace, not the whole corpus.

flowchart LR
    A[Incoming doc, ~2KB avg] --> H[SHA-256 content hash]
    H --> CH[Consistent-hashing router]
    CH --> SH1[Shard 1: LRU + Bloom filter + exact index]
    CH --> SH2[Shard 2: LRU + Bloom filter + exact index]
    CH --> SH3[Shard N: LRU + Bloom filter + exact index]
    SH1 --> V{Bloom says possibly seen?}
    V -->|no| ACC[Accept as new, add to filter and index]
    V -->|yes| VER[Verify against exact index]
    VER -->|confirmed dup| REJ[Reject as duplicate]
    VER -->|false positive| ACC

Worked example

The memory table above is the concrete instantiation at the stated scale: full-corpus filter 35.94 GB at k=20 for a 1e-6 target; sharded to 8/16/32 nodes at 4.49/2.25/1.12 GB each; the 4 GB-constrained case needing 9 shards (not fewer) to hold the global false-positive rate near target, versus 21.6% if forced onto one 4 GB node.

Trade-offs and pitfalls

• Incremental updates are naturally supported for additions, not deletions. A plain Bloom filter has no way to unset a bit safely (another key may share it), so if the corpus ever needs to support removing a document from the dedup set, that requires a counting Bloom filter (small counters instead of single bits) or a scheduled rebuild from the persistent exact-index, not an in-place fix to the bit array.
• Fallback when the persistent exact-index is temporarily unavailable is a genuine business decision, not just an engineering one. Fail-closed (treat any unverifiable Bloom-filter positive as a duplicate and defer or reject the write) protects against ingesting duplicates but risks losing legitimately new documents during an outage; fail-open (accept anyway, reconcile later in a batch pass) protects ingest availability but risks temporarily double-counting. Pick based on which failure mode costs the business more.
• A common wrong turn: sizing one enormous shared Bloom filter for the whole corpus and putting it behind a single service, which recreates a single point of contention and a single point of failure at 50,000 docs/sec; the entire reason to shard by consistent hashing is so no single filter, and no single node, has to absorb the full throughput or the full memory requirement alone.
• Verification cost scales with the true duplicate rate, not just the false-positive rate. At 5% duplicates, verification reads happen for roughly 1 in 20 documents regardless of how tightly the filter's false-positive rate is tuned; tuning p tighter mainly buys back the small extra sliver of wasted verification traffic, not the bulk of it.

Approach

Open addressing stores every entry directly inside one flat array (no linked chains); on a collision, double hashing computes a second, independent probe step so different keys that collide at the same starting slot still spread out across the table instead of clustering along a fixed stride. Concretely, slot i for probe attempt p is (h1(key) + p * h2(key)) mod capacity, where h2 is forced to never be zero and, with a prime table capacity, is guaranteed to eventually visit every slot. Deletion cannot simply null out a slot, because later entries may have probed past that slot to resolve their own collision; nulling it would break their probe chain and make get stop early and report them missing. The fix is a tombstone: a special "deleted, but keep probing past me" marker distinct from both "live entry" and "truly empty."

Code (Java)

public class DoubleHashTable {
    private static final Object TOMBSTONE = new Object();
    private Object[] keys;
    private Object[] values;
    private int capacity;
    private int size;   // live entries
    private int used;   // live entries + tombstones, drives resize

    public DoubleHashTable(int capacity) {
        this.capacity = capacity;
        this.keys = new Object[capacity];
        this.values = new Object[capacity];
    }

    private int h1(Object key) {
        return (key.hashCode() & 0x7fffffff) % capacity;
    }

    private int h2(Object key) {
        int h = key.hashCode();
        return 1 + ((h & 0x7fffffff) % (capacity - 1));  // never 0
    }

    public void put(String key, Integer value) {
        if ((double) (used + 1) / capacity > 0.6) resize();
        int idx = h1(key), step = h2(key), firstTombstone = -1;
        for (int probe = 0; probe < capacity; probe++) {
            int slot = (idx + probe * step) % capacity;
            if (keys[slot] == null) {
                int target = (firstTombstone != -1) ? firstTombstone : slot;
                if (keys[target] == null) used++;
                keys[target] = key; values[target] = value; size++;
                return;
            } else if (keys[slot] == TOMBSTONE) {
                if (firstTombstone == -1) firstTombstone = slot;
            } else if (keys[slot].equals(key)) {
                values[slot] = value;
                return;
            }
        }
        throw new IllegalStateException("table full, resize invariant violated");
    }

    public Integer get(String key) {
        int idx = h1(key), step = h2(key);
        for (int probe = 0; probe < capacity; probe++) {
            int slot = (idx + probe * step) % capacity;
            if (keys[slot] == null) return null;
            if (keys[slot] != TOMBSTONE && keys[slot].equals(key)) return (Integer) values[slot];
        }
        return null;
    }

    public boolean delete(String key) {
        int idx = h1(key), step = h2(key);
        for (int probe = 0; probe < capacity; probe++) {
            int slot = (idx + probe * step) % capacity;
            if (keys[slot] == null) return false;
            if (keys[slot] != TOMBSTONE && keys[slot].equals(key)) {
                keys[slot] = TOMBSTONE; values[slot] = null; size--;
                return true;
            }
        }
        return false;
    }

    private void resize() {
        Object[] oldKeys = keys, oldValues = values;
        capacity = nextPrime(capacity * 2);
        keys = new Object[capacity]; values = new Object[capacity];
        size = 0; used = 0;
        for (int i = 0; i < oldKeys.length; i++) {
            if (oldKeys[i] != null && oldKeys[i] != TOMBSTONE) {
                put((String) oldKeys[i], (Integer) oldValues[i]);
            }
        }
    }

    private static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; (long) i * i <= n; i++) if (n % i == 0) return false;
        return true;
    }

    private static int nextPrime(int n) {
        int candidate = Math.max(n, 2);
        while (!isPrime(candidate)) candidate++;
        return candidate;
    }

    public int size() { return size; }
    public int capacity() { return capacity; }

    public static void main(String[] args) {
        DoubleHashTable t = new DoubleHashTable(7);
        t.put("a", 1); t.put("b", 2); t.put("c", 3);
        System.out.println("get a -> " + t.get("a"));
        System.out.println("get missing -> " + t.get("zzz"));
        t.delete("b");
        System.out.println("get b after delete -> " + t.get("b"));
        t.put("d", 4);
        System.out.println("get d after reusing tombstone slot -> " + t.get("d"));
        System.out.println("get a still resolves past tombstone -> " + t.get("a"));
        for (int i = 0; i < 30; i++) t.put("k" + i, i * 10);
        System.out.println("size after bulk insert -> " + t.size() + " capacity -> " + t.capacity());
        boolean allCorrect = true;
        for (int i = 0; i < 30; i++) if (!Integer.valueOf(i * 10).equals(t.get("k" + i))) allCorrect = false;
        System.out.println("all 30 post-resize keys correct -> " + allCorrect);
        System.out.println("c survived resize -> " + (t.get("c") == 3));
        System.out.println("b stays deleted after resize -> " + (t.get("b") == null));
    }
}

Output (compiled with javac and executed as shown; starting capacity 7):

get a -> 1
get missing -> null
get b after delete -> null
get d after reusing tombstone slot -> 4
get a still resolves past tombstone -> 1
size after bulk insert -> 33 capacity -> 79
all 30 post-resize keys correct -> true
c survived resize -> true
b stays deleted after resize -> true

Key points

• Tombstones on delete: a deleted slot is marked with a distinct TOMBSTONE sentinel (not null), so get keeps probing past it instead of stopping early, while put is free to reclaim that slot for a brand-new key. The demo confirms both halves: get("b") correctly returns null after delete, and get("a") still resolves even though its probe sequence now passes through b's tombstone.
• Rehashing strategy during resize: the table grows to the next prime at least double the old capacity (kept prime so h2's stride never shares a factor with the table size), and every live entry is walked and re-inserted through the normal put path; tombstones are dropped rather than copied, since a resize is exactly the natural point to reclaim their space. This is why used (live plus tombstones) rather than size (live only) drives the resize trigger: a table can fill up with tombstones alone and still needs to compact even though size looks small.
• Amortized O(1) argument: each resize costs (O(n)) (every live entry is rehashed once), but a resize only fires after roughly doubling the entries admitted since the last one, so the total rehashing work after (n) inserts is bounded by (n + n/2 + n/4 + \cdots < 2n), a constant multiple of (n). Spread over (n) inserts, that is (O(1)) amortized per insert, on top of the already-(O(1))-average probe cost.
• Production concurrency: this implementation is single-threaded only. Making open addressing thread-safe is harder than chaining, because a resize physically relocates every entry, so a reader mid-probe during a concurrent resize can land on a slot that no longer means what it did. Practical options are a single coarse lock around every operation (simple, but serializes all access), sharding into N independently-locked sub-tables (much better throughput, standard production pattern), or a lock-free design with versioned/CAS slots and a copy-on-resize scheme, which is substantially more complex to get correct and is usually reached for only when a proven mature implementation (like java.util.concurrent.ConcurrentHashMap, which uses chaining internally rather than open addressing for exactly this reason) is not applicable to the constraints.

Complexity

• Average case, insert/get/delete: (O(1)), assuming a good hash and load factor kept under the resize threshold (here 0.6) so probe sequences stay short.
• Worst case: (O(n)), a pathological hash or a table nearly saturated with tombstones can force a scan of most of the table.
• Resize: (O(n)) when triggered, (O(1)) amortized per insert overall, per the argument above.

Edge cases

• Deleting then reinserting a different key: must be able to reuse the tombstoned slot (put("d", 4) above lands where b was deleted).
• A key whose probe sequence crosses a tombstone left by an unrelated deleted key: must still resolve correctly (get("a") after b's deletion).
• A table that has accumulated many tombstones without much live growth: resizing on used rather than size prevents probe sequences from silently degrading toward (O(n)) even while the map looks small.
• Deleting a key that was never present: the loop reaches an empty (null) slot and returns false without touching the table.

Direct answer

A Bloom filter is a bit array plus k hash functions: insert sets k bit positions per item, and might_contain reports present only if all k of an item's positions are set, which guarantees zero false negatives and a bounded, tunable false-positive rate. The catch is that bits are shared across items by design, so a single bit cannot be safely unset on removal, which is exactly what a Counting Bloom Filter fixes by replacing each bit with a small counter.

Structured elaboration

Sizing follows the standard formulas for expected item count n and target false-positive rate p: $m = -\frac{n\ln p}{(\ln 2)^2}$ bits and $k = \frac{m}{n}\ln 2$ hash functions, with k positions per item generated from two base hashes via $g_i(x) = h_1(x) + i\cdot h_2(x) \bmod m$ rather than implementing k independent hash functions.

import hashlib, math

class BloomFilter:
    def __init__(self, n_expected, p_target):
        self.m = max(1, math.ceil(-(n_expected * math.log(p_target)) / (math.log(2) ** 2)))
        self.k = max(1, round((self.m / n_expected) * math.log(2)))
        self.bits = bytearray(self.m)

    def _hashes(self, item):
        h1 = int(hashlib.sha256(item.encode()).hexdigest(), 16)
        h2 = int(hashlib.md5(item.encode()).hexdigest(), 16)
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def insert(self, item):
        for idx in self._hashes(item):
            self.bits[idx] = 1

    def might_contain(self, item):
        return all(self.bits[idx] for idx in self._hashes(item))


class CountingBloomFilter(BloomFilter):
    def __init__(self, n_expected, p_target, counter_max=15):
        super().__init__(n_expected, p_target)
        self.counters = [0] * self.m
        self.counter_max = counter_max

    def insert(self, item):
        for idx in self._hashes(item):
            if self.counters[idx] < self.counter_max:
                self.counters[idx] += 1

    def remove(self, item):
        for idx in self._hashes(item):
            if self.counters[idx] > 0:
                self.counters[idx] -= 1

    def might_contain(self, item):
        return all(self.counters[idx] > 0 for idx in self._hashes(item))

Insert and might_contain both cost O(k), independent of how many items are already stored, which is the whole appeal versus a hash set whose per-operation cost depends on collision chains that grow with load. The no-deletion limitation is structural, not an implementation oversight: two different items can legitimately share one of their k bit positions, so unsetting a bit because one item is "removed" can silently flip another still-present item to a false negative, which breaks the Bloom filter's core guarantee. A Counting Bloom Filter avoids this by storing a small saturating counter (here capped at 15, fitting a 4-bit slot) at each position instead of a single bit: insert increments, remove decrements, and might_contain checks that every relevant counter is still above zero, so one item's removal only affects a shared position if that position's count truly drops to zero.

Worked example

n_expected, p_target = 1000, 0.01
bf = BloomFilter(n_expected, p_target)
print(f"BloomFilter sized: m={bf.m} bits, k={bf.k} hash functions")

inserted = [f"doc-{i}" for i in range(n_expected)]
for item in inserted:
    bf.insert(item)

false_negatives = sum(1 for item in inserted if not bf.might_contain(item))
print(f"false negatives among inserted items: {false_negatives} (must be 0)")

probes = [f"unseen-{i}" for i in range(20000)]
fp_count = sum(1 for item in probes if bf.might_contain(item))
print(f"empirical FP rate on {len(probes)} unseen probes: {fp_count/len(probes):.4f} (target was {p_target})")

cbf = CountingBloomFilter(n_expected, p_target)
cbf.insert("target-doc")
cbf.insert("unrelated-doc")
before = cbf.might_contain("target-doc")
cbf.remove("target-doc")
after = cbf.might_contain("target-doc")
unrelated_after = cbf.might_contain("unrelated-doc")
print(f"CountingBloomFilter: might_contain BEFORE remove = {before}, AFTER remove = {after}")
print(f"unrelated item still present after unrelated removal: {unrelated_after}")

Running this driver against the classes above prints:

BloomFilter sized: m=9586 bits, k=7 hash functions
false negatives among inserted items: 0 (must be 0)
empirical FP rate on 20000 unseen probes: 0.0109 (target was 0.01)
CountingBloomFilter: might_contain BEFORE remove = True, AFTER remove = False
unrelated item still present after unrelated removal: True

All 1,000 inserted document ids are correctly reported present (zero false negatives, as guaranteed), and probing 20,000 ids that were never inserted produces an empirical false-positive rate of 1.09%, reasonably close to the 1% design target (a single run at this size will naturally land somewhat above or below the target; the theoretical formula is an expectation, not a per-run guarantee). The Counting Bloom Filter demo is the meaningful correctness check for deletion: if remove() were broken (a no-op), might_contain would still read True after the call; instead it flips to False, and a separately inserted, unrelated item remains True after that removal, confirming counters correctly separate the two items' shared positions rather than one clobbering the other.

Trade-offs and pitfalls

A Counting Bloom Filter costs 4 to 8 times the memory of a plain Bloom filter for the same m (each slot is now several bits instead of one) purely to support deletion. It also introduces a new failure mode a plain Bloom filter cannot have: calling remove() on an item that was never actually inserted decrements counters that a genuinely present item may depend on, which can push a shared counter to zero and produce a false negative, something a plain Bloom filter's contract explicitly promises never happens. Counter saturation (hitting counter_max) is the other edge case: once a counter caps out, further increments are silently dropped, so a very hot bit position can under-count relative to true insert volume, meaning a later legitimate sequence of removes may not bring that counter back to exactly zero when it should.

Direct answer

A hash function is good for hash-table use if it is deterministic, distributes keys uniformly across
buckets, computes quickly, and has the avalanche property: changing even one bit of the input flips
roughly half the bits of the output, so similar-looking keys don't cluster together.

Structured elaboration

Determinism. The same key must always produce the same hash within one process/run, or the table
could never find something it already inserted. Note this is compatible with hashing being
randomized across different runs (Python salts string hashing per-process specifically to defeat
hash-flooding attacks), as long as it is stable within a run.

Uniform distribution. Across the actual key population you expect, outputs should spread evenly
over the output range. A hash function can be "random-looking" in general and still distribute one
particular workload badly, e.g. a hash that is uniform over arbitrary strings can still collide badly
if your real keys are all short numeric-looking strings that share a common prefix.

Speed. A hash function runs on every insert, lookup, and delete, so it needs to be cheap,
typically a handful of multiply/xor/shift operations, not something like SHA-256 (see below).

Avalanche effect. A well-mixed hash function should make output bits maximally sensitive to
input bits, so that keys differing by one character (e.g. "user1" vs "user2") land in unrelated
buckets rather than adjacent ones.

Cryptographic vs non-cryptographic choice. Non-cryptographic hash families (FNV, MurmurHash,
xxHash, CityHash) are built purely to satisfy the four properties above as cheaply as possible.
Cryptographic hashes (the SHA family) additionally guarantee collision resistance against an
adversary who is trying to find two inputs with the same output, and preimage resistance
(you can't work backward from the hash to the input). Those extra guarantees cost 10 to 100 times
more CPU per hash and are unnecessary for an ordinary hash table where the only failure mode you
care about is accidental clustering, not a cryptographic attacker trying to forge a signature.
The one place a cryptographic-strength hash earns its cost inside a hash table is exactly the
hash-flooding defense: SipHash (a keyed, non-cryptographic-speed but attack-resistant function) is
used specifically because an attacker who can choose keys should not be able to predict or engineer
collisions even knowing the algorithm, unless they also know the per-process secret key.

Worked example

A concrete case of "uniform in general, bad on your workload": if your keys are internal object IDs
like "obj_00001", "obj_00002", ..., "obj_00999", and your hash function only uses the last
few characters heavily (a genuinely weak, easy-to-write-by-accident hash such as
sum(ord(c) for c in s[-2:])), then IDs sharing the same last two digits collide constantly even
though the hash "looks fine" on random strings. A well-mixed hash (Python's built-in hash(),
MurmurHash, xxHash) processes the whole string and avalanches, so "obj_00001" and "obj_00002"
land in unrelated buckets.

Trade-offs and pitfalls

The most common pitfall is picking a hash function by its name or its Wikipedia reputation
("MurmurHash is a good hash") without checking it against the actual key distribution the table
will see, uniform-on-paper is not the same as uniform-on-your-data. The second common pitfall is
reaching for a cryptographic hash "to be safe," which pays a real latency cost across every
operation for a property (adversarial collision resistance under an unknown-algorithm attacker)
that a table almost never actually needs, since the algorithm is usually knowable and the real
defense against adversarial keys is a per-process secret seed (SipHash-style), not raw
cryptographic strength.

Direct answer

A hash-flooding attack exploits the fact that any hash function has SOME set of inputs that all
collide, if an attacker can discover or predict that set and control the keys your service inserts
(form fields, JSON object keys, query parameters), they can force a hash table's normal average-case
O(1) behavior down to worst-case O(n) per operation, turning ordinary-looking requests into a
denial-of-service. The fix is making the hash function unpredictable to the attacker, not just fast.

Structured elaboration

Why this is a real, historically-exploited class, not a theoretical concern. In 2011, researchers
demonstrated that PHP, Python, Ruby, Java, and other languages using predictable, unkeyed
non-cryptographic hash functions (many using variants of DJBX33A) for their built-in
associative-array/dict/hashmap types could be attacked with a small number of specially-crafted
request parameters, since the hash algorithm was fixed and known, an attacker could precompute a
large batch of colliding keys offline and submit them in one request, degrading that single request's
processing to O(n^2), enough to exhaust a server's CPU with a tiny amount of network traffic. This is
what made "hash flooding" a named, patched, CVE-worthy vulnerability class rather than a purely
academic observation.

Why the fix is unpredictability, not just switching hash functions. Simply picking a "better"
non-cryptographic hash function doesn't solve this: ANY fixed, publicly-known algorithm has some
colliding input set an attacker with enough compute can eventually find. The actual fix is making the
hash function's OUTPUT unpredictable to someone who doesn't know a secret, this is exactly what
SipHash (a keyed pseudorandom function, fast enough for everyday hash-table use, unlike a
cryptographic hash) and Python's per-process hash-randomization seed both do: an attacker who knows
the algorithm perfectly still cannot predict which inputs will collide without also knowing the
process's private seed, which changes every time the process restarts.

Defense in depth beyond the hash function itself. Randomized/seeded hashing closes the specific
attack vector, but production systems layer additional mitigations: capping the number of items a
single request is allowed to insert into any one table (bounding the attack's blast radius even if a
collision set were somehow found), and falling back to a balanced-tree bucket (as Java 8's
treeification does automatically) once any one bucket's chain crosses a length threshold, which caps
the WORST realistic cost per bucket at O(log n) even in the pathological case, independent of whether
the seeding defense holds.

Application level versus infrastructure level. The question specifically asks for both, and they
are genuinely different layers, not the same fix said twice. Application level means changes inside
the service's own code: seeded/keyed hashing (SipHash, per-process randomization), capping items per
request into any one table, and treeification of oversized buckets, all described above. Infrastructure
level means stopping or containing the damage BEFORE or AROUND the application code: enforcing a
request body size or object-key-count limit at the API gateway or reverse proxy, so a pathological
payload is rejected before it ever reaches the parsing code that would build the hash table; capping
per-request CPU time or wall-clock time via a container cgroup limit or a serverless function timeout,
so one pathological request cannot monopolize a shared worker process indefinitely even if every
application-level defense somehow failed; and rate-limiting or blocklisting the offending client at the
load balancer or WAF, which is also the fastest lever to pull during an active incident, well before a
code-level fix can be reviewed and deployed. Application-level fixes close the vulnerability; infrastructure-level
controls bound the blast radius while that fix ships and catch anything the application layer misses.

Worked example

Without a secret seed, an attacker who knows a service uses (for example) an unkeyed 32-bit additive
hash for its JSON parser's object keys could precompute, entirely offline and ahead of time, a list
of a few thousand strings that all hash to the identical bucket, then submit ONE request containing
an object with those few thousand keys. If the server's hash table has no randomized seed, every one
of those keys collides into the same bucket, insertion (and any subsequent lookup) becomes O(n) per
operation for that one bucket, turning what looks like an ordinary few-KB request into work
equivalent to n^2 comparisons. With a per-process random seed mixed into the hash, the SAME
precomputed key list, valid against one seed, produces a essentially-random, non-colliding
distribution against a different, unknown seed, the attacker's precomputation is worthless without
also knowing the seed.

Trade-offs and pitfalls

A common incomplete answer stops at "just use a better hash function", missing that the defense is
specifically about UNPREDICTABILITY to an attacker who may well know the exact algorithm, not
raw hash quality in the uniform-random-input sense. A second common gap: treating this purely as an
academic curiosity rather than citing the real, patched, multi-language incident class it is,
concretely acknowledging the history (2011, DJBX33A, PHP/Python/Ruby) demonstrates the difference
between reciting a mitigation checklist and understanding why the mitigation exists.