HashMap Time Complexity

Direct Answer

HashMap.get() and put() are expected O(1) with well-distributed hashes. Heavy collisions require scanning or navigating one bucket. Current JDKs can treeify a large bin when the table is large enough, often improving collision-heavy lookup toward O(log n) for suitably orderable keys, but the public HashMap contract does not promise a universal O(log n) worst case.

Code Example

Each put and get hashes the key straight to a bucket — no scan — which is why both are constant time on average.

import java.util.*;

public class HashMapComplexity {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        // put: hash the key -> index -> place in bucket. O(1) average.
        map.put("sku-1", 100);
        map.put("sku-2", 200);

        // get: hash the key -> index -> read the bucket. O(1) average.
        Integer price = map.get("sku-1");   // 100

        // Worst case (all collide) is O(n), but since Java 8 a bucket
        // with > 8 entries becomes a red-black tree -> O(log n).
        // Note: iterating the whole map is always O(n + capacity).
        for (var e : map.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

The entrySet() loop is the exception — iterating the whole map is O(n + capacity), since it touches every bucket.

Common Mistakes & Pitfalls

• Saying always O(1): the correct description is expected O(1) with suitable hashes.
• Promising a universal O(log n) worst case: tree bins are an implementation strategy with key and operation nuances, not a public API guarantee.
• Ignoring mutable keys: a changed hash/equality value can make an entry unreachable by normal lookup.
• Confusing lookup and iteration: walking the whole map is O(capacity + size).
• Ignoring resize: growth is an occasional O(n) redistribution.