Hashing and Hash Tables Questions

Direct answer

With a fixed byte budget M instead of a fixed entry count, the cache needs to know each entry's size, not just its value, so eviction can be driven by "keep evicting least-recently-used entries until enough bytes are free" rather than "evict exactly one entry." An ordered hash map storing key -> (value, size) alongside a running used_bytes counter gives O(1) lookup and O(1) recency reordering, the same as a plain LRU (least-recently-used) cache, plus a loop on insert that evicts entries from the cold end until the new item actually fits.

Structured elaboration

Data structures and algorithm. Keep an ordered map (a doubly linked list plus hash index, collections.OrderedDict in Python or the manual equivalent) from key to (value, size), plus a running total used_bytes. get(key) looks up the value and moves the entry to the most-recently-used end, unchanged from a fixed-count LRU. put(key, value, size) first rejects outright any single item whose size exceeds the entire budget M (no amount of eviction can ever make it fit), then, if the key already exists, subtracts its old size from used_bytes before doing anything else (so growing an existing key does not silently double-count its old footprint), then evicts from the least-recently-used end in a loop, not just once, until used_bytes + size <= M, and only then inserts the new entry and adds its size to the running total.

Correctness when sizes vary. The two places a fixed-count LRU's usual logic breaks for variable sizes are exactly the two the algorithm above handles explicitly: a single large insert may need to evict several small entries, not one, so eviction has to be a loop bounded by the budget check, not a single popitem; and updating an existing key's size (larger or smaller) has to reconcile the byte accounting before the eviction loop runs, otherwise the running total silently drifts from reality.

Code

from collections import OrderedDict

class ByteBudgetLRU:
    def __init__(self, max_bytes: int):
        self._max_bytes = max_bytes
        self._used_bytes = 0
        self._store: "OrderedDict[str, tuple]" = OrderedDict()  # key -> (value, size)

    def get(self, key):
        if key not in self._store:
            return None
        self._store.move_to_end(key)
        value, _size = self._store[key]
        return value

    def put(self, key, value, size: int):
        if size > self._max_bytes:
            raise ValueError("single item larger than the entire budget")
        if key in self._store:
            _, old_size = self._store.pop(key)
            self._used_bytes -= old_size
        while self._used_bytes + size > self._max_bytes:
            self._evict_one()
        self._store[key] = (value, size)
        self._used_bytes += size

    def _evict_one(self):
        evicted_key, (_, evicted_size) = self._store.popitem(last=False)
        self._used_bytes -= evicted_size
        return evicted_key


if __name__ == "__main__":
    cache = ByteBudgetLRU(max_bytes=100)
    cache.put("a", "A" * 10, 40)
    cache.put("b", "B" * 10, 30)
    print("used bytes ->", cache._used_bytes)
    print("get a ->", cache.get("a") is not None)  # touches a, making b the LRU item

    cache.put("c", "C" * 10, 50)  # 70+50=120 > 100, must evict until it fits
    print("used bytes after adding c ->", cache._used_bytes)
    print("b evicted (LRU) ->", cache.get("b") is None)
    print("a survived (was MRU) ->", cache.get("a") is not None)
    print("c present ->", cache.get("c") is not None)

    try:
        cache.put("huge", "H", 500)
        raised = False
    except ValueError:
        raised = True
    print("oversized single item rejected ->", raised)

    cache.put("a", "A" * 20, 60)  # a grows from 40 to 60 bytes
    print("used bytes after growing a ->", cache._used_bytes, "(<=100) ->", cache._used_bytes <= 100)

    for i in range(20):
        cache.put(f"k{i}", i, 15)
    print("budget respected after 20 more varied inserts ->", cache._used_bytes <= 100)

Output (executed as shown):

used bytes -> 70
get a -> True
used bytes after adding c -> 90
b evicted (LRU) -> True
a survived (was MRU) -> True
c present -> True
oversized single item rejected -> True
used bytes after growing a -> 60 (<=100) -> True
budget respected after 20 more varied inserts -> True

Complexity

• get: O(1) average, a single hash lookup plus a constant-time move in the backing linked list.
• put: O(1) average work for the insert itself, plus the cost of however many entries it evicts. Each entry can be evicted at most once ever (it is removed from the structure the moment it is evicted), so across any sequence of n put calls the total eviction work is bounded by n, giving O(1) amortized cost per put, even though a single put inserting one very large item can, in the worst case, evict many entries at once and cost more than O(1) for that one call.

Trade-offs and pitfalls

