Hashing and Hash Tables Questions

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

Doubling capacity gives amortized O(1) insertion because the total cost of all the copying done across n insertions is bounded by a geometric series that sums to O(n), a standard aggregate-analysis argument. A smaller growth factor like 1.5x keeps the same asymptotic O(1) amortized guarantee but changes both constants in opposite directions: it wastes less memory right after a resize but does strictly more total copying over the table's lifetime, which is why memory-constrained services sometimes deliberately choose a smaller factor despite the extra copying cost.

Structured elaboration

Formal proof: doubling gives amortized O(1)

Use the aggregate method. Suppose the table starts at capacity $C_0$ and doubles every time it fills: $C_0, 2C_0, 4C_0, \dots$ After $n$ insertions, the table has resized $r = \lceil \log_2(n/C_0) \rceil$ times. Each resize at capacity $2^{i}C_0$ copies all $2^{i}C_0$ existing elements. The total copying work across all resizes is

a geometric series that telescopes to strictly less than $2n$, that is, $O(n)$ total copying work for $n$ insertions. Adding the $n$ direct insertion costs (O(1) each, O(n) total) gives total work $O(n)$ for $n$ insertions, so the AMORTIZED cost per insertion, total work divided by $n$, is $O(1)$, even though any single insertion that triggers a resize costs $O(n)$ in that instant.

Alternative growth factors: 1.5x versus 2x

The same argument holds for any growth factor $g > 1$: the geometric series still telescopes to $O(n)$ total copying, so amortized O(1) holds for ANY fixed $g>1$, not just doubling. What changes is the CONSTANT inside that O(1), in two opposite directions:

• Time constant: total copying work relative to $n$ scales with $\frac{g}{g-1}$. This is LARGER for smaller $g$: at $g=2$, the constant is 2 (copy up to 2x the final size in aggregate); at $g=1.5$, the constant is 3 (copy up to 3x). Smaller growth factors resize more often and do MORE total copying over the table's life.
• Space constant: right after a resize to capacity $gC$ holding $C$ elements, the table is only $1/g$ full. At $g=2$, that is 50% full (up to half the allocated capacity is temporarily wasted); at $g=1.5$, that is about 67% full (only about a third wasted). Smaller growth factors waste LESS peak memory.

So doubling buys a cheaper amortized time constant at the cost of wasting up to half the table's capacity right after a resize; a smaller factor like 1.5x wastes less memory at the cost of a larger total-copying constant over the table's lifetime.

When a smaller growth factor is preferable

For a memory-constrained service, many small maps held simultaneously, or a hard per-process memory limit such as embedded or high-density multi-tenant deployments, the up-to-50%-wasted peak capacity of doubling is a real, direct memory cost multiplied across every live table. Trading some extra copying work (a CPU cost, generally cheaper and more elastic than a hard memory ceiling) for a tighter worst-case memory bound is the right trade when memory, not CPU, is the binding constraint.

Worked example (10 million keys)

Target: insert 10,000,000 keys, keeping the load factor at or below 0.75 at all times, starting from an initial capacity of 16 and doubling.

Minimum capacity needed to hold 10,000,000 keys at a 0.75 load factor: $10{,}000{,}000 / 0.75 \approx 13{,}333{,}334$. The smallest power of two at or above that is $2^{24} = 16{,}777{,}216$. Starting from $2^4=16$ and doubling to $2^{24}$ takes exactly

Total copying work across those 20 resizes (summing the capacity at each resize: $16+32+64+\dots+2^{23}$) is $2^{24}-16 = 16{,}777{,}200$ element-copies, about 1.68x the final key count of 10,000,000, confirming the amortized O(1) bound concretely: roughly 1.68 copy-operations per insertion on average, despite 20 individual resize events, several of which each cost millions of copies in that single instant.

Mitigating long pause times in production

