🔑 Section 10 · Question #21

When Can Time Complexity Become O(n)

While HashMap operates in average $O(1)$ constant time, lookup and insertion operations can degrade to linear $O(N)$ time under several architectural failure conditions:

🔑 HashMap equals hashCode 📄 Source Markdown

🟢 Junior Level

Short Interview Answer (30 seconds)

While HashMap operates in average $O(1)$ constant time, lookup and insertion operations can degrade to linear $O(N)$ time under several architectural failure conditions:

  1. Pathological Hash Code Implementation: If a custom key class implements a broken hashCode() method (e.g., returning a constant like return 42;), all entries cluster into a single bucket.
  2. Small Table Capacity (capacity < 64): When 8 collisions occur in a single bucket, Red-Black tree conversion is suppressed if total table capacity is below 64. The bucket remains an $O(N)$ linked list while the map expands via resizing.
  3. Non-Comparable Keys with Identical Hash Codes: If colliding keys in a tree do not implement Comparable<K>, TreeNode.find() cannot determine branching directions and must recursively traverse both left and right subtrees, degrading tree search to $O(N)$.
  4. Sparse Table Iteration: Full-table traversals (keySet(), entrySet()) run in $O(\text{Capacity} + N)$ time, scanning thousands of empty slots in oversized tables.

Demonstration of a Pathological Key in Java 21

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

// Catastrophic Key: Always returns a constant hash
public class BrokenKey {
    private final String id;

    public BrokenKey(String id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return 42; // 💥 All keys route to the exact same bucket!
    }

    @Override
    public boolean equals(Object obj) {
        return (obj instanceof BrokenKey other) && Objects.equals(this.id, other.id);
    }

    public static void main(String[] args) {
        Map<BrokenKey, String> map = new HashMap<>();
        for (int i = 0; i < 1000; i++) {
            map.put(new BrokenKey("id_" + i), "Value" + i);
        }
        // Every get() operation now traverses the entire collision chain!
        System.out.println("Retrieved: " + map.get(new BrokenKey("id_999")));
    }
}

Real-World Analogy: Imagine an archive office with 100 filing drawers. If an archivist mistakenly dumps every single client folder into Drawer #1, finding any document requires rummaging through all papers one by one ($O(N)$), while the other 99 drawers sit completely empty.

🟡 Middle Level

Comparative Breakdown of Degradation Scenarios

Scenario Root Cause Time Complexity Mitigation Strategy
Java 7 Legacy Runtimes No treeification; all collisions resolved via linked lists $O(N)$ Upgrade to Java 8+
capacity < 64 with collisions Table doubles capacity instead of converting to tree $O(N)$ (during growth) Proper hashCode(), pre-size initial capacity $\ge 64$
Colliding Keys without Comparable TreeNode.find cannot determine branching direction $O(N)$ Implement Comparable<K> on key class
Hash Flooding DoS Attacks Adversary crafts keys producing identical hash codes $O(N)$ (Java 7) / $O(\log N)$ (Java 8+) Use String or implement Comparable
Sparse Table Iteration Scanning empty null slots in array $O(\text{Capacity} + N)$ Pre-size accurately; use LinkedHashMap for iteration

The MIN_TREEIFY_CAPACITY = 64 Threshold

In Java 8+, converting a linked list to a Red-Black tree (TreeNode) requires meeting two distinct conditions:

  1. Single-bucket collision count reaches TREEIFY_THRESHOLD = 8, AND
  2. Total table capacity satisfies: \(\text{table.length} \ge 64\)
// OpenJDK HashMap.java treeifyBin() logic:
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // MIN_TREEIFY_CAPACITY = 64
        resize(); // Resizes instead of treeifying!
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // Build Red-Black Tree (TreeNode)
    }
}

When using default new HashMap<>() (initial capacity 16) with colliding keys:

  • 8th collision in one bucket $\to$ table resizes to 32 (remains an $O(N)$ linked list).
  • 9th collision in that bucket $\to$ table resizes to 64 (remains an $O(N)$ linked list).
  • Only once capacity reaches 64 does the next collision convert the bucket to a Red-Black tree with $O(\log N)$ search time.

🔴 Senior Level

The Java 8+ Treeification Myth: Why TreeNode Degrades to $O(N)$

Many developers believe that in Java 8+, worst-case HashMap performance is guaranteed to be $O(\log N)$. This is a dangerous misconception.

Examine the find() search method inside OpenJDK’s HashMap.TreeNode:

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> q, pl = p.left, pr = p.right;
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr; // Directed binary tree descent O(log N)
        else if ((q = pr.find(h, k, kc)) != null) // ⚠️ DANGER ZONE!
            return q;
        else
            p = pl; // Recursive search down BOTH branches!
    } while (p != null);
    return null;
}

