Since Java 8, HashMap.get is O(log n) in the worst case, thanks to the red-black tree fallback. Before Java 8 it was O(n), because a degenerate bucket was a linked list.
The complexity table
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| get / containsKey (avg) | O(1) | O(1) | O(log n) | Tree fallback when bucket >= 8 and table >= 64 |
| put (avg) | O(1) | O(1) | O(log n) | Amortised; resize adds O(n) occasionally |
| remove | O(1) | O(1) | O(log n) | Same as get |
| iteration | O(n + cap) | O(n + cap) | O(n + cap) | Walks every bucket slot, occupied or not |
Why O(log n), not O(log k)?
If a single bucket holds all n entries and is treeified, lookup is O(log n) — the size of that one bucket equals the size of the map. In practice this happens only if every key collides on its hash, which requires either adversarial input or a broken hashCode().
Why it matters
The pre-Java-8 worst case (O(n) per lookup) made HashMap vulnerable to hash-flooding DoS attacks: an attacker submits keys engineered to collide, and what should be O(1) lookups become O(n), turning a single endpoint into a CPU sink. Web servers using user-supplied keys (form params, JSON keys) were the typical target.
// Pathological case: every key collides
record Bad(int x) {
@Override public int hashCode() { return 0; }
}
Map<Bad, Integer> m = new HashMap<>();
for (int i = 0; i < 10_000; i++) m.put(new Bad(i), i);
// Pre-Java-8: linear chain of 10000 -> get is O(n)
// Java 8+: red-black tree -> get is O(log n)Caveats
- The tree only forms once both thresholds are met (chain ≥ 8 and capacity ≥ 64). Below that, the bucket is still a linked list — but at that scale O(8) is fine.
- Tree ordering uses
hashCodefirst; if hashes also tie, it triesComparable.compareToon the keys. If keys aren'tComparable, the tree falls back to identity-based tie-breaking, which meansgetstill has to walk subtrees comparing withequals. Still bounded, just slower in the constant factor.