The expected complexity of HashMap.get is O(1). The interesting part is the worst case — and the answer changed in Java 8.
Pre-Java 8: O(n)
Every bucket was a singly linked list. If every key hashed to the same bucket (an adversarial input, or a terrible hashCode()), get degraded to a linear scan of one giant chain — O(n). This was a real denial-of-service vector: attackers could craft keys (e.g. HTTP form fields) that all collide, turning a map into a linked list and pinning a CPU.
Java 8+: O(log n)
Java 8 added treeification. When a single bucket grows to 8 nodes and the table capacity is at least 64, that bucket converts from a linked list into a red-black tree. A balanced tree gives O(log k) lookup within the bucket, so even a fully-colliding map answers get in O(log n) worst case instead of O(n).
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| get (expected) | O(1) | O(1) | O(log n) | treeified bucket; pre-Java 8 worst case was O(n) |
| put (expected) | O(1) | O(1) | O(log n) | plus amortized resize cost |
The catch — treeification needs a comparator
Red-black ordering needs to compare keys. If two keys have the same hash but the key type does not implement Comparable, the tree falls back to comparing by identity hash and class name, and ties still need linear-ish tie-breaking. So O(log n) is the guarantee specifically when keys are mutually Comparable; otherwise the bound is softer but the tree still bounds the damage far better than a flat list.