HashMap performance drops under heavy load
Scenario
Under peak traffic, CPU on map operations spikes. get/put that were microseconds become milliseconds. p99 latency grows while QPS is flat. Profilers show time inside HashMap or ConcurrentHashMap. You need to know whether the map is too big, badly hashed, resizing, or contended—and fix it without rewriting the whole service.
After reading, you should be able to:
- Explain O(1) average vs O(n) worst case (collisions, long chains).
- Spot bad
hashCode, undersized maps, and resize/rebalance storms. - Tell
HashMapmisuse fromConcurrentHashMapresize contention. - Fix with sizing, key design, bounded caches, and sharding—not only a bigger JVM.
Why — buckets stop behaving like O(1)
HashMap maps keys to an array of buckets using hashCode() and a spread function.
Average case: one or few entries per bucket → fast. Worst case: all keys land in one bucket → linked list or tree walk per operation → effectively O(n).
Under load, that looks like sudden “map degradation.”
Common degradation modes
| Mode | What happens |
|---|---|
| Hash collisions | Broken or hostile hashCode; all keys in one bucket |
| Resize / rehash | Table doubles when load factor exceeded; all entries rehashed—CPU spike |
| Treeify pressure (Java 8+) | Long chains become red-black trees—better than O(n) list but still hot |
| Huge unbounded map | Millions of entries; cache misses, GC scanning, long rehash |
| ConcurrentHashMap contention | Many threads hit same bin during resize or hot key updates |
| Wrong map type | HashMap shared across threads → external sync or corruption |
Hot computeIfAbsent | Many threads compute same missing key—duplicate expensive loads |
HashMap vs ConcurrentHashMap under load
HashMap— not thread-safe; one thread only, or you add locking (serializes access).ConcurrentHashMap— striped locks / CAS per bin; scales for independent keys but can still degrade on same key or during resize.Collections.synchronizedMap— single lock for entire map; often worse than CHM at concurrency.
Collisions ≠ races. Slow maps can be correct but poorly distributed. Concurrent modification of plain HashMap causes exceptions or bugs—see shared data races.
What — prove the bottleneck is the map
-
Profiler (CPU or wall-clock)
— async-profiler, JFR, YourKit: hot frames in
HashMap.getNode,putVal,ConcurrentHashMap.transfer,treeifyBin. - Correlate with traffic and map size — metrics: cache/map entry count, heap used by map (approximate via heap dump dominator tree). Spike at round entry counts (64k, 128k) → resize event.
-
Inspect key type
— custom
hashCode()returning constant? Onlyequalswithout consistenthashCode? Mutable keys changed after insert? -
Check for collision patterns
— security: Hash DoS with crafted
Stringkeys (mitigated in modern JDKs with per-map seed, but custom keys still vulnerable). — domain: IDs that collide mod bucket count if hash is weak. - Concurrent access pattern — one hot key updated by all threads? Metrics per key if possible (business id in logs).
-
Anti-patterns in hot loops
// CHM size() can be expensive — walks segments for (...) { if (cache.size() > MAX) evict(); // avoid } - Thread dump (secondary) — many threads in map methods or blocked on CHM bin—pairs with BLOCKED / short freezes during resize.
Smoking-gun examples
// Bad: constant hash — all keys in one bucket
@Override public int hashCode() { return 1; }
// Bad: default capacity for millions of inserts — many resizes
Map<String, Data> cache = new HashMap<>();
// Bad: hot global key
rateLimitMap.computeIfAbsent("GLOBAL", k -> new Counter());
How — restore map performance
Fixes (in priority order)
| Fix | When |
|---|---|
Fix hashCode / use immutable keys | Custom keys; use Objects.hash or record types |
| Pre-size the map | Known N inserts: new HashMap<>((int)(n / 0.75f) + 1) |
| Bound size | Caffeine/Guava cache with maximumSize + TTL—not unbounded ConcurrentHashMap |
| Shard maps | map[hash(id) % 16] reduces contention per CHM instance |
| Split hot keys | Per-tenant counters instead of one global key |
| Right structure | CHM for concurrent cache; HashMap only per-request |
| Load once per key | computeIfAbsent + single-flight wrapper for expensive loads |
Pre-sized ConcurrentHashMap
int expected = 100_000; Map<String, Session> sessions = new ConcurrentHashMap<>(expected);
JDK picks internal size from expected entries; avoids repeated resize while warming cache.
Bounded cache (Caffeine sketch)
Cache<String, User> users = Caffeine.newBuilder()
.maximumSize(50_000)
.expireAfterWrite(Duration.ofMinutes(10))
.build();
When to leave HashMap entirely
- Primitive keys — consider fastutil-style maps or specialized structures.
- Read-heavy, rare writes — copy-on-write or immutable map snapshot.
- Ordered iteration —
LinkedHashMapadds overhead; use only if needed.
Verify
- Load test at peak: map methods no longer top CPU; p99 back within SLO.
- Entry count stable or bounded; no stair-step latency at resize boundaries.
- Heap: map dominator size flat over 24h soak.
Interview one-liner
“HashMap degrades when keys collide into one bucket, the table keeps resizing, or ConcurrentHashMap contends on hot keys. I profile get/put, fix hashCode and initial capacity, bound the cache, and shard or use a proper cache library if it’s shared under high concurrency.”