Hashing and Hash Tables Questions

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

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 Count-Min Sketch (CMS) estimates how many times each item has appeared in a stream using a fixed
amount of memory regardless of how many distinct items there are, by maintaining a small 2D grid of
counters (depth d rows, width w columns) and, on update, incrementing one counter per row (chosen by
that row's own hash function); a query takes the MINIMUM of the d counters an item maps to, which is
provably never an underestimate and, with high probability, not far above the true count either.

Structured elaboration

Update. For item x with increment amount delta, compute d hash values h_1(x), ..., h_d(x), one
per row, each reduced modulo w to pick a column, and add delta to each of those d counters (one per
row). Different items can and will collide into the same column within any given row, that's the
whole source of the sketch's error.

Structured elaboration (continued)

Query. Return min over the d row-counters the item maps to. This is the key design idea: any
ONE row's counter for item x can be inflated by unrelated items that happened to collide into the
same column in that row, but it can never be DEFLATED below x's true count (since every update to x
always adds to that row's counter). Taking the min across d independently-hashed rows means the
estimate is only wrong if x collided with something heavy in EVERY row simultaneously, an
exponentially unlikely event as d grows, so the sketch trades a small, bounded, one-directional
(always-overestimate-never-underestimate) error for memory that stays constant no matter how many
distinct items appear.

How width and depth relate to epsilon and delta. Width w = ceil(e / epsilon) (where e is
Euler's number, about 2.718) controls how much any single row's collision error can inflate an
estimate, a bigger w means fewer collisions per row and thus a smaller per-row overestimate, epsilon
is the target bound on that overestimate as a fraction of the total stream count. Depth
d = ceil(ln(1/delta)) controls the PROBABILITY that the estimate exceeds that epsilon bound at all,
delta is the target failure probability, more rows means more independent chances to avoid the
unlucky all-rows-collided case, so the guarantee becomes "with probability at least 1-delta, the
estimate is within epsilon * total_count of the true count," entirely independent of how many
distinct items exist.

Worked example

For a stream you expect to have a total count of 10 million updates, wanting the estimate to be
within 0.1% of that total (epsilon = 0.001) with 99% confidence (delta = 0.01): width
w = ceil(e / 0.001) = ceil(2718.28...) = 2719 columns, depth d = ceil(ln(1/0.01)) = ceil(4.605) = 5 rows. That's a
grid of 2719 x 5 = 13,595 counters total, a few tens of kilobytes, to track frequency estimates for a
stream that could contain millions of distinct items, an amount of memory that does NOT grow with the
number of distinct items, only with your chosen epsilon and delta.

Trade-offs and pitfalls

The property most often gotten backwards: CMS estimates are always greater than or equal to the true
count, never less, so it is a strict upper bound with high-probability tightness, not a symmetric
"could be off in either direction" estimate the way, say, a random sample would be. This makes CMS
specifically well-suited for "find items whose true count is definitely at least X" (heavy-hitter
detection) but a poor fit for anything requiring an unbiased estimate of the exact count of any
single specific item, since the bias is always in the same, upward direction.

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).

Approach

An LRU (least-recently-used) cache needs O(1) lookup by key and O(1) reordering by recency, which is exactly what an ordered hash map gives for free: a structure that is simultaneously a hash map (for O(1) key lookup) and a doubly linked list (for O(1) move-to-end and remove-from-front). Python's collections.OrderedDict is built on exactly that combination, so get looks up the key and moves it to the most-recently-used end, and put inserts or updates, then evicts from the least-recently-used end whenever the cache exceeds capacity.

Code

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self._capacity = capacity
        self._store: "OrderedDict[int, int]" = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self._store:
            return -1
        self._store.move_to_end(key)  # mark as most recently used
        return self._store[key]

    def put(self, key: int, value: int) -> None:
        if key in self._store:
            self._store.move_to_end(key)
        self._store[key] = value
        if len(self._store) > self._capacity:
            self._store.popitem(last=False)  # evict least-recently-used


if __name__ == "__main__":
    cache = LRUCache(2)
    cache.put(1, 10)
    cache.put(2, 20)
    print("get(1) ->", cache.get(1))   # touches 1, making 2 the LRU entry
    cache.put(3, 30)                   # capacity 2 -> evicts key 2
    print("get(2) after eviction ->", cache.get(2))
    print("get(3) ->", cache.get(3))
    print("get(1) ->", cache.get(1))
    cache.put(4, 40)                   # evicts key 3 (1 was touched more recently)
    print("get(3) after second eviction ->", cache.get(3))
    print("get(1) ->", cache.get(1))
    print("get(4) ->", cache.get(4))
    print("final size never exceeds capacity ->", len(cache._store) <= 2)

Output (executed as shown):

get(1) -> 10
get(2) after eviction -> -1
get(3) -> 30
get(1) -> 10
get(3) after second eviction -> -1
get(1) -> 10
get(4) -> 40
final size never exceeds capacity -> True

Key points

• get is not a read-only operation on an LRU cache, it mutates the recency order (move_to_end), which matters directly for the concurrency discussion below.
• Java's built-in equivalent is LinkedHashMap, constructed with accessOrder=true and with removeEldestEntry overridden to return true once size exceeds capacity, giving the same automatic LRU eviction behavior without hand-rolling the linked list.
• Manual alternative: a hand-built doubly linked list plus a hash map from key to list node (the classic approach when no ordered-map built-in is available, or when extra per-entry metadata needs to live on the node itself). This is strictly more code for the same asymptotic behavior as OrderedDict/LinkedHashMap, and is usually only worth it when the language has no ordered-map primitive or the cache needs custom node-level behavior.

Complexity

• get and put: O(1) average, since both hashing to find a node and unlinking/relinking it in the backing doubly linked list are constant-time operations.
• Space: O(capacity), one entry per cached key up to the configured limit.

Edge cases

• Updating an existing key: handled by moving it to the end before overwriting its value, so it correctly counts as freshly used rather than being treated as new and separately evicting something else unnecessarily.
• Reading a key that was already evicted: returns -1 (verified above for key 2 after it was evicted, and again for key 3).
• Capacity exactly at the boundary: confirmed the store never exceeds the configured capacity of 2 entries across the whole sequence of operations above.
• A get changing which key is next in line for eviction: demonstrated directly, touching key 1 via get before inserting key 4 is what causes key 3, not key 1, to be evicted next.

Concurrency considerations

Neither OrderedDict nor LinkedHashMap is thread-safe, and the usual read/write split that works for simpler caches does not apply cleanly here, because get mutates the recency order, so it is effectively a write, not a safe concurrent read, even when it looks like a lookup. The straightforward fix is a single lock around every get and put call; because the critical section is small (a hash lookup plus a constant number of linked-list pointer updates), lock hold time is short and this is usually good enough. For higher throughput, the cache can be sharded by key hash into N independently locked sub-caches (the same idea used to reduce contention on any hot shared structure), at the cost of the eviction decision becoming local to a shard rather than a single, globally accurate least-recently-used choice across the whole cache; a key that is genuinely the coldest in the entire cache might still survive if it happens to live in a shard that is not currently under eviction pressure, while a merely moderately cold key in a busier shard gets evicted first. That trade-off, global LRU accuracy versus lock contention, is the central design decision once this cache needs to scale beyond a single lock.