---

🟢 Junior Level

Short Interview Answer (30 seconds)

In HashMap, core operations (get, put, remove, containsKey) execute in average $O(1)$ constant time, running almost instantaneously regardless of the total number of entries in the map.

Why It Executes in $O(1)$ Time:

1. Instant Address Calculation: The 32-bit key hash code directly maps to the exact bucket index in 1–2 CPU clock cycles.
2. Direct Memory Addressing: Reading array element table[index] is an immediate single-instruction dereference ($O(1)$).
3. Minimal Comparisons: Under a uniform hash distribution, each bucket contains at most 1–2 nodes on average. The target entry is verified in a single comparison.

---

Code Demonstration in Java 21

import java.util.HashMap;
import java.util.Map;

public class ComplexityDemo {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();

        // Insertion: O(1) amortized
        map.put("user_101", "Slava");

        // Lookup: O(1) average
        String name = map.get("user_101");

        // Deletion: O(1) average
        map.remove("user_101");
    }
}

Real-World Analogy: Imagine a coatroom holding 1,000,000 coats, each tagged with a unique ticket number from 1 to 1,000,000. To retrieve a coat, the attendant does not inspect all 1,000,000 hangers sequentially ($O(N)$); they walk directly to the hanger matching the ticket number ($O(1)$).

---

🟡 Middle Level

Operation Complexity Summary Table

Operation	Best Case	Average Case	Worst Case (Java 7)	Worst Case (Java 8+)
get()	$O(1)$	$O(1)$	$O(N)$ (Linked List)	$O(\log N)$ (RB-Tree)*
put()	$O(1)$	$O(1)$ amortized	$O(N)$ (Linked List)	$O(\log N)$ (RB-Tree)*
remove()	$O(1)$	$O(1)$	$O(N)$ (Linked List)	$O(\log N)$ (RB-Tree)*
containsKey()	$O(1)$	$O(1)$	$O(N)$ (Linked List)	$O(\log N)$ (RB-Tree)*
Iteration (keySet/entrySet)	$O(C + N)$	$O(C + N)$	$O(C + N)$	$O(C + N)$

*Note: Worst-case performance in Java 8+ is strictly $O(\log N)$ provided keys implement Comparable<K>. If keys with colliding hashes do not implement Comparable, tree search degrades to $O(N)$.

---

Amortized Analysis of put()

The put() operation is classified as amortized $O(1)$, even though an individual insertion that triggers resize() requires $O(N)$ time to allocate a new array and migrate existing entries.

Aggregate Analysis Proof:

Capacity expands geometrically: $16 \to 32 \to 64 \to \dots \to N$. When inserting $N$ elements, the total number of node migration copies across all resize operations forms a convergent series: \(1 + 2 + 4 + 8 + \dots + \frac{N}{2} = N - 1 \text{ operations}\) Total operational steps across $N$ insertions: \(\text{Cost} = N \text{ (base insertions)} + (N - 1) \text{ (resize migrations)} < 2N\) Dividing total cost by $N$ insertions yields constant amortized time: \(\text{Amortized Cost} = \frac{2N}{N} = O(1)\)

---

Full-Table Iteration Complexity: $O(\text{Capacity} + \text{Size})$

The time required to iterate over a map (for (Map.Entry<K, V> e : map.entrySet())) depends on both the element count $N$ and the physical bucket array capacity $C$. The iterator must sequentially scan every slot in table[] from index $0$ to $\text{capacity} - 1$. Creating new HashMap<>(1_000_000) and inserting only 2 elements results in a slow iteration ($O(1,000,000)$) because the iterator must inspect 999,998 empty null slots.

---

🔴 Senior Level

Cycle-by-Cycle Breakdown of getNode() at the CPU Level

The physical latency of map.get() is governed by hardware microarchitecture:

// OpenJDK HashMap.getNode() logic:
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) { // Steps 1, 2, 3
        if (first.hash == hash && // Step 4
            ((k = first.key) == key || (key != null && key.equals(k)))) // Steps 5, 6
            return first;
        // ... traverse collision chain or Red-Black tree ...
    }
    return null;
}

1. Hash Perturbation (hash(key)): (h = key.hashCode()) ^ (h >>> 16) executes in 2–3 CPU clock cycles inside registers in $< 1\text{ ns}$.
2. Index Masking: (n - 1) & hash executes in a single CPU cycle.
3. Array Slot Read (tab[index]):
   • L1/L2 Cache Hit: 1–4 ns latency (if table segment is cached in CPU cache lines).
   • Main DRAM Cache Miss: 60–100 ns latency (if the map is large and cold in RAM).
