Hashing and Hash Tables Questions

Direct answer

Double hashing resolves a collision by computing the NEXT probe step size from a second hash
function, h2(key), instead of always stepping by a fixed amount, so two keys that collide at the
same first slot follow different probe sequences afterward, avoiding the clustering that plagues
linear and (to a lesser extent) quadratic probing.

Structured elaboration

The probe formula. The i-th probe index is typically (h1(key) + i * h2(key)) % capacity. Unlike
linear probing (step size always 1) or quadratic probing (step size grows as i^2, same for every
key), here the step size itself, h2(key), is different for each key. Two keys that happen to share
the same h1 value only continue to collide with each other if they ALSO happen to share the same
h2 value, a much rarer coincidence, which is exactly why double hashing avoids secondary clustering
(quadratic probing's own weak point: same first collision implies the identical full probe sequence
for every colliding key).

The one hard constraint: h2 must be coprime with the table capacity. If h2(key) and capacity
share a common factor g > 1, the probe sequence (h1 + i*h2) % capacity only ever visits
capacity / g distinct slots before repeating, no matter how many times you probe, so it can miss
slots that are genuinely empty. The standard fix is to guarantee h2(key) is always coprime with the
capacity, either by choosing capacity to be a prime number (so any h2 in [1, capacity-1] is
automatically coprime with it), or by constructing h2 to always return an odd number when capacity
is a power of two.

Worked example

def h2(key, capacity):
    # A standard construction that guarantees coprimality with a power-of-two capacity:
    # any odd number is coprime with a power of two.
    return 1 + (hash(key) % (capacity - 1)) | 1   # forces the result to be odd

def probe_sequence(key, capacity, limit=None):
    h1 = hash(key) % capacity
    step = h2(key, capacity)
    limit = limit or capacity
    seq = [(h1 + i * step) % capacity for i in range(limit)]
    return seq

capacity = 16  # power of two
for k in ["alpha", "beta", "gamma"]:
    seq = probe_sequence(k, capacity)
    print(f"{k}: h1={seq[0]}, step={h2(k, capacity)}, first 5 probes={seq[:5]}, "
          f"visits all {capacity} slots exactly once: {len(set(seq)) == capacity}")

Running this shows each key gets its own first slot AND its own step size (since h2 depends on the
key), and confirms len(set(seq)) == capacity is True for every key, i.e. each key's full probe
sequence really does eventually visit every one of the 16 slots exactly once (no slot is skipped, and
none is revisited before all others are covered), which is precisely the guarantee that a coprime
step size provides.

Trade-offs and pitfalls

The pitfall interviewers specifically probe for is picking h2 carelessly, e.g. h2(key) = hash(key) % capacity with no adjustment: if capacity is even and that expression happens to be even too, the
probe sequence gets stuck cycling through only the even-indexed slots (or only odd), silently halving
the table's effective capacity for that key, a subtle bug that passes casual testing (small load
factors rarely reveal it) and only surfaces as mysterious "table full" failures well before the table
is actually full.

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

As the on-call SRE, the first thing to confirm is exactly what the heap snapshot already implies: the leak is in the KEY objects themselves, not the cached values, since a dict key must already be hashable, meaning these "large nested structures" are big tuples-of-tuples or similarly immutable data, never raw lists or dicts (those would have raised a TypeError on insertion and could never have reached the heap as keys). That distinction decides whether the fix is "evict more aggressively" or "stop storing so much per key", and it's the latter here.

Structured elaboration

Root-cause steps. First, use a heap snapshot (tracemalloc, objgraph, or a core dump with a memory profiler) to confirm which objects actually dominate retained size, the problem statement already points at the key objects, but this should be verified, not assumed, before choosing a fix. Second, since dict keys must be hashable, identify what's actually inside these tuples: commonly a full request context, a serialized feature vector, or an entire parameter set that got tupled up wholesale as a convenience, rather than a small derived identifier. Third, distinguish unbounded growth (a plain {} used as a memoization cache with no maxsize, accumulating a new large key on every distinct call forever) from a bounded cache whose per-entry footprint alone already exceeds budget, these are different bugs with different fixes. Fourth, check for near-duplicate-key cardinality explosion: if two calls that are semantically the same request produce different keys because something incidental (a timestamp, a request id) is embedded in the tuple, both cache hit rate collapses toward zero AND every distinct call permanently grows the dict.

