Hashing and Hash Tables Questions
How hash tables and hash-based structures work internally, and how to reason about their performance and correctness. Covers hash function properties (determinism, uniform distribution, speed, avalanche effect), cryptographic versus non-cryptographic hash choices, collision resolution (separate chaining, open addressing: linear probing, quadratic probing, double hashing, Robin Hood hashing, cuckoo hashing), load factor and amortized-cost resizing, and what makes an object hashable (the __hash__/__eq__ contract, immutability, custom composite keys). Covers hash-map-backed cache design (LRU and LFU eviction, TTL) and thread-safe concurrent hash maps (lock striping, CAS-based updates, safe concurrent resizing). Also covers hash-based structures beyond arrays and strings: consistent hashing for distributed routing and sharding, hash joins, hash-flooding and algorithmic-complexity security attacks and their mitigations, and probabilistic membership/cardinality structures such as Bloom filters, Cuckoo filters, Count-Min Sketch, and HyperLogLog. Excludes using a hash map purely as an optimization trick inside an array or string problem (two-sum, group anagrams, longest substring without repeating characters); that pattern belongs to Arrays, Strings, and Hashing. This topic is about the hash table itself: how it is built, how it fails under skewed or adversarial input, and how it scales.
You maintain an in-memory ingestion service that uses hash maps intensively. Propose optimizations to improve cache locality and concurrency (for example sharded hash tables, open addressing, or prefetching). Explain trade-offs in code complexity, memory usage, and throughput, and how you'd benchmark changes.
Sample Answer
Direct answer
Two largely independent levers improve a hash-map-heavy service: cache locality (how memory is
laid out so the processor's cache can prefetch effectively) and concurrency (how many threads
can operate on the map simultaneously without blocking each other). Open addressing (storing
entries directly in one contiguous array) improves locality over separate chaining (where each
bucket is a separately-allocated linked structure); sharding the map into independently-locked
partitions improves concurrency by letting operations on different keys never contend for the
same lock.
Structured elaboration
Cache locality: open addressing vs chaining. Separate chaining stores each bucket as its own
linked list (or growable list) object; walking a bucket during a lookup means following a
pointer to a DIFFERENT heap allocation for each node, which the processor cannot reliably
prefetch, since the next node's address is not predictable until the current one is read. Open
addressing keeps every entry inline in ONE contiguous array; probing during a lookup walks
adjacent array slots, which the processor's hardware prefetcher handles well, since the next
slot's address is simply "next," known in advance. The concrete cost of chaining is not just the
lookup pattern: it also means many small separate heap objects (one per non-empty bucket)
instead of one larger contiguous block, adding real memory overhead beyond the raw data.
Concurrency: sharded hash tables. Instead of one hash map guarded by one lock, partition
keys across N independent shards (each its own map plus its own lock), routing each key to a
shard via hash(key) % N. Two operations on keys that land in DIFFERENT shards structurally
cannot contend, since they acquire two entirely different lock objects; this reduces contention
in proportion to shard count, at the cost of needing N separate locks and maps instead of one,
and losing the ability to do a single atomic operation across the whole table (a size() or
iteration must now touch every shard).
Prefetching. Even within a contiguous open-addressing array, explicit software prefetch
hints (issuing a request to load the next few likely probe slots into cache before they are
needed) can further help, particularly for probe sequences that are not perfectly sequential
(quadratic probing, double hashing); the benefit is workload- and hardware-dependent, so this is
usually the last lever pulled, after locality and concurrency structure are already improved.
Trade-offs in code complexity, memory, and throughput. Open addressing avoids per-node
allocation overhead (helping memory and locality) but complicates deletion (tombstones are
usually needed, since simply clearing a slot can break probe sequences for other keys that
probed past it) and degrades sharply as load factor approaches 1 (probe sequences grow long).
Chaining tolerates a higher load factor more gracefully (buckets just get slightly longer lists)
at the cost of the locality and per-node memory overhead already described. Sharding adds real
code complexity (every operation must first resolve which shard, and whole-table operations must
iterate all shards) in exchange for concurrency.
How to benchmark changes. Do not report wall-clock timings as the improvement metric, since
they are hardware- and load-dependent and not reproducible across environments; instead measure
structural, reproducible properties: memory footprint per entry (bytes per key/value pair,
measured directly), number of separate heap allocations (a direct proxy for locality, since fewer
larger allocations mean fewer pointer chases), and lock-contention structure (how many distinct
lock objects exist, and whether two specific keys share one). Where a throughput number is
needed for a real decision, run the SAME benchmark harness on the SAME hardware under controlled
load and report relative improvement with the harness and conditions fully specified, rather than
an isolated absolute number.
Worked example
# Run with PYTHONHASHSEED=0 to reproduce the exact byte counts below: Python randomizes
# string hash() per process by default, so unpinned runs will show slightly different numbers.
import sys, threading
def build_open_addressing_table(num_slots, keys):
table = [None] * num_slots
for k in keys:
idx = hash(k) % num_slots
while table[idx] is not None:
idx = (idx + 1) % num_slots
table[idx] = k
return table
def build_chained_table(num_buckets, keys):
buckets = [[] for _ in range(num_buckets)]
for k in keys:
buckets[hash(k) % num_buckets].append(k)
return buckets
keys = [f"key-{i}" for i in range(1000)]
open_table = build_open_addressing_table(2000, keys)
chained_table = build_chained_table(2000, keys)
open_bytes = sys.getsizeof(open_table)
outer_bytes = sys.getsizeof(chained_table)
all_bucket_bytes = sum(sys.getsizeof(b) for b in chained_table)
num_nonempty = sum(1 for b in chained_table if b)
print("open addressing, single array:", open_bytes, "bytes")
print("chained, outer array:", outer_bytes, "bytes")
print("chained, all 2,000 bucket objects combined:", all_bucket_bytes,
f"bytes ({num_nonempty} non-empty, {2000 - num_nonempty} empty)")
print("chained, total:", outer_bytes + all_bucket_bytes, "bytes")
# Concurrency: shard across independent locks, confirm different shards use different lock objects
num_shards = 16
locks = [threading.Lock() for _ in range(num_shards)]
sample_keys = ["alice", "bob", "carol", "dave", "erin"]
shards = [hash(k) % num_shards for k in sample_keys]
for k, s in zip(sample_keys, shards):
print(k, "-> shard", s)
for i in range(len(sample_keys)):
for j in range(i + 1, len(sample_keys)):
if shards[i] != shards[j]:
print(f"{sample_keys[i]} vs {sample_keys[j]}: different shards, "
f"different lock objects: {locks[shards[i]] is not locks[shards[j]]}")
Building both structures for 1,000 keys at a 0.5 load factor (with PYTHONHASHSEED=0 pinned for
reproducibility): the open-addressing array is a SINGLE object, sys.getsizeof reporting 16,056
bytes. The chained version's outer array alone is 16,184 bytes; summing sys.getsizeof over all
2,000 bucket-list objects (775 non-empty, 1,225 empty) adds 136,800 bytes, for a combined 152,984
bytes spread across 2,001 separate heap allocations (the outer array plus every bucket list,
empty or not). That is the measured, structural basis for the locality argument: a probe sequence
in the open-addressing table walks one array, while a bucket traversal in the chained table
follows a pointer to a different heap object each time. For concurrency, sharding across 16
independent threading.Lock objects and routing the same 5 sample keys by hash lands them on
shards 1, 10, 2, 11, and 8 respectively under this pinned seed, and confirms, by object identity
(is not), that any two keys landing in different shards are guarded by two DIFFERENT lock
objects, meaning writers to those keys are structurally unable to block each other regardless of
thread scheduling.
Trade-offs and pitfalls
- Do not report wall-clock benchmark numbers as if they were portable facts. They depend on
the specific machine, load, and even the run; report the reproducible structural properties
above, or a relative comparison from a fully specified, shared benchmark harness. - Sharding trades whole-table operations for concurrency. An operation that needs a
consistent view across the whole map (exactsize(), a full iteration) now has to coordinate
across all shards, which is easy to get subtly wrong (for example, reading each shard's size
without synchronization while writes are in flight gives an approximate, not exact, count). - Open addressing's deletion complexity is a common trip-up: naively clearing a slot on
delete can silently break lookups for a DIFFERENT key whose probe sequence passed through that
slot; tombstones (a special "deleted" marker distinct from "empty") are the standard fix, at
the cost of needing periodic table rebuilds to reclaim tombstoned slots. - Prefetching is the smallest, most hardware-dependent lever; validate it actually helps on
your target hardware before adding the complexity, rather than assuming it always pays off.
Explain hash collision (hash-flooding) attacks and their effect on hash-table-backed services. As a data engineer, what would you deploy at the application and infrastructure level to make your pipeline's hash tables resilient to an attacker who can choose input keys?
Sample Answer
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.
Describe robust strategies to hash composite keys (tuples of multiple fields) for hash tables. Explain common combination techniques (e.g., multiply-add mixing 31*prev + fieldHash, xor+rotations), handling nulls, order sensitivity, and producing stable hashes across language runtimes.
Sample Answer
Direct answer
Hash each field independently, then combine the per-field hashes with a mixing step, most
commonly the Java-style multiply-add h = 31 * h + fieldHash(field), applied one field at a time
in a fixed order, or an xor-plus-rotate accumulator as an alternative mixing strategy. Handle
null fields with a distinct sentinel value so a missing field never collides with a real value
that happens to hash the same way, and if the key's fields are logically ORDERED (like a
directed edge (from, to)), pick a mixing function that is order-sensitive, since swapping field
order should produce a different combined hash.
Structured elaboration
Multiply-add mixing. Starting from h = 0, fold in each field one at a time:
h = 31 * h + fieldHash(field). The multiplier 31 (an odd prime, chosen historically for being
efficiently computable via a shift-and-subtract on old hardware, and for having good mixing
properties in practice) means each field's contribution is scaled differently depending on its
POSITION, since earlier fields get multiplied by 31 more times than later ones. This is what
makes the combination order-sensitive: combine(a, b) and combine(b, a) generally differ,
because a and b play different roles depending on which position they occupy.
xor+rotate mixing. An alternative: rotate the accumulator by a fixed number of bits, then XOR
in each field's hash: h = rotate_left(h, k) XOR fieldHash(field). This is also order-sensitive
(the rotation happens BETWEEN fields, so which field lands at which rotation phase changes the
result), and distributes bit influence differently than multiply-add; some implementations prefer
it for its simple, fast, branch-free operations.
Handling nulls. A field that is legitimately absent or null must not be silently treated the
same as some default value (empty string, zero) that could also occur as a REAL value, or two
genuinely different composite keys could collide. The fix: define a fixed sentinel hash (for
example, the hash of a marker byte sequence no real field value could ever produce) and use it
whenever a field is null, so (name="Alice", nickname=None) and (name="Alice", nickname="") hash differently, since null and empty string are different values.
Order sensitivity, and when you want it (or don't). If the composite key is inherently
ordered (a directed edge, a version+id pair where the two fields play different roles),
multiply-add or xor-rotate mixing gives you order sensitivity "for free," since each already
depends on field POSITION. If instead the key is a genuinely unordered SET of fields (order
should not matter for equality), you need a different approach: hash each field independently and
combine with a commutative operation, like summing or XOR-ing the individual field hashes
directly (without rotation, which reintroduces order-sensitivity), so permuting the fields leaves
the combined hash unchanged.
Producing stable hashes across language runtimes. A language's BUILT-IN hash function for a
string is frequently randomized per process (to defend against hash-flooding), which makes it
unsuitable as the per-field hash if the combined hash must be reproducible across restarts or
across a different language entirely. Use a fixed, well-specified, content-addressed hash (for
example, a cryptographic digest like SHA-256, or a documented non-cryptographic hash with a
FIXED, published seed) as fieldHash, so the same field VALUE hashes identically regardless of
which process, restart, or language runtime computed it.
Worked example
import hashlib
_NULL_MARKER = b"\x00__NULL__\x00"
def field_hash(value) -> int:
data = _NULL_MARKER if value is None else repr(value).encode("utf-8")
return int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
def combine_multiply_add(fields, mask=(1 << 63) - 1):
h = 0
for f in fields:
h = (31 * h + field_hash(f)) & mask
return h
print(combine_multiply_add(("user-42", None, "US")))
print(combine_multiply_add(("user-42", "", "US")))
print(combine_multiply_add(("alice", "bob")))
print(combine_multiply_add(("bob", "alice")))
Running this: ("user-42", None, "US") and ("user-42", "", "US") produce different combined
hashes (5823293871742902993 versus 8134958508199836266), confirming null and empty string are
never conflated. Swapping field order, combine_multiply_add(("alice", "bob")) versus
combine_multiply_add(("bob", "alice")), produces different hashes (859106286592904078 versus
5917848126298614322), confirming the multiply-add mixing is order-sensitive as intended.
Cross-runtime stability, actually checked (not just claimed)
The claim above, that this scheme is stable across process restarts even though Python's own
built-in string hash() is randomized per process, is worth demonstrating rather than asserting.
This spawns two independent child processes with different PYTHONHASHSEED values and compares
both the built-in hash and the SHA-256-based combined hash between them:
import subprocess
import sys
import os
_CHILD_CODE = '''
import hashlib
_NULL_MARKER = b"\\x00__NULL__\\x00"
def field_hash(value):
data = _NULL_MARKER if value is None else repr(value).encode("utf-8")
return int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
def combine_multiply_add(fields, mask=(1 << 63) - 1):
h = 0
for f in fields:
h = (31 * h + field_hash(f)) & mask
return h
print(hash("user-42"))
print(combine_multiply_add(("user-42", "checkout", "US")))
'''
def run_with_seed(seed):
env = {"PYTHONHASHSEED": str(seed), "PATH": os.environ.get("PATH", "")}
out = subprocess.run([sys.executable, "-c", _CHILD_CODE], env=env,
capture_output=True, text=True, check=True)
builtin_hash, combined_hash = out.stdout.strip().splitlines()
return int(builtin_hash), int(combined_hash)
b1, c1 = run_with_seed(1)
b2, c2 = run_with_seed(999)
print("builtin hash differs across seeds:", b1 != b2)
print("combined hash agrees across seeds:", c1 == c2)
Running this prints builtin hash differs across seeds: True then
combined hash agrees across seeds: True: the two child processes' randomized hash("user-42")
values are different (as expected, since PYTHONHASHSEED changes between them), but the
SHA-256-based combine_multiply_add result for the same composite key is identical in both,
confirming the cross-runtime stability claim rather than just asserting it.
Trade-offs and pitfalls
- Using a language's randomized built-in hash as the per-field hash is the most common bug:
it works fine within one process's lifetime but silently breaks the moment the combined hash
needs to survive a restart, be compared across processes, or be recomputed by a different
language's implementation. - Order sensitivity is a design DECISION, not an automatic property. Confirm whether the
composite key is genuinely ordered (use multiply-add or xor-rotate as shown) or genuinely a set
(use a commutative combination instead); applying the wrong one either silently distinguishes
keys that should be equal, or silently merges keys that should be distinct. - Never let null collapse into a real value's hash. This is a subtle correctness bug: it
usually will not surface in testing until two records that differ only by "field present vs
field null" collide unexpectedly. - The multiplier and rotation amount are tuning choices, not magic constants:
31is a
well-tested convention (used by Java's ownObject.hashCode()combination), but the mixing
quality still depends on the per-field hash itself being well-distributed; a poorfieldHash
undermines even a good combination strategy.
Compare separate chaining and open addressing collision-resolution strategies (linear probing, quadratic probing, double hashing). Discuss cache locality, memory overhead, deletion complexity, primary clustering, probe length distribution, and which you'd choose for systems with constrained memory versus systems optimized for CPU caches.
Sample Answer
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).
Implement an LRU cache class with get and put methods in Java (using LinkedHashMap) or Python (using collections.OrderedDict). Requirements: get and put must run in O(1) average time, the cache is capacity-limited, and least-recently-used entries are evicted on overflow. Discuss alternative implementations and concurrency considerations.
Sample Answer
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
getis 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 withaccessOrder=trueand withremoveEldestEntryoverridden 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
getandput: 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 key2after it was evicted, and again for key3). - Capacity exactly at the boundary: confirmed the store never exceeds the configured capacity of 2 entries across the whole sequence of operations above.
- A
getchanging which key is next in line for eviction: demonstrated directly, touching key1viagetbefore inserting key4is what causes key3, not key1, 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.
Unlock Full Question Bank
Get access to all Hashing and Hash Tables interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.