• This design tracks a logical byte budget, not physical memory layout, so as implemented here (ordinary in-process objects plus a running counter) there is no physical fragmentation: each entry is its own independent object, and evicting one frees its memory back to the language runtime directly.
• Fragmentation becomes a real concern the moment the cache is backed by a fixed, contiguous byte arena instead (an off-heap buffer or shared-memory region, often chosen specifically to avoid garbage-collection overhead for large cached blobs). Freeing several small, non-contiguous slots by evicting cold entries does not guarantee a new, differently-sized item can actually fit into that freed space, even though the aggregate free-byte count is sufficient, exactly the external-fragmentation problem a general-purpose memory allocator has. The standard production fix is slab allocation (rounding each item up to the nearest of a small set of fixed size classes and only ever placing or evicting within same-size-class slots), which trades a bounded amount of internal fragmentation (wasted space within an oversized slot) for eliminating external fragmentation entirely, since any freed slot in a size class is guaranteed reusable by any other item in that same class.
• A single very large insert can evict a disproportionate share of the cache's useful working set in one call, since LRU eviction has no concept of "how much value am I giving up" versus "how much space do I need," only recency order. Rejecting any item above a stricter fraction of the total budget (not just above the full budget outright) is a common guardrail to bound how much of the cache one oversized insert can wipe out.
• A common wrong turn: forgetting to subtract an existing key's old size before recomputing whether a put fits, which either double-counts that key's footprint (causing unnecessary eviction) or under-counts it (letting used_bytes drift above the real budget over many updates); the fix above handles this by removing the old entry's byte contribution before running the eviction loop, verified directly by growing key a from 40 to 60 bytes and confirming used_bytes stays correct and within budget afterward.

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

An LRU (least-recently-used) cache gets O(1) get/put by combining a hash map, for instant lookup of
where a key lives, with a doubly linked list, ordered from most- to least-recently-used, so moving an
entry to the front or evicting the back is a constant-time pointer operation rather than a scan.

Structured elaboration

Why you need both structures, not just one. A hash map alone gives O(1) lookup but has no
concept of "order of use," so evicting the least-recently-used entry would require scanning every
entry to find it, O(n). A linked list alone gives O(1) reordering (splice a node to the front) but
finding a given key's node in the first place would require a scan, again O(n). Putting them together
gives each structure exactly what the other is missing: the map stores key -> node, so you can jump
straight to a node in O(1), then the list lets you move that node to the front, or drop the tail
node, in O(1) pointer rewiring.

The operations.

• get(key): look up the node via the map in O(1); if found, splice it out of its current list
  position and re-insert it at the front (it's now the most-recently-used); return its value.
• put(key, value): if the key exists, update its value and move it to the front exactly like get.
  If it's new, create a node, insert it at the front, add it to the map, and if this pushed the cache
  over capacity, remove the tail node (the true least-recently-used one) and delete its key from the
  map too, both structures must stay in sync on every mutation.

Why sentinel head/tail nodes simplify the code. Using two permanent dummy nodes (an empty head
and an empty tail) means every real node always has both a prev and a next that exist, so
insertion and removal never need special-cased branches for "is this the first/last real node,"
which is exactly where off-by-one linked-list bugs usually hide.

Worked example

class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=None, value=None):
        self.key, self.value, self.prev, self.next = key, value, None, None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}
        self.head = Node()       # most-recently-used sentinel
        self.tail = Node()       # least-recently-used sentinel
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _insert_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._insert_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._insert_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))     # accessing 1 makes it MRU, 2 is now LRU
cache.put(3, 3)          # over capacity: evicts key 2 (the LRU)
print(cache.get(2))      # -1: evicted
cache.put(4, 4)           # evicts key 1 (now LRU after 3 was inserted more recently)
print(cache.get(1))       # -1: evicted
print(cache.get(3))       # 3: still present
print(cache.get(4))       # 4: still present

Running this prints 1, then -1, then -1, then 3, then 4, in that order, exactly matching
the intended eviction sequence: accessing key 1 protects it temporarily, but once key 3 and key 4 are
both inserted after it, key 1 becomes the oldest and is the one evicted.

Thread-safety considerations for a multi-threaded SRE service

This exact implementation is NOT thread-safe as written. The danger is not just put, get looks
like a read but it mutates the linked list (_remove plus _insert_front on every call), so two
threads calling get on the SAME key concurrently are two unsynchronized writers to the same pointers,
not a safe concurrent read. Two threads racing through _remove/_insert_front at the same time can
interleave their pointer updates and corrupt the list, dropping a node, creating a cycle, or leaving
self.map pointing at a node no longer reachable from head, all without raising an exception, so the
corruption can go unnoticed until a much later, unrelated lookup misbehaves.