4. 32-Bit Hash Comparison (first.hash == hash): 1 CPU cycle. Rapidly rejects non-matching entries without dereferencing object payload fields.
5. Reference Identity Check (first.key == key): 1 CPU cycle. If pointers match (e.g., String Pool literals), equals() is skipped entirely.
6. Key Equality Evaluation (key.equals(k)): 2–5 ns for small objects; for long strings, SIMD vectorization (ArraysSupport.mismatch) compares 128/256 bits per cycle.

---

Hardware Reality: CPU Cache Locality vs. Theoretical Asymptotics

While Red-Black trees guarantee $O(\log N)$ algorithmic complexity, physical pointer traversal can be significantly slower than contiguous memory scans:

• TreeNode objects are allocated at distinct times and reside at non-contiguous heap addresses.
• Navigating node.left and node.right pointers triggers repeated CPU Cache Misses (60–100 ns penalty each).
• Traversing a balanced tree of 15 elements (4 pointer dereferences) can take up to $4 \times 80 = 320\text{ ns}$. In contrast, a linear scan ($O(N)$) over a flat, contiguous 15-element array benefits from CPU hardware prefetchers, executing in only 10–15 ns.

---

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

HashMap provides average $O(1)$ time complexity for get(), put(), remove(), and containsKey(). Worst-case performance is $O(N)$ in Java 7 (linked list degradation) and $O(\log N)$ in Java 8+ (Red-Black treeification), provided keys implement Comparable<K>. Resizing costs $O(N)$, but geometric doubling ($2 \times$) guarantees amortized $O(1)$ insertion. Iteration complexity is $O(\text{Capacity} + \text{Size})$.

---

2. 4 Tricky Interview Questions with Deep Answers

Question 1: Can get() degrade to $O(N)$ in Java 8+ despite Red-Black trees?

Answer: Yes, it can. Red-Black trees require a binary search ordering. HashMap orders tree nodes using Comparable.compareTo(). If keys:

1. Share the exact same hashCode() (e.g., hardcoded return 42;), AND
2. Do NOT implement Comparable<K> (or compareTo() returns 0 for non-equal keys),

TreeNode.find() cannot determine whether to branch left or right. It is forced to recursively search both branches of the subtree, degrading tree search to a full traversal of all nodes: $O(N)$.

Question 2: Why is put() considered $O(1)$ when a single resize operation takes $O(N)$?

Answer: Algorithmic analysis distinguishes between worst-case single operation latency and amortized sequence cost. While an individual resize takes $O(N)$, table capacity doubles geometrically ($16 \to 32 \to 64 \dots$). Resizes occur with exponentially decreasing frequency as $N$ grows. The aggregate cost of copying elements across all resizes during $N$ insertions is bounded by $2N - 1$. The amortized cost per insertion is strictly bounded by a constant: $\frac{2N}{N} = O(1)$.

Question 3: What is the time complexity of map.size() and map.isEmpty()?

Answer: Strictly $O(1)$. HashMap maintains element count in a primitive field: transient int size;. The size() method returns this cached value in a single CPU cycle, and isEmpty() evaluates size == 0. No bucket traversal or node counting takes place (unlike pre-Java 8 ConcurrentLinkedQueue.size()).

Question 4: Why is iterating over a HashMap significantly slower than iterating over an ArrayList with the same number of elements?

Answer: ArrayList iteration is strictly $O(N)$ over contiguous memory, maximizing CPU cache line prefetching (64 bytes transferred per cycle). In contrast, HashMap iteration:

1. Runs in $O(\text{Capacity} + N)$ time: the iterator must scan every array slot in table[], wasting cycles checking null slots in sparsely populated maps.
2. Suffers from Pointer Chasing: each Node is an independent heap allocation, triggering frequent CPU L1/L2 cache misses upon dereferencing node.next.

---

3. Common Pitfalls & Red Flags

• ❌ “HashMap lookups are guaranteed to always be O(1).”
  Correction: $O(1)$ is the average-case expectation; worst-case latency is $O(\log N)$ or $O(N)$ under severe hash collisions.

• ❌ “Iterating through HashMap keys is O(N).”
  Correction: It is $O(\text{Capacity} + N)$, penalizing sparsely allocated maps.

• ❌ “Treeification guarantees O(1) worst-case performance.”
  Correction: Treeification caps worst-case search at $O(\log N)$, not $O(1)$.

• ❌ “Java 8 treeification works automatically for all key classes.”
  Correction: If keys colliding in a bucket do not implement Comparable, search degrades toward $O(N)$.

---

4. Related Topics

• When Can Time Complexity Become O(n) — $O(N)$ degradation triggers
• What is a Collision in HashMap — Collision mechanics and resolution
• What Happens When 8 Elements Are Reached in One Bucket — Treeification threshold
• What Happens During Rehashing — Array doubling and single-bit partitioning