Immediate mitigations, no full restart. If any operational hook exists (an admin endpoint, a signal handler, or attaching to the live process with a tool like py-spy dump or an injected REPL) that can call cache.clear() on the offending dict, use it first, it's the fastest way to reclaim memory and buy time. If no such hook exists, a graceful, rolling restart of just the affected worker behind the load balancer (draining traffic first) is a legitimate immediate mitigation, distinct from an uncontrolled crash-restart of the whole fleet. If horizontally scaled, temporarily shed load or scale out more replicas to slow the rate of new large keys accumulating while the real fix ships.

Longer-term fixes. Replace the large tuple key with a compact digest (a fixed-size hash of a canonical serialization of the same content) as the actual dict key, so key-storage cost stops scaling with what's being cached. Add a real eviction policy with a bounded size (functools.lru_cache(maxsize=...) or a proper cache library) if the dict was being used as an unbounded memoization cache, an unbounded plain dict used as a cache is itself the root design bug, independent of key size. Audit for and strip anything from the key that doesn't actually change the cached result (timestamps, request ids, connection objects), so semantically identical calls collapse to the same key.

Worked example

import tracemalloc, hashlib

def make_large_key(request_id):
    return (request_id, tuple((f"field{i}", i * request_id) for i in range(500)))

N = 3000
tracemalloc.start()
naive_cache = {}
for req_id in range(N):
    naive_cache[make_large_key(req_id)] = f"result-for-{req_id}"
naive_current, naive_peak = tracemalloc.get_traced_memory()
tracemalloc.stop()

tracemalloc.start()
fixed_cache = {}
for req_id in range(N):
    context = tuple((f"field{i}", i * req_id) for i in range(500))
    digest = hashlib.blake2b(repr(context).encode(), digest_size=16).hexdigest()
    fixed_cache[digest] = f"result-for-{req_id}"
fixed_current, fixed_peak = tracemalloc.get_traced_memory()
tracemalloc.stop()

print(f"naive cache (key = full nested tuple): peak = {naive_peak/1024:.1f} KiB, current = {naive_current/1024:.1f} KiB")
print(f"fixed cache (key = 16-byte digest):     peak = {fixed_peak/1024:.1f} KiB, current = {fixed_current/1024:.1f} KiB")
print(f"reduction in resident (current) key-storage memory: {(1 - fixed_current/naive_current) * 100:.1f}%")

# Correctness check: sampled lookup on both caches for the same request id
sample_id = 1234
sample_context = tuple((f"field{i}", i * sample_id) for i in range(500))
naive_value = naive_cache[(sample_id, sample_context)]
sample_digest = hashlib.blake2b(repr(sample_context).encode(), digest_size=16).hexdigest()
fixed_value = fixed_cache[sample_digest]
print(f"naive lookup: {naive_value}, fixed lookup: {fixed_value}, match: {naive_value == fixed_value}")

Output for N = 3,000 distinct requests, each with a 500-field nested context tuple:

naive cache (key = full nested tuple): peak = 224364.2 KiB, current = 224360.2 KiB
fixed cache (key = 16-byte digest):     peak = 631.4 KiB, current = 587.2 KiB
reduction in resident (current) key-storage memory: 99.7%
naive lookup: result-for-1234, fixed lookup: result-for-1234, match: True

Both caches return the identical value for the same sampled request id (result-for-1234), confirming the digest swap changes only the key-storage footprint, not correctness, while cutting resident key memory by 99.7% in this pinned scenario.

Trade-offs and pitfalls

Switching to a digest key trades a vanishingly small, but nonzero, risk of hash collision between two genuinely different contexts for a large memory win, acceptable for a cache (a false hit just returns a slightly wrong cached result, self-correcting on the next real miss or TTL expiry) but NOT acceptable anywhere that same key is treated as a durable, must-never-collide identifier. Clearing the cache as an immediate mitigation is a blunt instrument: it evicts every genuinely useful entry along with the problem, causing a real cache-miss spike against whatever backs the cache, which itself needs to be capacity-planned for rather than assumed free.

