Hashing and Hash Tables Questions

Direct answer

Since Java 8, HashMap stores entries in an array of buckets, each normally a linked list of
Node<K,V> objects; it resizes (doubles capacity) once the entry count exceeds capacity times the
load factor (default 0.75), and, as a worst-case safety net, converts ("treeifies") any single
bucket's chain into a small balanced red-black tree once that one bucket grows past 8 entries in a
sufficiently large table.

Structured elaboration

From hashCode to bucket index. HashMap doesn't use a key's raw hashCode() directly as the
index. It first applies a supplemental "hash spreading" step (XOR-ing the hash with itself shifted
right by 16 bits) specifically to mix higher bits into the lower bits, since the actual index
computation is hash & (capacity - 1) (capacity is always a power of two, so this bitmask is
equivalent to, but much cheaper than, a modulo), which only ever looks at the LOW bits of the hash;
without the spreading step, two keys whose hashCodes only differ in high bits would collide on every
capacity that happens to be smaller than that difference.

Load factor and resize. Default loadFactor = 0.75 and default initial capacity 16 means a
resize (doubling capacity, then rehashing every entry) fires once the 13th entry is inserted (16 * 0.75
= 12, so the map resizes on exceeding that threshold). This is the same load-factor/resize mechanism any hash table needs generically; HashMap's specific default is 0.75 with
doubling.

Treeification. Once a single bucket's chain length exceeds TREEIFY_THRESHOLD (8 entries), AND
the table's total capacity is at least MIN_TREEIFY_CAPACITY (64), that one bucket converts from a
linked list to a small red-black tree, bounding THAT bucket's worst-case lookup at O(log n) instead of
O(n). Below capacity 64, HashMap prefers to resize the whole table first (since a small table with one
long bucket is more likely just needing more buckets overall, not a genuinely pathological
distribution), only treeifying once the table is already reasonably large and a bucket is STILL long
after that.

Why hashCode/equals correctness matters more here than almost anywhere else. Every one of the
mechanisms above (bucket index selection, chain traversal, treeified-tree comparison) depends on
hashCode() being consistent with equals() for every key ever inserted; violating that contract doesn't just risk a collision, it can make an entry
permanently unfindable.

Worked example

Inserting keys whose hashCode() values are 0x0000FFFF and 0xFFFF0000 into a HashMap of capacity
16 (capacity - 1 = 0x0000000F): a naive hash & (capacity-1) on the RAW hashCode gives
0x0000FFFF & 0xF = 0xF for the first and 0xFFFF0000 & 0xF = 0x0 for the second, no collision, by
coincidence. But two keys with hashCodes 0x00010000 and 0x00020000 (differing only in bits far
above the low 4 bits actually used by a capacity-16 mask) BOTH give hash & 0xF = 0x0, an unnecessary
collision a wider mask would have avoided if it could see those higher bits at all; the supplemental
hash ^ (hash >>> 16) spreading step exists specifically to fold higher-order bit differences down
into the low bits the mask actually inspects, reducing exactly this class of avoidable collision.

Trade-offs and pitfalls

A common shallow answer describes ONLY the chaining/collision behavior without mentioning the
capacity-must-be-a-power-of-two design (and the resulting bitmask-instead-of-modulo optimization),
or without mentioning that treeification requires BOTH a long chain AND a sufficiently large table,
stating it as if any 8-entry chain treeifies regardless of table size overstates the mechanism and
is a common, checkable inaccuracy.

Direct answer

A hash-flooding attack exploits the fact that any hash function has SOME set of inputs that all
collide, if an attacker can discover or predict that set and control the keys your service inserts
(form fields, JSON object keys, query parameters), they can force a hash table's normal average-case
O(1) behavior down to worst-case O(n) per operation, turning ordinary-looking requests into a
denial-of-service. The fix is making the hash function unpredictable to the attacker, not just fast.

Structured elaboration

Why this is a real, historically-exploited class, not a theoretical concern. In 2011, researchers
demonstrated that PHP, Python, Ruby, Java, and other languages using predictable, unkeyed
non-cryptographic hash functions (many using variants of DJBX33A) for their built-in
associative-array/dict/hashmap types could be attacked with a small number of specially-crafted
request parameters, since the hash algorithm was fixed and known, an attacker could precompute a
large batch of colliding keys offline and submit them in one request, degrading that single request's
processing to O(n^2), enough to exhaust a server's CPU with a tiny amount of network traffic. This is
what made "hash flooding" a named, patched, CVE-worthy vulnerability class rather than a purely
academic observation.

