1. Production Problem
The service was a transaction enrichment pipeline — a Java backend responsible for decorating payment events with merchant metadata before pushing them downstream to a fraud scoring engine. Under normal load the p50 latency was comfortable at around 12 ms. The p99 was stable. Nothing in the dashboards suggested a problem.
The issue surfaced only when a specific category of merchants — those whose identifiers shared a structural pattern — were processed in batch. The p99 latency jumped from 18 ms to 340 ms for that cohort. The p50 barely moved. The discrepancy made the initial investigation misleading: most traffic was fine, so the focus shifted to downstream systems, then to network, then to the fraud engine itself. None of those were the culprit.
A thread dump taken during one of the spikes showed the majority of threads blocked inside HashMap.getNode(), traversing what should have been O(1) lookups. The merchant metadata cache was implemented as a HashMap<String, MerchantDetails>, keyed on a composite String built from merchant category code and country code. That composite key construction — combining two short uppercase strings of similar character ranges — produced a small set of colliding hash values under Java’s String hashCode() algorithm. Every lookup for the affected merchants was traversing a linked list of 40–60 entries rather than resolving directly.
The root cause was not a bug in HashMap itself. HashMap behaved exactly as designed. The problem was an assumption: that O(1) average-case performance would hold regardless of the key distribution. It does not. When keys cluster into the same bucket — whether through poor hashCode() design, adversarial input, or unlucky data characteristics — HashMap’s performance guarantee collapses in precisely the scenarios that are hardest to reproduce in testing.
2. Internal Working
HashMap stores entries in an array of Node<K,V> objects, where each node contains the key, value, hash, and a reference to the next node. This makes each bucket position in the array the head of a singly-linked list. The relationship between a key and its bucket is determined by two operations.
First, the hash is spread using the static HashMap.hash() method defined in OpenJDK’s HashMap source:
// Java 8+ — static utility method inside java.util.HashMap
static final int hash(Object key) {
int h;
// XOR the high 16 bits down into the low 16 bits to spread entropy.
// Without this, keys whose hashCode() differs only in high bits would
// collide when the table capacity is small (index = hash & (n-1)).
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}Code language: Java (java)Second, the bucket index is computed as index = hash & (n - 1), where n is always a power of two. This is equivalent to modulo but uses a bitwise AND, which is faster. The consequence is that only the low-order bits of the hash actually determine bucket placement when capacity is small. The hash >>> 16 spreading step exists specifically to reduce collisions in this scenario by folding high-order entropy into the low bits.
Before Java 8, collision chains were always linked lists. As the chain length grew, so did lookup time — linearly. JEP 180 introduced treeification: when a single bucket accumulates TREEIFY_THRESHOLD (8) or more nodes and the overall table capacity has reached MIN_TREEIFY_CAPACITY (64), the linked list for that bucket is converted to a Red-Black Tree. This changes worst-case lookup within a bucket from O(n) to O(log n). When entries are removed and the count falls below UNTREEIFY_THRESHOLD (6), the tree reverts to a linked list.
Resizing is triggered when the total number of entries exceeds capacity * loadFactor. The default load factor is 0.75 and the default initial capacity is 16, meaning resizing first occurs at 13 entries. During resize, the table doubles in capacity and every existing entry is rehashed and repositioned — this is an O(n) operation and happens on the thread that triggers it.
3. Code Example
The following demonstrates how a poorly implemented hashCode() concentrates all entries in a single bucket, rendering every lookup a linear scan:
// Java 8+ — illustrates O(n) bucket degradation from a constant hashCode()
import java.util.HashMap;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
public class BucketDegradationDemo {
private static final Logger log = LoggerFactory.getLogger(BucketDegradationDemo.class);
static class MerchantKey {
private final String code;
MerchantKey(String code) { this.code = code; }
@Override
public int hashCode() {
// Returning a constant forces every key into bucket 0.
// In practice, poorly distributed hashCode() implementations
// cause the same effect — not at bucket 0, but at whichever
// index the constant hash maps to for the current capacity.
return 1;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof MerchantKey)) return false;
return code.equals(((MerchantKey) o).code);
}
}
public static void main(String[] args) {
HashMap<MerchantKey, String> cache = new HashMap<>();
for (int i = 0; i < 100; i++) {
cache.put(new MerchantKey("MCH-" + i), "details-" + i);
}
long start = System.nanoTime();
String result = cache.get(new MerchantKey("MCH-99"));
long elapsed = System.nanoTime() - start;
// With 100 entries in one bucket, this get() traverses 99 nodes
// before finding MCH-99. The treeification threshold (8) was crossed
// at entry 9, so this is actually a Red-Black Tree traversal — O(log n)
// rather than O(n) — but the degradation is still significant and visible.
log.info("Lookup result: {}, elapsed ns: {}", result, elapsed);
}
}Code language: Java (java)What happens at runtime: each put() calls HashMap.putVal(), which computes the bucket index from hash(key) & (n - 1). Since every key returns hashCode() == 1, all entries land in the same bucket. After the ninth entry, treeifyBin() is invoked (assuming capacity >= 64, which is reached here through resizing), and the linked list is replaced with a Red-Black Tree. The final get() traverses this tree. The O(log n) bound is better than O(n), but a correctly distributed hashCode() would resolve the same lookup in a single array access.
4. What Can Go Wrong
The most common failure mode is a hashCode() implementation that produces low entropy output for the actual data the system processes. This is frequently invisible in unit tests because test data is typically small and syntactically diverse. Production data, by contrast, has structural patterns — merchant codes within the same region share prefixes, user IDs issued within the same time window share numeric ranges, IP addresses within the same subnet share octets. Any of these patterns can cause hash clustering without the hashCode() method being technically incorrect.
A second failure mode involves mutable keys. HashMap computes the bucket index at insertion time using the key’s hashCode() at that moment. If the key object is mutated afterward — a field changed, a collection modified — the hashCode() value may change, making the entry unreachable under the new hash but still occupying the old bucket. The entry is not removed; it simply becomes orphaned. The map’s size counter reflects the entry, but get() cannot find it and containsKey() returns false. This produces slow memory growth and incorrect miss rates in any cache built on top of HashMap.
A third failure mode is thread-safety violation under concurrent access. HashMap makes no synchronisation guarantees. In Java 7, concurrent put() operations during resize could produce an infinite cycle in the linked list — a situation where two threads would both traverse the chain indefinitely during a subsequent get(). Java 8’s redesigned resize algorithm eliminated the infinite loop risk, but concurrent modifications still produce inconsistent reads: stale values, missed entries, or partially written state. The production symptom is typically intermittent NullPointerExceptions or incorrect application behaviour under load, which does not reproduce in single-threaded testing.
5. Performance and Scalability
The O(1) amortised complexity for get() and put() holds only when the hash function distributes keys uniformly across buckets. When the distribution degrades, so does the constant factor behind that O(1), and eventually the complexity class itself changes. Under treeification, worst-case per-bucket lookup is O(log n), but the treeified nodes are larger than linked list nodes — each TreeNode<K,V> carries parent, left, right, and prev references in addition to the base node fields. A fully treeified HashMap consumes meaningfully more heap than one with well-distributed keys, which increases GC pressure in applications with large, high-churn maps.
Resizing is the most predictable performance event and also the most commonly ignored. An application that initialises a HashMap at default capacity (16) and inserts 10,000 entries will trigger approximately 10 resize operations before stabilising. Each resize allocates a new internal array, rehashes every entry, and discards the old array. Under sustained insert load this produces a sawtooth pattern in GC metrics — rapid allocation spikes followed by minor GC collection of the old arrays. With async-profiler or Java Flight Recorder (jfr start name=hashmap_profile settings=profile), these allocations appear as repeated java.util.HashMap$Node[] allocations in the heap profiler.
Pre-sizing is the standard mitigation: new HashMap<>(expectedSize / 0.75 + 1) allocates sufficient initial capacity to avoid resizing during the expected load. This calculation accounts for the load factor threshold — simply passing expectedSize as the initial capacity is insufficient because resizing triggers when entries exceed capacity * 0.75, not when entries exceed capacity.
6. Trade-offs
Lowering the load factor below 0.75 reduces the probability of collision by keeping buckets sparser. The cost is increased memory consumption — a map with load factor 0.5 uses roughly twice the backing array space for the same number of entries. This trade-off makes sense in latency-sensitive applications where lookup speed matters more than heap footprint, but it does not help when the source of collisions is poor hash distribution rather than high load factor. Sparse buckets do not rescue a hashCode() that maps everything to the same value.
Raising the load factor above 0.75 reduces memory consumption at the cost of longer average bucket chains and more frequent treeification. At 0.9 or 1.0, maps with genuinely uniform hash distribution will still function correctly but will treeify more buckets and degrade more readily when any non-uniformity appears in the data.
The default of 0.75 was chosen as an empirical compromise that minimises both memory overhead and collision frequency under the assumption of uniform hash distribution. The correct mental model is not “0.75 is always right” but rather: the load factor governs the trade-off between space and time only when the hash function is doing its job. When it is not, the load factor is irrelevant.
7. When NOT to Use
HashMap is the wrong choice in any context where multiple threads share access to the same instance without external synchronisation. Collections.synchronizedMap(new HashMap<>()) provides coarse-grained locking that serialises all operations but does not support atomic compound operations like putIfAbsent. ConcurrentHashMap is the correct replacement — it uses segment-level (Java 7) or node-level (Java 8+) locking that allows concurrent reads and minimises write contention.
HashMap is also the wrong choice when insertion order or sorted order matters. LinkedHashMap preserves insertion order and is appropriate for LRU cache implementations. TreeMap maintains keys in their natural or comparator-defined order and is appropriate when range queries or sorted iteration are required. Substituting HashMap for these structures to gain perceived performance is a category error — the O(1) put/get advantage is irrelevant if the application then has to sort or iterate the entries on every read.
Finally, HashMap should not be used as a long-lived cache without eviction. It has no expiry semantics, no maximum size, and no eviction policy. Entries accumulate indefinitely until the map is cleared or garbage collected. Applications that treat HashMap as a cache typically rediscover this during memory pressure incidents.
8. Real-World Use Case
A per-user rate limiter in a high-throughput API gateway is a natural fit for HashMap’s characteristics. The implementation maintains a HashMap<String, TokenBucket> keyed on user ID, where each TokenBucket tracks the number of remaining requests within the current window. The access pattern is read-heavy — the vast majority of requests are gets, with puts occurring only on window expiry or new user creation. HashMap’s O(1) amortised lookups make the per-request overhead negligible.
The key design decision was initialising the map with a capacity derived from the expected concurrent user count rather than the default 16. At 50,000 concurrently active users and a load factor of 0.75, the correct initial capacity is 50000 / 0.75 + 1 = 66,668, rounded up to the next power of two (131,072). This eliminated all resizing events during normal operation and the associated allocation spikes that were previously visible in GC logs.
User IDs in this system were UUID strings. Java’s String.hashCode() was adequate — UUID strings have sufficient entropy across their character positions that bucket distribution stayed close to uniform under profiling. The rate limiter was wrapped in a read-write lock to manage the single-threaded access constraint.
9. Production Interview Section
What happens if a class overrides hashCode() to return a constant value, and instances of that class are used as keys in a HashMap with 10,000 entries?
Root Cause: A constant hashCode() produces the same bucket index for every key. All 10,000 entries collide into a single bucket.
Internal Behaviour: After the eighth entry, HashMap.treeifyBin() converts the bucket’s linked list to a Red-Black Tree, provided the table capacity has reached 64. Every subsequent put() performs a tree insertion (O(log n)) and every get() performs a tree traversal (O(log n)) rather than a direct array access followed by a single equals() check.
Production Impact: At 10,000 entries, each get() traverses approximately 13 comparisons (log₂ 10,000 ≈ 13) rather than 1. Under high request rates this saturates CPU, produces thread contention visible in thread dumps as HashMap.getNode() hotspots, and increases p99 latency disproportionately compared to p50.
Fix: Implement a hashCode() that distributes entropy across the full integer range. For composite keys, use a combination strategy: Objects.hash(field1, field2) or manually combine fields using the standard 31 * result + field.hashCode() polynomial. Profile the distribution against production data before deploying.
How does the system behave when a HashMap key is mutated after insertion — for example, a field used in hashCode() is changed?
Root Cause: HashMap computes and stores the hash of the key at insertion time to determine bucket placement. The key reference is stored in the Node, but the hash used for bucket lookup is recomputed from the object’s current state on subsequent get() calls. If the state has changed, the recomputed hash maps to a different bucket, and the entry cannot be found.
Internal Behaviour: HashMap.getNode() computes hash(key) using the key’s current hashCode(), uses it to find the bucket index, then traverses the chain or tree at that index comparing keys using equals(). Since the entry was placed in the bucket corresponding to the original hash, it does not appear in the bucket the new hash resolves to. The entry is permanently unreachable without a full table scan.
Production Impact: In a metadata cache keyed on mutable domain objects, this manifests as intermittent cache misses that force expensive downstream calls even though the entry appears to exist (map.size() is non-zero, the key object is still in scope). The pattern is difficult to diagnose because the map is not corrupt — it simply cannot locate entries that were moved by mutation.
Fix: Use immutable objects as HashMap keys. If the key domain requires mutable objects, extract an immutable identifier (a String ID, a long primary key) and key the map on that instead. Final fields and value objects are the correct key type.
What issues arise when a HashMap is shared across threads in a Spring Boot service without synchronisation, and traffic increases beyond what was tested?
Root Cause: HashMap is not thread-safe. Its internal state — the backing array, the size counter, the modCount used by iterators — is modified without any memory visibility guarantees.
Internal Behaviour: During a resize, the old array is replaced with a new one. If one thread is mid-traversal inside getNode() while another thread triggers putVal() and a resize, the traversing thread may see a partially initialised or inconsistent backing array. In Java 8+, this will not produce an infinite loop (as it could in Java 7’s linked list resize), but it can produce a NullPointerException, a missed entry, or a stale read that returns a value from before the resize.
Production Impact: The failure is load-dependent — it appears only when concurrent write throughput causes actual concurrent resize events. In a Spring Boot service with a singleton bean containing a shared HashMap, this typically surfaces under load testing or production traffic spikes as intermittent NPEs in threads that have nothing functionally to do with map mutation. The stack traces point into HashMap internals, and the root cause is often misidentified as a JVM bug.
Fix: Replace with ConcurrentHashMap. For read-heavy access patterns where snapshot semantics are acceptable, consider initialising the map once at startup and treating it as effectively immutable during runtime. If the access pattern requires atomic compound operations (check-then-put, compute-if-absent), use ConcurrentHashMap’s built-in atomic methods: computeIfAbsent(), putIfAbsent(), merge().
10. Summary
HashMap’s O(1) guarantee is a statistical expectation, not a contract. It holds when the hash function distributes keys uniformly across buckets, the load factor remains below the threshold, and no concurrent mutation occurs. When any of these assumptions fails — poor hashCode() implementation, unexpected data patterns, or shared mutable state — HashMap degrades silently. The most dangerous characteristic of this degradation is that it is invisible to standard monitoring: request counts remain stable, error rates stay zero, and only latency percentiles reveal the underlying traversal cost.
The actionable insight is to treat hashCode() quality as a first-class performance concern, initialise maps with realistic capacity estimates to eliminate resize events, and default to ConcurrentHashMap in any context where the thread-safety assumption is not guaranteed by the surrounding design.
From Real Experience
The latency investigation I described in the opening came from a payment enrichment service I worked on in a high-traffic financial platform processing several million transactions per day. The initial symptoms were subtle enough that the first two hours of the investigation focused entirely on the downstream fraud scoring engine — the service calling us was seeing intermittent SLA violations, and the natural assumption was that the enrichment step was fine and something further downstream had regressed.
What broke the assumption was a thread dump taken at peak load. The thread pool showed 40 of 50 threads inside java.util.HashMap.getNode(). That was unusual enough to shift focus. A quick heap dump confirmed that the merchant metadata cache — a straightforward HashMap<String, MerchantDetails> — had six buckets with over 30 nodes each, all treeified.
The composite key was constructed by concatenating a two-character merchant category code with a two-character ISO country code: "MCCxxCC". The character range for both fields was narrow — uppercase letters, digits, and a small set of punctuation marks. Java’s String hashCode() algorithm is polynomial and the short length of the string meant the resulting integers clustered in a narrow range, mapping repeatedly to the same buckets for this data shape.
The fix was changing the composite key from a String concatenation to a proper value class with a hashCode() implemented using Objects.hash(categoryCode, countryCode) after verifying distribution against the actual merchant catalogue. The improvement was immediate: p99 dropped from 340 ms back to 18 ms, and the treeified buckets disappeared entirely from subsequent heap dumps.
The broader lesson was that cache key design deserves the same scrutiny as cache eviction policy and cache size. Picking a convenient String for map key construction without profiling its hash distribution against real data is a latent performance bug waiting for the right data shape to trigger it.