Direct answer

Extending an LRU (least-recently-used) cache with per-entry time-to-live (TTL, a lifespan after which an entry is no longer considered valid) means treating expiry and eviction as two independent mechanisms layered on the same structure: TTL decides whether an entry is even valid to serve at all, LRU decides who gets removed when the cache is full, regardless of whether that entry's TTL has expired yet. Safe concurrent access comes from sharding the cache into N independently locked pieces by key hash, so unrelated keys never contend for the same lock, rather than one global lock serializing every request. The one genuine race to guard against is a reader and an expiry-driven cleanup touching the same key at the same instant, which a single lock per shard around each operation's full check-then-mutate sequence eliminates by construction.

Structured elaboration

Data structures. Per shard: an ordered map (a doubly linked list plus a hash index, or collections.OrderedDict in Python) storing key -> (value, expires_at). get first checks expires_at against the current time; if expired, the entry is deleted and treated as a miss, never served stale. If still valid, it is moved to the most-recently-used end, same as a plain LRU. put inserts or updates the entry with a fresh expires_at, then evicts from the least-recently-used end while the shard is over capacity, exactly as a TTL-unaware LRU would, an unexpired entry can still be evicted early purely for space if it is cold enough.

Locking and sharding to minimize contention. A single lock around the whole cache serializes every request regardless of which key it touches, the same contention problem as a naive shared counter. The fix is the same: partition keys across N shards by hash(key) % N, each with its own lock, so two threads touching different shards never block each other; within a shard, the critical section (a dict lookup, a move, maybe an eviction) is small enough that a simple mutex around the whole operation is both correct and fast, a lock-free linked-list-based LRU is real engineering effort that rarely pays for itself compared to just adding more, smaller shards.

Eviction rules on TTL expiry. Two independent triggers remove an entry: lazily, on access, if its expires_at has passed; and capacity-driven, on put, evicting the least-recently-used entry regardless of that entry's own TTL state once the shard is full. A background sweep thread that proactively scans for and removes expired-but-never-accessed entries is an optional memory-hygiene addition, not a correctness requirement, lazy expiry alone already guarantees an expired entry is never served, it just might sit unreclaimed in memory until LRU pressure or a sweep removes it.

Race conditions between expiry and access. Because the expiry check and the touch-or-evict mutation both happen inside the same lock acquisition as one atomic operation, no other thread on that shard can observe a half-expired state in between. Two remaining subtleties matter: use a monotonic clock (one that only ever moves forward, unaffected by wall-clock adjustments) for expiry comparisons, since a wall-clock adjustment (an NTP correction, a daylight-saving shift) can jump time backward and silently corrupt TTL math; and treat the exact boundary consistently, an access at precisely expires_at should be treated as expired, not as a coin flip.

Code

import threading, time
from collections import OrderedDict

class TTLLRUCache:
    def __init__(self, capacity, default_ttl):
        self._capacity = capacity
        self._default_ttl = default_ttl
        self._store = OrderedDict()  # key -> (value, expires_at)
        self._lock = threading.Lock()

    def get(self, key, now=None):
        now = time.monotonic() if now is None else now
        with self._lock:
            entry = self._store.get(key)
            if entry is None:
                return None
            value, expires_at = entry
            if now >= expires_at:
                del self._store[key]
                return None
            self._store.move_to_end(key)
            return value

    def put(self, key, value, ttl=None, now=None):
        now = time.monotonic() if now is None else now
        ttl = self._default_ttl if ttl is None else ttl
        with self._lock:
            if key in self._store:
                del self._store[key]
            self._store[key] = (value, now + ttl)
            self._store.move_to_end(key)
            while len(self._store) > self._capacity:
                self._store.popitem(last=False)