• Pre-size when the target is knowable: if 10,000,000 is known or well-estimated ahead of time, constructing the table at capacity $2^{24}$ directly eliminates all 20 resizes and their pauses, at the cost of allocating the full capacity up front even before it is needed.
• Incremental (lazy) resizing: instead of copying the entire old table in one atomic step, keep both the old and new tables alive during a transition window and migrate a bounded number of entries (a few buckets) on each subsequent operation, spreading one large pause into many tiny ones; this is how some production key-value stores avoid a single stop-the-world copy.
• Smaller growth factor: reduces the SIZE of the worst individual pause (each resize copies less, since resizes happen more often but at a smaller jump), trading a few large pauses for more numerous, smaller ones, useful when the tail latency of one huge pause matters more than the higher aggregate resize count.
• Segmented structures: a table built from independently-sized segments, adding a new segment instead of reallocating and copying the whole table, avoids the "copy everything" pattern altogether, at the cost of a slightly more complex lookup path (checking the right segment).

Trade-offs and pitfalls

• Treating "amortized O(1)" as meaning "every insertion is fast" is the most common misreading of this proof; the guarantee is about the AVERAGE over many insertions, individual resize-triggering insertions are genuinely $O(n)$ in that instant, exactly why production services with strict per-operation latency budgets need the mitigations above, not just the amortized guarantee.
• Choosing a growth factor without a specific memory or latency constraint driving the choice is arbitrary; the analysis above only tells you the shape of the trade-off, the right point on it depends on which resource, memory or CPU/pause time, is actually scarce for the specific service.

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