Why the fix is unpredictability, not just switching hash functions. Simply picking a "better"
non-cryptographic hash function doesn't solve this: ANY fixed, publicly-known algorithm has some
colliding input set an attacker with enough compute can eventually find. The actual fix is making the
hash function's OUTPUT unpredictable to someone who doesn't know a secret, this is exactly what
SipHash (a keyed pseudorandom function, fast enough for everyday hash-table use, unlike a
cryptographic hash) and Python's per-process hash-randomization seed both do: an attacker who knows
the algorithm perfectly still cannot predict which inputs will collide without also knowing the
process's private seed, which changes every time the process restarts.

Defense in depth beyond the hash function itself. Randomized/seeded hashing closes the specific
attack vector, but production systems layer additional mitigations: capping the number of items a
single request is allowed to insert into any one table (bounding the attack's blast radius even if a
collision set were somehow found), and falling back to a balanced-tree bucket (as Java 8's
treeification does automatically) once any one bucket's chain crosses a length threshold, which caps
the WORST realistic cost per bucket at O(log n) even in the pathological case, independent of whether
the seeding defense holds.

Application level versus infrastructure level. The question specifically asks for both, and they
are genuinely different layers, not the same fix said twice. Application level means changes inside
the service's own code: seeded/keyed hashing (SipHash, per-process randomization), capping items per
request into any one table, and treeification of oversized buckets, all described above. Infrastructure
level means stopping or containing the damage BEFORE or AROUND the application code: enforcing a
request body size or object-key-count limit at the API gateway or reverse proxy, so a pathological
payload is rejected before it ever reaches the parsing code that would build the hash table; capping
per-request CPU time or wall-clock time via a container cgroup limit or a serverless function timeout,
so one pathological request cannot monopolize a shared worker process indefinitely even if every
application-level defense somehow failed; and rate-limiting or blocklisting the offending client at the
load balancer or WAF, which is also the fastest lever to pull during an active incident, well before a
code-level fix can be reviewed and deployed. Application-level fixes close the vulnerability; infrastructure-level
controls bound the blast radius while that fix ships and catch anything the application layer misses.

Worked example

Without a secret seed, an attacker who knows a service uses (for example) an unkeyed 32-bit additive
hash for its JSON parser's object keys could precompute, entirely offline and ahead of time, a list
of a few thousand strings that all hash to the identical bucket, then submit ONE request containing
an object with those few thousand keys. If the server's hash table has no randomized seed, every one
of those keys collides into the same bucket, insertion (and any subsequent lookup) becomes O(n) per
operation for that one bucket, turning what looks like an ordinary few-KB request into work
equivalent to n^2 comparisons. With a per-process random seed mixed into the hash, the SAME
precomputed key list, valid against one seed, produces a essentially-random, non-colliding
distribution against a different, unknown seed, the attacker's precomputation is worthless without
also knowing the seed.

Trade-offs and pitfalls

A common incomplete answer stops at "just use a better hash function", missing that the defense is
specifically about UNPREDICTABILITY to an attacker who may well know the exact algorithm, not
raw hash quality in the uniform-random-input sense. A second common gap: treating this purely as an
academic curiosity rather than citing the real, patched, multi-language incident class it is,
concretely acknowledging the history (2011, DJBX33A, PHP/Python/Ruby) demonstrates the difference
between reciting a mitigation checklist and understanding why the mitigation exists.

Direct answer

Collisions in a running hash table come from four distinct root causes: a poorly-distributed hash function, a table that has grown too full for its size, adversarially chosen input designed to defeat the hash, and keys that happen to be very similar to each other. They look different in production metrics and need different fixes, so the first job when investigating a collision problem is figuring out which of the four you actually have.

Structured elaboration

Detecting these in a running system, the metrics worth collecting: load factor (n/m) per table or shard over time, alerting before it crosses the resize threshold; the maximum bucket chain length or probe-sequence length sampled periodically, not just the average, since a healthy average can hide one badly-clustered bucket; the gap between p50 and p99 operation latency, since well-distributed buckets should give uniform latency and a widening p99-to-p50 gap while the average load stays flat is a strong signal of localized clustering; and, to tell normal random variance from a genuine skew, a chi-squared goodness-of-fit style comparison of per-bucket counts against the expected uniform distribution. For adversarial input specifically, correlate an abnormal p99 latency spike with an abnormal request rate from a single client or a narrow key-prefix pattern.

Worked example