class ShardedTTLLRUCache:
    def __init__(self, shard_count, capacity_per_shard, default_ttl):
        self._shards = [TTLLRUCache(capacity_per_shard, default_ttl) for _ in range(shard_count)]
        self._shard_count = shard_count

    def _shard_for(self, key):
        return self._shards[hash(key) % self._shard_count]

    def get(self, key, now=None):
        return self._shard_for(key).get(key, now=now)

    def put(self, key, value, ttl=None, now=None):
        self._shard_for(key).put(key, value, ttl=ttl, now=now)


if __name__ == "__main__":
    # basic TTL expiry
    cache = TTLLRUCache(capacity=2, default_ttl=10)
    cache.put("a", 1, now=0)
    print("get a at t=5 (not expired) ->", cache.get("a", now=5))
    print("get a at t=15 (expired, ttl=10) ->", cache.get("a", now=15))

    # LRU eviction independent of TTL (long ttl so eviction is purely LRU-driven)
    cache2 = TTLLRUCache(capacity=2, default_ttl=100)
    cache2.put("x", 100, now=0)
    cache2.put("y", 200, now=1)
    cache2.get("x", now=2)          # touch x -> y becomes LRU
    cache2.put("z", 300, now=3)     # evicts y (LRU), not due to TTL (ttl=100, still valid)
    print("y evicted by LRU (not TTL) ->", cache2.get("y", now=4) is None)
    print("x survived ->", cache2.get("x", now=4) == 100)

    # concurrency check: 16 threads, 200 put-then-get round trips each, shared 8-shard cache
    shared = ShardedTTLLRUCache(shard_count=8, capacity_per_shard=64, default_ttl=1000)
    errors = []

    def worker(tid):
        for i in range(200):
            key = f"t{tid}-{i}"
            shared.put(key, (tid, i), now=0)
            val = shared.get(key, now=0)
            if val != (tid, i):
                errors.append((key, val))

    threads = [threading.Thread(target=worker, args=(t,)) for t in range(16)]
    for th in threads:
        th.start()
    for th in threads:
        th.join()
    print("concurrent put/get across 16 threads, errors ->", len(errors))

    # exact boundary: an access at precisely expires_at counts as expired
    cache3 = TTLLRUCache(capacity=2, default_ttl=1.0)
    cache3.put("k", 42, now=0.0)
    print("exactly-at-expiry (t=1.0) counts as expired ->", cache3.get("k", now=1.0) is None)

Output (executed as shown, using an injected clock so TTL behavior is deterministic and reproducible):

get a at t=5 (not expired) -> 1
get a at t=15 (expired, ttl=10) -> None
y evicted by LRU (not TTL) -> True
x survived -> True
concurrent put/get across 16 threads, errors -> 0
exactly-at-expiry (t=1.0) counts as expired -> True

The concurrency check ran 16 threads, each performing 200 put-then-get round trips against a shared 8-shard cache, and confirmed every value was read back exactly as written with zero errors, evidence the sharded locking is actually safe under real concurrent access, not just single-threaded correctness.

Trade-offs and pitfalls

• Lazy-only expiry can leave cold, expired entries resident indefinitely if the cache has generous capacity and that key is never looked up again; add a background sweep if bounding memory tightly matters more than the extra CPU cost of scanning.
• Shard count is a real tuning knob, not a fixed choice. Too few shards under-spreads lock contention; too many wastes memory on mostly-empty per-shard structures and adds bookkeeping overhead.
• Distributed sharding is the same idea one layer up. The identical hash-the-key-to-a-shard principle extends from in-process locks to independent nodes in a distributed cache: shard by consistent hashing across nodes so the cache's total capacity and throughput scale past one machine, with a routing layer (client-side or proxy-side) sending each request to the node that owns its key's shard.
• Persistence across restarts should stay proportionate to what TTL data actually needs. Since every entry already has a bounded lifespan, a periodic best-effort snapshot to disk or an external store, reloaded at startup and immediately filtered to discard anything whose expires_at has already passed relative to current wall-clock time, is sufficient; treating this like a database's durability guarantee (distributed consensus, write-ahead logs) is usually over-engineering for data that was always meant to expire.
• A common wrong turn: using wall-clock time (time.time()) instead of a monotonic clock for TTL comparisons. It works in every normal test run and fails exactly once, silently, during a real clock adjustment in production, which is precisely why it is easy to ship and hard to catch without deliberately testing for it.

