---

🟢 Junior Level

Short Interview Answer (30 Seconds)

HashMap is an associative array (key-value data structure) built on a hash table using open hashing and separate chaining.

Internally, HashMap stores entries in an array of buckets (Node<K,V>[] table), whose capacity is always a power of two ($16, 32, 64\dots$). When a key-value pair is inserted, the key’s hash code is computed and converted into an array index using a fast bitwise mask: index = (n - 1) & hash. If the target bucket is empty, a new Node is stored there. If a collision occurs (different keys mapping to the same bucket index), entries form a singly linked list. Starting in Java 8, if a single bucket reaches 8 elements and the total table capacity is at least 64, the linked list transforms into a balanced Red-Black Tree (TreeNode), guaranteeing $O(\log n)$ lookup performance even under severe collision spikes.

---

Comparison Table: Java Map Implementations

Map Implementation	Internal Data Structure	Time Complexity	Iteration Order Guarantee	Thread Safety
HashMap	Array + Linked Lists + Red-Black Trees	$O(1)$ average, $O(\log n)$ worst	❌ No order guarantee	❌ No (Fail-Fast iterators)
LinkedHashMap	Hash table + Doubly linked list of nodes	$O(1)$ average	✅ Insertion order (or access order)	❌ No
TreeMap	Red-Black Tree	$O(\log n)$ guaranteed	✅ Sorted by key (Comparable/Comparator)	❌ No
ConcurrentHashMap	Array of buckets + CAS + node-level locks	$O(1)$ average	❌ No order guarantee	✅ Yes (Thread-safe, non-blocking reads)

---

Basic Java 21 Example

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

public class HashMapBasicsDemo {
    public static void main(String[] args) {
        // Default constructor: capacity = 16, loadFactor = 0.75
        // Crucial detail: table array remains null until the very first put() call (lazy allocation)!
        Map<String, Integer> userAges = new HashMap<>();

        // 1. Inserting entries (put)
        userAges.put("Alice", 30); // Hash calculated -> index computed -> node placed
        userAges.put("Bob", 25);
        userAges.put(null, 99);    // null key is always mapped to table[0]

        // 2. Retrieving entries (get)
        System.out.println("Alice's age: " + userAges.get("Alice")); // O(1) average

        // 3. Overwriting values (when hash and equals match)
        userAges.put("Alice", 31); // Overwrites 30 with 31, returns previous value 30

        System.out.println("Map size: " + userAges.size());
    }
}

---

🟡 Middle Level

Lifecycle of the put(key, value) Operation

The insertion algorithm in OpenJDK HotSpot executes the following sequential steps:

                  put(key, value)
                         │
                         ▼
             key == null ? hash = 0 
        : hash = (h = key.hashCode()) ^ (h >>> 16)
                         │
                         ▼
                table == null or empty?
               ├── Yes ──► Invoke resize() (allocates array of 16)
               └── No
                         │
                         ▼
              index = (table.length - 1) & hash
                         │
                         ▼
                   table[index] == null?
          ├── Yes ──► Create Node<K,V> and assign to table[index]
          └── No (COLLISION DETECTED!)
                         │
                         ▼
              Does first node match key?
      (p.hash == hash && (p.key == key || key.equals(p.key)))
          ├── Yes ──► Overwrite value and return old value
          └── No ──► Check node type:
                       ├── TreeNode ──► Insert into Red-Black Tree
                       └── Node (List) ──► Traverse linked list:
                              ├── Key found ──► Overwrite value
                              └── End reached ──► Append new Node to tail
                                         │
                                         ▼
                            Bucket length >= 8?
                           ├── Yes ──► treeifyBin() (treeify or resize)
                           └── No ──► Continue
                         │
                         ▼
         Increment modCount and size; size > threshold?
               ├── Yes ──► Invoke resize() (double capacity)
               └── No ──► Return null

---

Why Table Capacity is Always a Power of Two ($2^n$)

In HashMap, the bucket index is computed using:

int index = (n - 1) & hash;

where $n$ is the current table capacity (table.length).

Mathematical and Architectural Reasons:

1. Replacing Modulo with Bitwise Masking: In mathematics, computing an array slot via modulo division ($hash \pmod n$) requires the CPU integer division instruction (idiv), which consumes 20–40 clock cycles. When $n$ is strictly a power of two ($2^k$), the mathematical operation $hash \pmod{2^k}$ is identical to a bitwise AND with $(2^k - 1)$, which executes in a single CPU clock cycle.
2. Uniform Mask Distribution: If $n = 16$ (0001 0000_b), then $n - 1 = 15$ (0000 1111_b). The lowest 4 bits are all binary 1s. This guarantees that every low-order bit of the computed hash code directly determines the target bucket index. If capacity were an odd or arbitrary number (e.g., 15, mask 14 = 1110_b), the least significant bit of the index would always be 0, meaning all odd bucket indices would remain permanently empty.

---

Hash Perturbation Function (Bitwise Spread)

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Why the >>> 16 Shift and XOR are Essential:

Standard Java objects return a 32-bit signed int from hashCode(). In small maps (e.g., $n = 16$), the index mask (n - 1) = 15 accounts only for the lowest 4 bits. The upper 28 bits of the hash code are completely ignored!
If a set of keys shares identical low-order bits while varying in high-order bits, they would all collide into the exact same bucket.
The perturbation (h ^ (h >>> 16)) folds the upper 16 bits of entropy into the lower 16 bits. Consequently, variation across any of the 32 bits of the original hash code influences bucket selection.

---

🔴 Senior Level

HotSpot Memory Layout: Node Memory Overhead

In high-throughput enterprise systems, storing millions of entries in a HashMap creates substantial heap pressure due to node object wrapper overhead:

Anatomy of Node<K, V> on a 64-bit JVM with Compressed OOPs (-XX:+UseCompressedOops):

1. Object Header: 12 bytes (8-byte Mark Word + 4-byte Compressed Klass Pointer);
2. int hash: 4 bytes;
3. final K key: 4 bytes (compressed object reference);
4. V value: 4 bytes (compressed object reference);
5. Node<K,V> next: 4 bytes (compressed reference to next node);
6. Padding (8-byte boundary alignment): 4 bytes.
   Total: Exactly 32 bytes just for the Node wrapper shell (excluding the actual key and value objects)!

Anatomy of TreeNode<K, V>:

TreeNode extends LinkedHashMap.Entry and contains parent, left, right, prev pointers and a boolean red flag. Its memory footprint is 56–64 bytes (approximately double that of a standard list node).

---

Java 8+ Resize Mechanics: Bitwise Splitting Without Re-Hashing

In Java 7, table expansion (resize()) recalculated every element’s bucket index via hash % newCapacity and inserted elements at the head of the new list (Head Insertion), which inverted element order and caused infinite loops under multithreaded race conditions.

In Java 8+, the algorithm was completely redesigned: doubling capacity ($oldCap \to 2 \times oldCap$) shifts the bitmask to expose exactly one new significant bit at the position corresponding to oldCap.

oldCap = 16  (Bitmask: 0000 1111)
newCap = 32  (Bitmask: 0001 1111)
Mask differential is bit 16: (0001 0000)

HotSpot tests this single bit using: (e.hash & oldCap) == 0:

• If 0, the element retains its existing bucket index in the new table (newIndex = oldIndex);
• If 1, the element shifts by exactly the old capacity: newIndex = oldIndex + oldCap.