A table of size m = 8 using key % m as its hash: ids 0, 8, 16, and 24 all satisfy id % 8 == 0, so all four land in the same bucket regardless of how many buckets exist, purely because the id-generation stride (8, from some upstream sharding scheme) shares a factor with the table size. Growing the table to size 100 does not fix this on its own if ids keep incrementing by 8, since id % 100 still repeats every 100/gcd(8,100) = 25 distinct values; the actual fix is a hash function that mixes the bits of the key (e.g., multiplying by a large odd constant and shifting) before reducing modulo the table size, not a hash that reduces mod table_size directly on a structured id.

Trade-offs and pitfalls

Watching only the average load factor is the most common mistake: "load factor is 0.6, this should be fine" can coexist with one client's key pattern degenerating a subset of buckets to effectively O(n) lookups. Fixing a suspected hash-quality problem by resizing the table addresses load-factor-driven collisions but does nothing for a genuinely poor hash function or a targeted adversarial pattern, and conversely, swapping in a better hash function does nothing if the real problem is simply too high a load factor for the collision-resolution strategy in use. Diagnose which cause you have (via the metrics above) before choosing between resizing, replacing the hash function, adding per-process random seeding to defeat adversarial input, or accepting a genuine, unrelated hot-key skew that no hash-table change will fix.

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

An LRU (least-recently-used) cache always evicts whichever entry hasn't been touched for the longest
time when it needs to make room. A hash map alone can't track "longest untouched" cheaply, and a
linked list alone can't find a given key quickly, so LRU caches pair the two: the map gives instant
lookup, the list gives instant reordering.

Structured elaboration

Why not just a hash map? A plain hash map has no sense of time or usage order at all, entries
are just there or not. To find "the oldest one" you'd have to inspect every entry's last-access time
and take the minimum, an O(n) scan on every eviction.

Why not just a linked list? A linked list ordered by recency (most-recent at the front) makes
"find the least-recently-used entry" trivial, it's always the tail, O(1). But finding a SPECIFIC
key's node, which you need to do on every get, requires walking the list from the front until you
find it, O(n) in the worst case.

Why the pair solves both problems. The map stores key -> node reference, so get(key) jumps
straight to the right list node in O(1) instead of scanning. Having jumped there, moving that node
to the front of the list (marking it "just used") is a handful of pointer updates, O(1), not a
re-sort of the whole list. Eviction is then just "drop whatever's at the tail," also O(1), and
requires removing that same key from the map too, so the two structures never drift out of sync.

Worked example

Capacity-2 cache, inserting A, then B, then accessing A, then inserting C:

1. put(A): list is [A] (front=back=A). map: {A}.
2. put(B): list is [B, A] (B is now most-recent). map: {A, B}.
3. get(A): A moves to the front. list is [A, B]. (B is now least-recently-used, at the tail.)
4. put(C): over capacity, evict the tail (B). list becomes [C, A]. map: {A, C}.

Note step 3 is the entire reason this is "least-recently-USED" and not "least-recently-inserted": had
step 3 not happened, B (inserted more recently than A) would have survived and A would have been
evicted instead. Reading a value is itself a "use" that resets the clock.

Why LRU is often a good default for SRE caching use cases

Most real production access patterns exhibit temporal locality: whatever was used recently (a hot
config value, an active user's session, a just-computed result) is disproportionately likely to be
requested again soon, and whatever hasn't been touched in a while genuinely is less likely to be
needed. LRU's eviction rule tracks exactly that signal, recency of use, directly and cheaply: no
per-key frequency counters to maintain (unlike LFU, least-frequently-used), no manual re-tuning as the
workload's hot set shifts over time, since LRU adapts automatically the moment access patterns change.
That combination, cheap to implement (the map-plus-list pairing above), O(1) per operation, and
self-adjusting to whatever is actually hot right now, is why it's the default reached for first, with
more specialized policies (LFU, ARC, a size- or cost-aware eviction rule) reserved for workloads where
a measured access pattern shows LRU's recency-only heuristic is actually a poor fit, such as the bursty
one-time-scan case below.

Trade-offs and pitfalls

Bursty access patterns are the well-known caveat: if a workload scans through a huge sequential range
of keys once each (a full-table scan, say), LRU's "most recently touched" heuristic can be actively
wrong, it will evict genuinely hot, repeatedly-used entries in favor of keeping whatever was touched
most recently by the one-time scan, right up until the scan finally moves on. Recognizing this is the
mark of a stronger answer than one that presents LRU as universally optimal.