Direct answer

For small integer keys in a range 0..K, a direct-indexing array wins on raw lookup speed and
cache locality whenever the keys are DENSE (most of the range is actually used); a hash map wins
on memory whenever the keys are SPARSE (only a small fraction of the range is present), because
an array must pay for every slot in the range whether or not it holds a key, while a hash map
only pays for the keys that actually exist.

Structured elaboration

Dense case: prefer the array. If nearly every value in 0..K is a real key, a direct-index
array gives true O(1) lookup with no hashing step, no collision handling, and excellent cache
locality (sequential or nearby accesses land on adjacent memory, which the processor can
prefetch). This is strictly better than a hash map in the dense case: same or better time
complexity, no hashing overhead, no memory wasted on a mostly-empty array (since it is mostly
FULL by assumption).

Sparse case: prefer the hash map. If only a small fraction of 0..K is actually present
(the question's example: K = 1e9 but only 1e6 keys present, a 0.1% occupancy), a direct-index
array must still allocate all K slots, most of which are wasted space holding nothing. A hash
map instead allocates space roughly proportional to the number of keys actually present, at the
cost of a hashing step per lookup (still O(1) average) and slightly worse cache locality than
sequential array access (though still far better than, say, a tree).

The crossover point. As occupancy rises from sparse toward dense, there is a break-even
density where the array's fixed K-sized cost stops being worse than the hash map's
per-entry cost; above that density, the array becomes the more memory-efficient choice again,
in addition to already being the faster one. Where exactly that crossover sits depends on the
per-entry overhead of the specific hash map implementation you are using, which is worth
measuring rather than assuming.

Update patterns. Both structures support O(1) average insert and update for a key already
within range. The practical difference under updates is less about complexity and more about
whether new keys can appear OUTSIDE the originally assumed range K: an array sized for K at
allocation time cannot cheaply grow past K without a full reallocation and copy, while a hash
map's amortized resizing (doubling capacity and rehashing existing entries once load factor
crosses a threshold) handles arbitrary growth naturally, since it was never tied to a fixed K
in the first place.

Worked example

import sys

K = 1_000_000_000
present = 1_000_000
dense_array_bytes = K * 4  # int32 slots

sample = {i: i for i in range(100_000)}
bytes_per_entry = sys.getsizeof(sample) / len(sample)
hashmap_bytes = present * bytes_per_entry

print(dense_array_bytes, hashmap_bytes, dense_array_bytes / hashmap_bytes)

For K = 1{,}000{,}000{,}000 (1e9) with int32 slots, a dense direct-index array needs
4{,}000{,}000{,}000 bytes (about 3.73 GiB), allocated regardless of occupancy. Measuring a real
Python dictionary's actual memory footprint (sys.getsizeof) for 100,000 int-to-int entries
gives about 52.4 bytes per entry for the hash table's backing structure; extrapolating that
measured per-entry cost to the question's 1{,}000{,}000 present keys gives roughly 50 MiB for
the hash map, versus 3.73 GiB for the array, about 76 times more memory for the array at this
0.1% occupancy. Solving for where the array stops being the memory loser (dense_array_bytes <= present_entries * bytes_per_entry) with these measured numbers gives a break-even around 7.6%
occupancy: below that density, the hash map wins on memory; above it, paying for the full K
slots up front costs less than the hash table's per-entry overhead.

Trade-offs and pitfalls

• "Small integer keys" is doing real work in the question. This comparison is specific to
  integer keys in a bounded range; it does not generalize to string or composite keys, which have
  no natural direct-index mapping at all.
• The measured 76x and 7.6% break-even numbers above are specific to this demo's assumptions
  (int32 array slots, a particular runtime's dictionary overhead); recompute for your actual
  value type and hash-map implementation rather than treating these as universal constants.
• A common mistake is defaulting to a hash map "to be safe" even when the key range is known,
  small, and dense, giving up the array's simplicity and cache-locality advantage for no real
  benefit.
• The reverse mistake, defaulting to a huge array because the key TYPE happens to be an
  integer, is exactly the failure mode the sparse case in this question is testing for.