// Snippet from HashMap.resize() in OpenJDK HotSpot:
Node<K,V> loHead = null, loTail = null; // List staying at old index
Node<K,V> hiHead = null, hiTail = null; // List moving to (oldIndex + oldCap)
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null) loHead = e;
        else loTail.next = e;
        loTail = e;
    } else {
        if (hiTail == null) hiHead = e;
        else hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

Elements are partitioned into two lists preserving original insertion order (Tail Insertion), eliminating cyclic pointer corruption.

---

Poisson Distribution and the Treeification Threshold of 8

Why did JDK architects select TREEIFY_THRESHOLD = 8?

The OpenJDK source documentation references probability theory: under a well-distributed hash function and default load factor of $0.75$, bucket population frequencies follow a Poisson distribution with average parameter $\lambda \approx 0.5$:

\[P(k) = \frac{e^{-\lambda} \lambda^k}{k!}\]

Probability of a bucket holding $k$ elements:

• 0 elements: $0.6065$
• 1 element: $0.3032$
• 2 elements: $0.0758$
• 3 elements: $0.0126$
• …
• 8 elements: $0.00000006$ ($6 \times 10^{-8}$)

The probability of any bucket reaching a depth of 8 under legitimate hash codes is less than one in ten million. Treeification was introduced primarily as defense against Hash Flooding DoS attacks, where malicious clients craft colliding keys to degrade lookup times to $O(n)$.

---

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

HashMap is a hash table built upon an array of buckets (Node<K,V>[] table) with power-of-two capacity. Bucket indices are computed via bitwise AND (n - 1) & hash, where hash folds the top 16 bits of hashCode() into the lower 16 bits. Collisions are handled using separate chaining. If a bucket’s list length reaches 8 and overall table capacity $\ge 64$, the bucket transforms into a balanced Red-Black Tree ($O(\log n)$). When resizing, capacity doubles and elements are split into lo and hi lists based on (hash & oldCap) == 0 without re-hashing. HashMap is non-thread-safe and fail-fast.

---

2. 4 Tricky Questions with Deep Answers

Question 1: Why does reaching 8 elements in a bucket not always produce a Red-Black Tree, and what secondary condition must be satisfied?

Answer: For a bucket to convert into a Red-Black Tree in treeifyBin(), two conditions must hold simultaneously:

1. Bucket chain length $\ge 8$ (TREEIFY_THRESHOLD);
2. Total table capacity table.length $\ge 64$ (MIN_TREEIFY_CAPACITY).
   If a bucket reaches 8 elements but table capacity is below 64 (e.g., 16 or 32), treeification does not occur. Instead, resize() is invoked to double the array size. JDK architects determined that in small tables, collisions are usually due to insufficient capacity; resizing redistributes nodes more efficiently than allocating heavy TreeNode objects.

Question 2: How does the bitwise split optimization (loHead/hiHead) work during resize in Java 8+, and why did it eliminate Java 7’s infinite loop bug?

Answer: In Java 7, resizing inserted nodes at the head of the new list (Head Insertion), reversing element order. Under concurrent resize races, competing threads could manipulate pointers such that A.next = B became B.next = A, creating a circular reference and causing 100% CPU lockups on subsequent get() calls.
Java 8+ uses Tail Insertion and bitwise testing (e.hash & oldCap) == 0. In a single pass, nodes are split into two chains (lo keeping oldIndex, hi moving to oldIndex + oldCap) preserving original order, eliminating cyclic reference bugs.

Question 3: Why does the hash() function XOR the top 16 bits with the bottom 16 bits (h ^ (h >>> 16))?

Answer: Default HashMap capacities are modest (16, 32, 64), so the index mask (n - 1) only preserves the lowest 4–6 bits of the hash. If keys have hash codes that differ primarily in their upper bits (e.g., memory pointers, integer multiples of 1,000, or formatted strings), all keys would map to the same bucket without the shift. XORing the upper 16 bits down ensures that entropy across all 32 bits affects the low-order bits, distributing entries uniformly across buckets.

Question 4: Why was 6 chosen as the threshold to convert a tree back into a list (UNTREEIFY_THRESHOLD), instead of 7 or 8?

Answer: The two-element difference between TREEIFY_THRESHOLD (8) and UNTREEIFY_THRESHOLD (6) provides hysteresis. If both thresholds were adjacent (e.g., 8 and 7), repeatedly adding and removing an 8th element would trigger continuous, costly conversions between linked lists and Red-Black Trees (structure thrashing/flapping). The 2-element gap stabilizes internal structures against frequent minor variations in collection size.

---

3. Common Pitfalls and Red Flags

❌ “HashMap allocates its internal table array immediately upon new HashMap<>().”
Correction: The constructor only initializes loadFactor and calculates initial threshold. The table array is allocated lazily during the first put() invocation inside resize().

❌ “Bucket index is computed using modulo division hash % capacity.”
Correction: It uses bitwise AND (capacity - 1) & hash, which executes in 1 clock cycle compared to 20–40 cycles for division.

❌ “A Red-Black Tree is created immediately whenever any bucket reaches 8 elements.”
Correction: Only if total table capacity is at least 64. If capacity is under 64, resize() is invoked instead.

---

4. Related Questions

• What is a Bucket in HashMap
• How HashMap Determines Which Bucket to Put an Element In
• What is a Collision in HashMap
• How HashMap Handles Collisions
• What Happens When 8 Elements Are Reached in One Bucket