How the Degeneracy Happens:

  1. When all keys share the exact same hash code (ph == h), binary branching by hash value is impossible.
  2. HashMap attempts to resolve a comparable comparator via comparableClassFor(k).
  3. If the key class DOES NOT implement Comparable<K>:
    • The tree cannot determine whether the key belongs in the left or right branch (dir is unknown).
    • The algorithm initiates a recursive scan down the right subtree: pr.find(h, k, kc).
    • If the element is not found there, it falls back to traversing the left subtree: p = pl.
    • Result: The search performs a complete traversal of all nodes in the tree. Looking up an absent key visits every single element in the bucket, degenerating to strictly $O(N)$!

Hash Flooding DoS Attacks (CVE-2011-4858)

In late 2011, security researchers exposed a critical algorithmic vulnerability across web servers (Tomcat, Jetty, PHP, Node.js). An attacker submitted a single HTTP POST request containing thousands of form parameters whose names were precalculated to yield identical hash codes in Java (e.g., "AaAa", "BBBB", "AaBB", "BBAa" all produce hash 2060436).

In Java 7:

  • The servlet engine placed parameters into a standard HashMap<String, String>.
  • All $N$ parameters accumulated into a single bucket as a linked list.
  • Inserting $N$ items required checking equals() across the growing list on every put(), taking: \(\sum_{i=1}^{N} i = \frac{N(N-1)}{2} = O(N^2) \text{ operations}\)
  • A payload of 50,000 parameters pegged a CPU core at 100% for several minutes, causing Denial of Service.

In Java 8+: The String class implements Comparable<String>. When collisions occur, the bucket converts to a Red-Black tree, reducing total batch insertion time from $O(N^2)$ to $O(N \log N)$ and neutralizing the attack.

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

HashMap complexity degrades to $O(N)$ when: (1) broken hashCode() implementations cluster all keys into one bucket without Comparable, (2) capacity is below 64, suppressing treeification, (3) on legacy Java 7 runtimes, (4) on single put() operations that trigger table resizing, or (5) when searching for non-existent keys in a Red-Black tree where keys share hashes but omit Comparable. Iteration is $O(\text{Capacity} + N)$ by design.

2. 4 Tricky Interview Questions with Deep Answers

Question 1: If a key class has hashCode() { return 1; } and omits Comparable, what is the time complexity of map.get() across 1,000,000 entries in Java 21?

Answer: The complexity is strictly $O(N)$. Because all hash codes are identical, all entries reside in a single bucket. While the bucket converts to a TreeNode tree (since capacity $> 64$), TreeNode.find() cannot invoke compareTo() to choose a branch. When searching for a non-existent key, the algorithm recursively searches both the left and right subtrees of every node, traversing all 1,000,000 nodes in linear $O(N)$ time.

Question 2: Why can a single put() operation take $O(N)$ time in a collision-free HashMap?

Answer: This occurs during a resize() event. When an insertion pushes size > threshold (e.g., adding the 13th element in a default map), HashMap allocates a new array of double capacity and migrates all $N$ existing nodes. While the amortized sequence cost of insertions is $O(1)$, that single resizing invocation executes in $O(N)$ time.

Question 3: Is iterating over map.keySet() taking $O(N)$ considered an architectural degradation?

Answer: No, this is normal algorithmic behavior. HashMap iteration complexity is $O(\text{Capacity} + N)$. The iterator must sequentially scan every slot in the table array. In sparsely populated maps (e.g., 5 elements in a table of 1,000,000 slots), the iterator spends most of its time evaluating empty null slots ($O(\text{Capacity})$). For workloads requiring frequent iteration over sparse datasets, LinkedHashMap should be used instead, which maintains a contiguous doubly linked list with $O(N)$ iteration.

Question 4: Why does treeifyBin() check tab.length < 64 instead of converting to a tree immediately at 8 collisions?

Answer: Building a Red-Black tree incurs substantial overhead:

  1. TreeNode objects consume 56–64 bytes of heap space (versus 32 bytes for a standard Node).
  2. Tree balancing requires node object allocations, color flips, and pointer rotations.

When capacity is small ($< 64$), clustering is typically an artifact of a narrow bitmask rather than a pathological hash function. Resizing doubles the array, introducing a new high bit into the index mask that statistically splits the 8-node chain into two shorter chains with a 50% probability, avoiding the memory overhead of treeification.

3. Common Pitfalls & Red Flags

  • ❌ “Java 8 guarantees that worst-case HashMap lookup is always O(log N).”
    Correction: It is only $O(\log N)$ if keys implement Comparable<K>. Without Comparable, search in a collided tree degrades to full-tree traversal ($O(N)$).

  • ❌ “HashMap iteration runs in O(N) where N is map.size().”
    Correction: Iteration runs in $O(\text{Capacity} + N)$, penalizing oversized empty tables.

  • ❌ “A single put() operation always executes in O(1) time.”
    Correction: Individual put() operations that trigger resize() run in $O(N)$ time.

  • ❌ “Treeification occurs immediately whenever any bucket reaches 8 elements.”
    Correction: Treeification only occurs if total capacity is at least 64; otherwise, the map resizes.