Under the standard "uniform hashing" assumption (each of n keys independently, uniformly picks one of
m buckets), the expected number of keys in any one specific bucket is exactly n/m, the load factor,
which is why the expected cost of a chaining lookup (hash once, then scan that bucket's short chain)
is O(1 + n/m), constant so long as the load factor is kept bounded by resizing.

Structured elaboration

The balls-into-bins framing. Model each of the n keys as a ball thrown independently and
uniformly at random into one of m bins (buckets). For a SPECIFIC bin, define an indicator random
variable for each ball: it's 1 if that ball landed in this bin, 0 otherwise. Each indicator has
probability exactly 1/m of being 1 (uniform hashing assumption), and by linearity of expectation
(which holds regardless of whether the indicators are independent), the expected TOTAL count in that
one bin is simply the sum of n such indicators' expectations: n * (1/m) = n/m.

Why this justifies the O(1) average-case claim. A lookup for a key first computes its bucket
(O(1)) then scans that bucket's chain. The EXPECTED length of that chain, from the derivation above,
is n/m, the load factor. As long as the table resizes to keep n/m bounded by a small constant, expected lookup cost stays O(1) regardless of how large n
itself grows, the load factor, not the absolute entry count, is what determines expected cost.

What this proof does NOT claim. This is an EXPECTED (average) value across all buckets under a
uniformity assumption, it says nothing about the WORST bucket, which, even under perfectly uniform
hashing, will by chance hold noticeably more than the average (a distinct, sharper question about the WORST bucket rather than a typical one), and it says nothing at all about what
happens once the uniformity assumption itself is violated (a weak hash function, or an adversary
choosing keys), which is a different failure mode entirely, covered by worst-case-complexity analysis and hash-flooding-attack mitigations.

Worked example

import random
from collections import Counter

def bucket_zero_average_count(n, m, trials, seed=0):
    rng = random.Random(seed)
    counts = []
    for _ in range(trials):
        placements = [rng.randrange(m) for _ in range(n)]
        counts.append(placements.count(0))   # count landing in ONE specific bucket (bucket 0)
    return sum(counts) / len(counts)

n = m = 1000
avg = bucket_zero_average_count(n, m, trials=5000, seed=1)
print(f"n={n}, m={m}, theoretical expected count in bucket 0 (n/m) = {n/m:.3f}")
print(f"empirical average count in bucket 0 over 5000 trials      = {avg:.3f}")

Running this prints theoretical expected count in bucket 0 (n/m) = 1.000 and
empirical average count in bucket 0 over 5000 trials = 1.007, matching the linearity-of-expectation
derivation to within simulation noise (n/m simplifies to exactly 1 here since n = m = 1000). This
deliberately tracks ONE specific bucket across many independent trials, which is what the n/m
derivation actually claims. Averaging over all m buckets within a single trial instead (a tempting
shortcut) would be a hollow check: sum(counts.values()) always equals n by simple conservation, so
"average load across all buckets" prints exactly 1.000 even if every one of the n keys were forced
into bucket 0 by a completely broken, non-uniform hash function, it says nothing about whether the
placement was actually uniform.

Trade-offs and pitfalls

The most common mistake is conflating THIS result (expected load of a TYPICAL/specific bucket, n/m)
with the MAXIMUM load across all m buckets, which is provably, and often substantially, higher than
n/m even under perfectly uniform hashing (the balls-into-bins max-load result shows the maximum grows like Theta(log n / log log n) for n = m, meaningfully above the
constant average). A senior answer distinguishes these two claims explicitly rather than treating
"expected load per bucket" as if it also bounded the worst bucket you'd ever see.

Direct answer

Hash-table lookup, insertion, and deletion are O(1) on average, assuming keys spread roughly evenly
across buckets, but they degrade to O(n) in the worst case when many keys land in the same bucket,
because that bucket then behaves like a plain list you have to scan linearly.

Structured elaboration

Where the O(1) average comes from. If n keys spread uniformly across m buckets, each bucket holds
about n/m entries, the load factor, kept bounded by resizing. A lookup does one O(1) hash computation
plus a scan of that one bucket's roughly-constant-length contents.

What forces the worst case. Three distinct triggering conditions, each real:

1. A degenerate/weak hash function that maps many real keys to the same bucket regardless of
   intent (e.g. only reading the first character of a string key when most keys share a prefix).
2. An adversary who controls the keys. Even a well-designed general-purpose hash function has
   some set of inputs that all collide (pigeonhole principle guarantees this), and if an attacker
   can discover or brute-force that set (this is exactly what the 2011 hash-flooding disclosures
   exploited across PHP, Python, Ruby, and other languages: PHP and Perl specifically used the
   DJBX33A hash for this, while Python and Ruby each had their own similarly deterministic,
   unseeded string hash broken the same way), they can deliberately force every key into one
   bucket, turning every operation into an O(n) scan, a genuine denial-of-service vector (the mitigations are a deep topic in their own right).
3. A load factor left unbounded, i.e. the implementation simply never resizes.

How modern implementations mitigate this. Java's HashMap (since Java 8) treeifies a bucket
once its chain grows past 8 entries in a sufficiently large table, converting that one bucket's linked
list into a small balanced red-black tree, capping that bucket's worst case at O(log n) instead of
O(n), while leaving every other, non-degenerate bucket untouched. Python and other languages instead
lean on hash randomization (a per-process secret seed mixed into string hashing) so an attacker
cannot predict which inputs will collide without also knowing the secret seed, closing off attack
class 2 above without changing the underlying data structure at all.

Worked example

Concretely, for a chaining table with 8 buckets: if 100 keys spread perfectly evenly, each bucket
holds 12.5 entries (average-case O(1) relative to a further-scaled table, i.e. still small and
constant as the table resizes to keep this bounded). If instead all 100 keys were engineered to hash
into bucket 0, that one bucket now holds a 100-entry list and a lookup for the 100th key inserted
there requires scanning all 100 (or, in Java 8+, only up to a red-black tree's O(log 100) is approx 7
comparisons instead, once treeification's threshold of 8 is crossed).

Trade-offs and pitfalls

Stating "hash tables are O(1)" without qualification is the single most common shallow answer to this
question; a strong answer immediately volunteers the word "average-case" and can name at least one
concrete mechanism that breaks it. A second-level pitfall is thinking treeification "fixes" the
worst case universally, it only bounds the cost of ONE pathological bucket to O(log(bucket size)),
it does not prevent an attacker from still degrading overall throughput by forcing every key into
that single treeified bucket, it just caps how bad that specific bucket's cost gets.