Hashing and Hash Tables Questions

Direct answer

When two keys hash to the same bucket, you either let that bucket hold multiple entries (separate
chaining, usually a small linked list or dynamic array per bucket) or you find a different, empty
slot elsewhere in the same table (open addressing, via linear probing, quadratic probing, or
double hashing). Chaining is simpler and more forgiving of a bad hash function; open addressing is
more cache-friendly and memory-efficient when it works well.

Structured elaboration

Separate chaining. Each bucket is itself a small container (linked list, or a dynamic array/tree
once Java's HashMap treeifies a long chain). Insertion appends to the bucket's list; lookup hashes to
the bucket then scans its (usually very short) list; deletion is a normal list removal, no special
handling needed. Memory overhead is one pointer/node per entry beyond the raw key/value, but the
table degrades gracefully, a bad hash function just makes some chains longer, it never causes the
whole table to fail.

Open addressing. All entries live directly in the backing array; there is no auxiliary structure.
On a collision, the table computes an alternate slot via a probe sequence:

• Linear probing: try index+1, index+2, ... . Simple and extremely cache-friendly (the next slot
  is usually already in the same cache line), but suffers primary clustering: once a run of
  occupied slots forms, it tends to grow, since any key hashing anywhere inside the run has to probe
  through the whole thing.
• Quadratic probing: try index+1, index+4, index+9, ... . Spreads probes out faster, reducing
  primary clustering, at some cost to cache locality and at the risk of not visiting every slot
  unless the table size and quadratic step are chosen carefully.
• Double hashing: the probe step size itself comes from a second hash function, so different
  keys that collide at the same first slot follow different probe sequences, avoiding secondary
  clustering. This needs the step size to be coprime with the table size (its own dedicated
  question covers exactly this).

Deletion under open addressing is the sharp edge. You cannot simply clear a slot to "empty," or a
later probe sequence that walked past it looking for a still-present key would incorrectly stop early
and report the key missing. Implementations use a tombstone marker (a distinct third state:
occupied / tombstone / never-used) so probing keeps walking through tombstones, while insertion is
allowed to reuse a tombstone slot (covered in depth separately: it needs a dedicated tombstone marker rather than clearing the slot outright, and why tombstones must eventually be cleared by a full rehash).

Worked example

Table of capacity 8, linear probing, keys hash to indices [3, 3, 4, 3] for keys A, B, C, D in that
order:

• A -> slot 3 (empty, placed directly)
• B -> wants slot 3 (occupied by A), probes to slot 4 (empty, placed)
• C -> wants slot 4 (occupied by B), probes to slot 5 (empty, placed)
• D -> wants slot 3 (occupied), probes 4 (occupied), probes 5 (occupied), lands at slot 6

Four keys that only collided on their first choice ended up forming one contiguous run of length
four (slots 3 to 6), which is exactly primary clustering: every future key hashing into slots 3
through 6 now has to walk through this whole run. Under separate chaining, the same four keys would
simply form two short chains (bucket 3: [A, B, D]; bucket 4: [C]), no run, no clustering across
neighboring buckets.

Trade-offs and pitfalls

Open addressing needs the load factor kept meaningfully below 1 (commonly under 0.7 to 0.75) because
performance degrades sharply as the table fills, an empty slot becomes hard to find. Chaining
degrades far more gracefully and can even be pushed past a load factor of 1 (average chain length
just grows past one entry). The real-world default matters here: Java's HashMap uses chaining
(with treeification of long chains since Java 8), while Python's dict uses open addressing
internally, both are legitimate, widely-used production choices, so "which is better" depends on
whether you value graceful degradation under a bad hash function (chaining) or raw cache locality and
lower per-entry memory overhead when the hash function is trustworthy (open addressing).

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.

Direct answer

For n = 100,000,000 expected items and a target false-positive rate p = 1%, the standard formulas
give a bit-array size m of about 958.5 million bits (roughly 114.3 MiB) and k = 7 hash functions,
using m = -(n * ln(p)) / (ln 2)^2 and k = (m/n) * ln(2).

Structured elaboration

Where the formulas come from. The false-positive probability of a Bloom filter, after n
insertions into an m-bit array using k independent hash functions, is well-approximated by
$p \approx \left(1 - e^{-kn/m}\right)^{k}$
Minimizing this expression over k for fixed m and n (taking the derivative and setting it to zero)
gives the optimal number of hash functions,
$k = \frac{m}{n}\ln 2$
Substituting that optimal k back into the false-positive formula and solving for m in terms of a
target p gives the required bit-array size,
$m = -\frac{n \ln p}{(\ln 2)^2}$
These two formulas are used together: first size m for your target n and p, then derive the k that
makes that m/n ratio actually achieve close to that target.

Reading the result. ~9.6 bits per expected element is the headline number worth memorizing: at a
1% target false-positive rate, a Bloom filter costs a bit under 10 bits per item, dramatically less
than storing even a single byte per item, let alone a full key, which is exactly the space trade-off
Bloom filters exist to make.

Worked example

import math

def bloom_params(n: int, p: float):
    m = -(n * math.log(p)) / (math.log(2) ** 2)
    k = (m / n) * math.log(2)
    return math.ceil(m), round(k), m, k

n, p = 100_000_000, 0.01
m_bits, k_funcs, m_exact, k_exact = bloom_params(n, p)
print(f"n={n:,}  target p={p}")
print(f"m (bits, exact)   = {m_exact:,.1f}")
print(f"m (bits, ceiling) = {m_bits:,}")
print(f"m in MiB          = {m_bits/8/1024/1024:,.2f} MiB")
print(f"k (hash fns, exact) = {k_exact:.3f}  ->  k (rounded) = {k_funcs}")
print(f"bits per element    = {m_bits/n:.3f}")

# sanity check: plug the rounded m,k,n back into the false-positive formula
fp_check = (1 - math.exp(-k_funcs * n / m_bits)) ** k_funcs
print(f"false-positive rate with rounded k={k_funcs}: {fp_check:.5f}  (target was {p})")

This prints:

n=100,000,000  target p=0.01
m (bits, exact)   = 958,505,837.7
m (bits, ceiling) = 958,505,838
m in MiB          = 114.26 MiB
k (hash fns, exact) = 6.644  ->  k (rounded) = 7
bits per element    = 9.585
false-positive rate with rounded k=7: 0.01004  (target was 0.01)

The sanity check matters as much as the derivation: plugging the ROUNDED k = 7 (not the exact 6.644,
you can't have a fractional number of hash functions) back into the false-positive formula gives
1.004%, essentially exactly the 1% target, confirming the rounding didn't meaningfully cost you
accuracy here.

Bloom filter vs. exact hash set for membership testing

A hash set has zero false positives and supports deletion and enumeration, but its memory scales
with the actual bytes of every item stored: 100,000,000 items at a typical 50 bytes/entry (item plus
per-entry hash-table overhead) costs about 5.0 GB, versus the Bloom filter's fixed 114.26 MiB for the
same n, a roughly 42x saving. Prefer the hash set when you need exact answers with zero tolerance for
false positives, need to delete or enumerate items, or n is small enough that the memory difference
doesn't matter in practice. Prefer the Bloom filter when n is large enough that exact storage is the
actual bottleneck, a bounded false-positive rate is acceptable because the downstream cost of a rare
false positive is cheap, and you never need to list or remove members.

Trade-offs and pitfalls

The rounding step is the part candidates most often skip, quoting k = 6.644 as if you could implement
"6.644 hash functions." Rounding k is unavoidable, and the honest next step, which the sanity check
above performs, is verifying the ROUNDED k still meets your target, not just reporting the exact
theoretical value and stopping. A second pitfall: this whole calculation assumes n is known up front;
if the actual number of items inserted ends up meaningfully larger than the n you sized for, the
realized false-positive rate silently climbs well above your target, since m and k were fixed at
build time, this is exactly the size-planning risk that makes n a genuine input requiring a real
estimate, not a number to guess casually.

Approach

Quadratic probing is open addressing (every entry lives directly in one flat array, no linked chains) where a collision at the home slot is resolved by trying home + 1^2, home + 2^2, home + 3^2, ... modulo the table capacity, instead of the fixed stride double hashing would use. The quadratic step spreads consecutive colliding keys apart quickly, which avoids the long runs of adjacent occupied slots that plain linear probing (home + 1, home + 2, ...) produces (a problem known as primary clustering). Deletes cannot just null out a slot, because a later key may have probed past it; a tombstone marker keeps get probing through a deleted slot while letting put reclaim it.

Code (Java)

public class QuadraticProbingMap {
    private static final Object TOMBSTONE = new Object();
    private Object[] keys;
    private Object[] values;
    private int capacity, size, used;

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

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

    public void put(String key, Integer value) {
        if ((double) (used + 1) / capacity > 0.6) resize();
        int base = home(key), firstTombstone = -1;
        for (int i = 0; i < capacity; i++) {
            int slot = (int) (((long) base + i * i) % 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 base = home(key);
        for (int i = 0; i < capacity; i++) {
            int slot = (int) (((long) base + i * i) % capacity);
            if (keys[slot] == null) return null;
            if (keys[slot] != TOMBSTONE && keys[slot].equals(key)) return (Integer) values[slot];
        }
        return null;
    }

    public boolean remove(String key) {
        int base = home(key);
        for (int i = 0; i < capacity; i++) {
            int slot = (int) (((long) base + i * i) % 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) {
        QuadraticProbingMap m = new QuadraticProbingMap(11);
        m.put("x", 1); m.put("y", 2); m.put("z", 3);
        System.out.println("get x -> " + m.get("x"));
        System.out.println("get missing -> " + m.get("nope"));
        m.remove("y");
        System.out.println("get y after remove -> " + m.get("y"));
        m.put("w", 4);
        System.out.println("get w -> " + m.get("w"));
        System.out.println("get x still resolves past tombstone -> " + m.get("x"));
        for (int i = 0; i < 25; i++) m.put("k" + i, i * 5);
        System.out.println("size -> " + m.size() + " capacity -> " + m.capacity());
        boolean allCorrect = true;
        for (int i = 0; i < 25; i++) if (!Integer.valueOf(i * 5).equals(m.get("k" + i))) allCorrect = false;
        System.out.println("all 25 post-resize keys correct -> " + allCorrect);
        System.out.println("z survived resize -> " + (m.get("z") == 3));
        System.out.println("y stays deleted after resize -> " + (m.get("y") == null));
    }
}

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

get x -> 1
get missing -> null
get y after remove -> null
get w -> 4
get x still resolves past tombstone -> 1
size -> 28 capacity -> 47
all 25 post-resize keys correct -> true
z survived resize -> true
y stays deleted after resize -> true

Key points

• Collision resolution choice: quadratic probing was chosen over linear probing specifically to avoid primary clustering (long runs of adjacent full slots that make every new insertion near that run progressively more expensive), at the cost of a subtler risk covered below. It was chosen over chaining because the goal here is to keep every entry inside one contiguous array, which is more cache-friendly (fewer pointer chases) and avoids per-entry node allocation.
• Tombstones on delete: remove marks the slot with TOMBSTONE rather than null, so get keeps probing past it (confirmed above: x still resolves after y's slot becomes a tombstone), while put is free to reuse that slot for a new key (w reuses y's old slot).
• Resize and rehashing: capacity grows to the next prime at least double the old size once used (live entries plus tombstones) crosses 60% of capacity; every live entry is walked and reinserted, and tombstones are dropped in the process, reclaiming their space.
• Memory implications: open addressing stores keys and values directly in two flat arrays with no per-entry node object and no next-pointer, which is more memory-efficient per live entry than chaining (which pays for a node object per entry) as long as the load factor is kept reasonably low; the cost is that the array itself must always be sized somewhat larger than the live entry count (here, never let past 60% full), whereas chaining can, in principle, run at a load factor above 1.0 with only a linear degradation in bucket length.

Complexity

• Average case, put/get/remove: (O(1)), given a good hash and the load factor kept under the resize threshold.
• Worst case: (O(n)), a table with heavy clustering or many tombstones can force a long probe sequence.
• Resize: (O(n)) when triggered, but (O(1)) amortized per insert, by the same doubling argument as any doubling hash table: total rehashing work across all resizes up to (n) inserts is bounded by a constant multiple of (n).

Edge cases and pitfalls

• The quadratic-probing coverage limitation: for home + i^2 mod capacity with a prime capacity, i and capacity - i produce the same residue, so the probe sequence for i = 0, 1, 2, ... visits only about half of the table's slots before repeating, not all of them. A load factor of 0.6 is inside the danger zone for this: it is possible (though not certain, and it did not occur in the run above) for put to fail to find a free slot even though the table is well under 100% full, because the reachable half happens to be occupied. The safer engineering choice is either to cap the load factor nearer 0.5 for this exact probing formula, or use a probing sequence proven to cover every slot, such as triangular-number probing (i(i+1)/2) on a power-of-two-sized table.
• Deleting then reusing a slot for an unrelated key: must not break lookups for keys whose probe sequence passes through that slot (verified above).
• A key that was never inserted: the probe sequence hits an empty (null) slot and both get and remove correctly report absence.
• A table saturated with tombstones but few live entries: resizing on used, not size, prevents probe sequences from silently degrading even when the map looks small from the outside.

Approach

Use an array of buckets (a fixed-size list), where each bucket is itself a small list of (key, value) pairs. To find a key, hash it, reduce it modulo the number of buckets to pick a bucket index, then scan that one short list for a matching key (separate chaining: collisions are handled by letting multiple entries share one bucket, rather than probing elsewhere in the array). Track how full the table is (the load factor, live entries divided by bucket count) and double the bucket array once it crosses 0.75, redistributing every existing entry into the new, larger array so buckets stay short.

Code

class ChainingHashMap:
    def __init__(self, capacity=8):
        self._capacity = capacity
        self._size = 0
        self._buckets = [[] for _ in range(self._capacity)]

    def _index(self, key):
        return hash(key) % self._capacity

    def put(self, key, value):
        idx = self._index(key)
        bucket = self._buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)   # update in place
                return
        bucket.append((key, value))
        self._size += 1
        if self._size / self._capacity > 0.75:
            self._resize()

    def get(self, key):
        idx = self._index(key)
        for k, v in self._buckets[idx]:
            if k == key:
                return v
        return None

    def remove(self, key):
        idx = self._index(key)
        bucket = self._buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self._size -= 1
                return True
        return False

    def _resize(self):
        old_buckets = self._buckets
        self._capacity *= 2
        self._buckets = [[] for _ in range(self._capacity)]
        self._size = 0
        for bucket in old_buckets:
            for k, v in bucket:
                self.put(k, v)

    def __len__(self):
        return self._size


if __name__ == "__main__":
    m = ChainingHashMap(capacity=4)
    m.put("apple", 1)
    m.put("banana", 2)
    m.put("cherry", 3)
    print("get apple ->", m.get("apple"))
    print("get missing ->", m.get("no_such_key"))

    m.put("apple", 99)
    print("get apple after overwrite ->", m.get("apple"))

    removed = m.remove("banana")
    print("remove banana ->", removed, "| get banana after remove ->", m.get("banana"))

    for i in range(20):
        m.put(f"key{i}", i * 10)
    print("size after 20 more inserts ->", len(m))
    print("capacity after growth ->", m._capacity)
    all_correct = all(m.get(f"key{i}") == i * 10 for i in range(20))
    print("all 20 post-resize keys still correct ->", all_correct)
    print("cherry survived resize ->", m.get("cherry") == 3)
    print("get on never-inserted key returns None ->", m.get("zzz_absent") is None)

Output (executed as shown, capacity starts at 4):

get apple -> 1
get missing -> None
get apple after overwrite -> 99
remove banana -> True | get banana after remove -> None
size after 20 more inserts -> 22
capacity after growth -> 32
all 20 post-resize keys still correct -> True
cherry survived resize -> True
get on never-inserted key returns None -> True

Key points

• put on an existing key overwrites its value in place rather than appending a duplicate entry; that scan-then-overwrite check is what makes put idempotent for repeated keys.
• remove returns False for a key that was never present instead of raising, so callers can check the result rather than wrapping every call in a try/except.
• The resize walks the old buckets and calls self.put again for every surviving entry, which is what re-distributes entries across the new, larger bucket count (a key's bucket index depends on capacity, so it generally changes when capacity changes).
• hash(key) % self._capacity is only safe because the prompt guarantees hashable keys; a custom class used as a key would need a correct __hash__/__eq__ pair (equal objects must hash equally) for this to behave correctly.

Complexity

• Average case, all three operations: (O(1)). With a good hash function and a load factor kept under 0.75 by resizing, each bucket holds a small constant number of entries on average, so scanning one bucket is constant time.
• Worst case: (O(n)), if every key collides into the same bucket (a pathological or adversarial hash function), the table degrades to one long list and every operation becomes a linear scan.
• Resize: (O(n)) when it happens (copies every entry), but it happens only when size crosses a growing threshold, so the amortized cost added to any single put stays (O(1)) averaged over a sequence of inserts.

Edge cases

• Updating an existing key: handled by the in-bucket scan in put, which finds the match and overwrites rather than duplicating.
• Removing a key that is not present: returns False rather than raising, verified above (remove is only demonstrated on a present key here, but the loop structure is identical to get's not-found path, which the test above confirms returns None).
• Getting a key that was never inserted: returns None, confirmed by the final assertion in the demo.
• Two different keys landing in the same bucket: correctness still holds because the bucket scan compares full keys with ==, not just the bucket index; only performance degrades, not correctness.
• Resizing mid-lifecycle: the demo forces a resize (capacity grows from 4 to 32) and confirms every one of the 22 live keys, old and new, still resolves correctly afterward.