The standard fix, the same one used for any hot shared structure, is a single lock (a mutex) acquired
for the full duration of every get and put call, covering the map lookup and the linked-list
splice together as one atomic unit; because the critical section is small (a hash lookup plus a
constant number of pointer rewrites), lock hold time is short and a single lock is usually good enough
in practice. If lock contention itself becomes the bottleneck under high concurrency, shard the cache
by key hash into N independently-locked sub-caches (the same technique used to scale any single-locked
structure), accepting that eviction becomes locally-accurate per shard rather than a single, globally
exact least-recently-used ordering across the whole cache, the identical trade-off that applies when
extending this design with per-entry TTL and safe concurrent access, genuinely harder still, since two
threads racing on the same key's expiry versus its access need that same lock to avoid disagreeing
about whether the key is even still valid.

Trade-offs and pitfalls

The most common bug is forgetting to remove-then-reinsert on a get (only updating order on put),
which silently turns the cache into "least-recently-inserted" rather than "least-recently-USED."
The second common bug is updating the map and the list independently in a way that can partially
fail (e.g. an exception between the map update and the list update), leaving them desynced; using
the node object itself as the single source of truth for both key and value, as above, and updating
both structures adjacent to each other, minimizes that window.

Direct answer

A hash-based response cache needs four separate decisions: what goes into the key, what gets evicted when memory is tight, how staleness is bounded, and what changes once the cache is no longer sitting in a single process. Treat those as independent axes: conflating "eviction" with "invalidation" is the most common design mistake here.

Structured elaboration

Cache key composition. Include everything that changes the response: route template, path parameters, query parameters (sorted, so ?page=2&status=active and ?status=active&page=2 collide to the same key), the relevant subset of headers (tenant id, Accept-Language), and an API/schema version. Hash that canonical tuple with a fast non-cryptographic hash (xxHash or MurmurHash) rather than a cryptographic one: you need speed and uniform distribution, not preimage resistance.

Eviction under memory pressure. Least-recently-used (LRU: evict the entry that has gone longest untouched) is the default, built as a hash map plus a doubly linked list so both lookup and the recency update are O(1). If a single bulk scan (a report job hitting thousands of distinct keys once) should not be allowed to evict everything a real user needs, use a segmented cache: a small probationary segment for first-seen keys and a protected segment for keys accessed at least twice, so one-off scans age out of probationary without ever touching the protected set. Critically, gate eviction on an actual memory budget (bytes), not entry count: response payloads vary by orders of magnitude in size, so a 10,000-entry cap can still OOM if a handful of entries are large paginated lists.

Keeping it fresh. Combine a TTL (so worst-case staleness is bounded even if invalidation is missed) with active invalidation on writes: on a write, delete the cache key rather than trying to update it in place (update-then-cache races when a slow commit finishes after a fast concurrent read repopulates the cache with stale data). Embedding an upstream version or ETag in the key is a cheap third layer: a byte-level change to the underlying data naturally produces a new key with no explicit bust needed.

Once there is more than one instance. A single process's in-memory map has no relationship to another instance's map. Four real options, roughly cheapest to most consistent: (1) keep per-instance local caches with a short TTL and accept staleness bounded by that TTL; (2) move to one shared external cache (e.g. Redis) all instances query, trading a network hop for a single source of truth; (3) shard the keyspace across a cache tier with consistent hashing so each cache node owns a partition of keys, which also solves the "same key cached N times" memory waste; (4) a two-tier design, a small local L1 for latency plus a shared L2 for consistency, with a pub/sub invalidation broadcast so a write on one instance evicts the key from every L1. Within one instance, if request handling is itself multi-threaded, a single lock guarding the whole map serializes unrelated requests; shard the map into N independently-locked segments (the same idea Java's ConcurrentHashMap uses) so a write to key A never blocks a read of unrelated key B. At very large scale, even the LRU bookkeeping (moving a linked-list node on every touch) becomes contended; production caches like Redis instead sample a handful of random entries and evict the oldest-looking one by an approximate recency counter, trading a slightly worse eviction choice for removing that contention entirely.

Worked example

For GET /users/42/orders?status=active&page=2 with schema version 3, the key is built from the canonical string "GET|/users/{id}/orders|id=42|page=2|status=active|v=3" and hashed: key = xxhash64(canonical_string). Two requests differing only in query-param order produce the same canonical string and therefore the same key (a hit); a request after a schema bump to v=4 produces a different key (a clean miss, no explicit invalidation required).

Trade-offs and pitfalls

• No TTL ceiling: staleness becomes unbounded the moment any write path forgets to invalidate (a very common regression when a new mutation endpoint ships).
• Update-in-place on write invites the classic race described above; delete-then-lazy-repopulate avoids it at the cost of one extra miss per write.
• A cache key that omits a relevant query parameter serves the wrong data to some requests; one that includes something irrelevant (a request id) turns every request into a guaranteed miss.
• Entry-count eviction caps can both over-evict (many tiny entries) and under-evict (few huge entries) relative to actual memory pressure.

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.