---

🟢 Junior Level

Short Interview Answer (30 Seconds)

HashMap determines the target bucket index for storing or locating an entry through a strict three-stage pipeline:

1. Obtaining the key’s hashCode(): The JVM invokes int h = key.hashCode() to obtain a 32-bit integer signature. For a null key, the hash is always defined as 0.
2. Bitwise Perturbation (Hash Spread Function): The upper 16 bits of the raw hash are XOR-ed with the lower 16 bits: hash = h ^ (h >>> 16). This spreads high-bit entropy to the lower bits, preventing collision clusters in small tables.
3. Applying the Bitwise Mask: The bucket index is computed using bitwise AND with the table capacity minus one: index = (table.length - 1) & hash. Because capacity is always a power of two ($2^n$), this operation is mathematically identical to modulo arithmetic ($hash \pmod{table.length}$), but executes in 1 CPU clock cycle.

---

Comparison Table: Bucket Addressing Mechanisms

Indexing Mechanism	Formula	CPU Cycles	Negative Hash Handling	Practical Usage
Bitwise AND	(n - 1) & hash	1 cycle	Guarantees non-negative index $[0, n-1]$	Java HashMap standard (requires $n = 2^k$)
Modulo Division	hash % n	20–40 cycles (idiv)	Produces negative indices!	Legacy approach; requires Math.abs
Universal Hashing	Murmur3 / CityHash	5–15 cycles	Handled by hash generator	Removed in Java 8 in favor of Treeification

---

Step-by-Step Index Calculation in Java 21

public class BucketCalculationDemo {
    public static void main(String[] args) {
        String key = "interview";
        int capacity = 16; // Default initial table capacity

        // Step 1: Raw 32-bit hashCode
        int h = key.hashCode(); // 1421060965 (binary: 01010100 10110001 01100111 01100101)

        // Step 2: Perturbation spread function
        int hash = (key == null) ? 0 : h ^ (h >>> 16);

        // Step 3: Power-of-two bitwise masking (n - 1 = 15 = 0000 1111)
        int index = (capacity - 1) & hash;

        System.out.println("Raw hashCode: " + h);
        System.out.println("Perturbed hash: " + hash);
        System.out.println("Final bucket index (0..15): " + index);

        // Special case: null key always maps to bucket index 0
        int nullIndex = (capacity - 1) & 0;
        System.out.println("Bucket index for null key: " + nullIndex);
    }
}

---

🟡 Middle Level

The Perturbation Function: Why the 16-Bit Shift is Essential

In OpenJDK HotSpot, HashMap.hash() is implemented as follows:

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

The Problem Without Perturbation:

Consider a table with default capacity $n = 16$. The index bitmask (n - 1) is $15$ (0000 0000 0000 0000 0000 0000 0000 1111_b).
Calculating the index via (n - 1) & hash utilizes only the lowest 4 bits. The upper 28 bits of the hash code are completely discarded.

If keys differ only in higher-order or middle bits (e.g., memory pointers, integer multiples of 16 or 32, formatted string identifiers):

Key 1: 00110000 00000000 00000000 00000001 -> index = 1
Key 2: 01010000 00000000 00000000 00000001 -> index = 1
Key 3: 11110000 00000000 00000000 00000001 -> index = 1

All these entries map to bucket index 1, producing an artificial collision disaster.

How h ^ (h >>> 16) Resolves This:

A Java int is 32 bits wide. The unsigned right shift h >>> 16 shifts the upper 16 bits into the lower 16-bit positions. The bitwise XOR combines the upper 16 bits with the lower 16 bits. Any variation in the high-order bits will change the lower bits, distributing entries uniformly across buckets even when keys produce sequential or clustered hash codes.

---

Hash Caching in the Node Structure (Node.hash)

Every allocated node stores the calculated perturbed hash in an immutable field:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // Cached perturbed hash value
    final K key;
    V value;
    Node<K,V> next;
    // ...
}

Why Hash Caching is Vital:

1. Short-Circuit Rejection During Lookups: When traversing a collision chain during get(key), HotSpot checks:

   if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
   

   Comparing integer primitives (p.hash == hash) executes in sub-nanosecond time in CPU registers. If hashes do not match, the expensive key.equals(k) method (which for strings requires byte-by-byte array iteration) is never invoked!

2. Instant Resizing: When table capacity doubles, key.hashCode() does not need to be recomputed; HotSpot directly reads the cached p.hash.

---

🔴 Senior Level

The Sign Bit Problem and Negative hashCode() Values

In Java, int is a signed two’s complement integer (ranging from $-2^{31}$ to $2^{31} - 1$). Any object’s hashCode() can return a negative integer:

"polygenelubricants".hashCode(); // -1257093246
Integer.valueOf(-42).hashCode(); // -42
Integer.MIN_VALUE;               // -2147483648

Why Modulo Division (%) is Dangerous:

If an implementation uses modulo division:

int index = hash % table.length; // -42 % 16 = -10 (NEGATIVE INDEX!)

Accessing table[-10] throws an ArrayIndexOutOfBoundsException.
Attempting to fix this using Math.abs(hash) % table.length contains a subtle trap: Math.abs(Integer.MIN_VALUE) still returns a negative number (Integer.MIN_VALUE) because its positive counterpart cannot be represented in a 32-bit signed integer!

Bitwise Masking as an Invariant Solution:

With the formula (n - 1) & hash: When $n = 16$, the mask $(n - 1) = 15$ has binary representation: 00000000 00000000 00000000 00001111
The most significant bit (the sign bit) of the mask is always 0. Bitwise AND inherently forces the sign bit to 0, guaranteeing a strictly non-negative index within $[0, n - 1]$.

---

Evolution of Hash DoS Defense: Why MurmurHash Was Abandoned

In Java 7u6, to combat web server Denial-of-Service attacks (where attackers sent crafted HTTP form parameters with colliding hash codes), Oracle introduced Alternative String Hashing based on MurmurHash3 with a randomized per-JVM seed (hashSeed), activated via jdk.map.althashing.threshold.

Why Alternative Hashing Was Removed in Java 8:

1. Non-Deterministic Iteration Order: The random hashSeed caused HashMap iteration order to vary between JVM restarts, breaking serialization formats and customer unit tests that relied on stable iteration.
2. Computational Overhead: MurmurHash3 added substantial CPU cycle overhead to every map operation.
3. Treeification (TreeNode): Java 8 adopted a structural solution: keep the fast deterministic perturbation function h ^ (h >>> 16), but convert collision lists into balanced Red-Black Trees when depth reaches 8. This caps worst-case search complexity at $O(\log n)$ without breaking iteration determinism.

---

Micro-Optimization Analysis of HotSpot Key Matching

The key lookup expression in HotSpot’s HashMap.getNode():

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

is ordered strictly by computational cost:

1. p.hash == hash (Cheapest): Single-cycle register comparison. Filters out $>99.99\%$ of non-matching nodes in a collision chain.
2. (k = p.key) == key (Reference Equality): Compares heap addresses. If identical instances (e.g., interned strings or cached objects) are looked up, the costly equals() method is bypassed entirely.
3. key != null && key.equals(k) (Most Expensive): Invokes the virtual equals() method only when hashes match and object references differ, minimizing overhead on deep business object comparisons.

---

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

HashMap calculates the target bucket in three steps: it calls key.hashCode(), perturbs it via h ^ (h >>> 16) to blend higher-order entropy into the lower bits, and applies the bitwise mask (table.length - 1) & hash. Using bitwise AND instead of modulo division accelerates indexing by 20–40x and automatically eliminates negative indices without Math.abs(). The perturbed hash is permanently cached in Node.hash, enabling instant equality short-circuiting before invoking equals().

---

2. 4 Tricky Questions with Deep Answers

Question 1: What happens if key.hashCode() returns Integer.MIN_VALUE, and why is (n - 1) & hash safe against exceptions?

Answer: Integer.MIN_VALUE is 0x80000000 (binary 10000000 00000000 00000000 00000000). Modulo division MIN_VALUE % 16 or Math.abs(Integer.MIN_VALUE) % 16 produces -0 or a negative index, causing ArrayIndexOutOfBoundsException.
The formula (n - 1) & hash applies a bitmask whose sign bit is always 0. The bitwise AND between 15 (0x0000000F) and 0x80000000 evaluates cleanly to 0. It is mathematically impossible for (n - 1) & hash to return a negative number or an index outside $[0, n - 1]$.

Question 2: Why does HashMap store final int hash inside each Node, rather than re-calling key.hashCode() when needed?

Answer:

1. Search Performance: key.hashCode() is a virtual method invocation. In a bucket collision chain, calling hashCode() repeatedly wastes CPU cycles. Comparing the cached primitive p.hash == hash takes 1 CPU cycle.
2. Mutable Key Defense: If a key object is mutated after insertion and its hash changes, key.hashCode() would return a new value. Storing the original hash allows the table to still perform consistent bitwise splitting during resizing.
3. Resize Efficiency: During table doubling, splitting chains via (e.hash & oldCap) == 0 uses the cached hash directly without re-executing key hashing logic.

Question 3: Why was the randomized MurmurHash3 Alternative Hashing feature in Java 7 removed in Java 8?

Answer: Alternative Hashing generated a random salt (hashSeed) at JVM startup. Consequently, HashMap iteration order differed on every run, breaking applications, distributed protocols, and unit tests that inadvertently relied on predictable iteration sequences. Furthermore, computing MurmurHash3 incurred noticeable CPU penalties. In Java 8, Oracle solved Hash DoS attacks structurally: linked lists treeify into Red-Black Trees when bucket length reaches 8, capping worst-case performance at $O(\log n)$ deterministically.

Question 4: How does the short-circuit expression p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))) optimize lookups?

Answer: It executes an escalating three-tier evaluation:

1. p.hash == hash: Fast CPU register comparison. If hashes differ, it immediately aborts without reading object memory.
2. (k = p.key) == key: Pointer equality. If looking up the same instance in heap, equals() is skipped.
3. key != null && key.equals(k): Deep object comparison. Executed only as a last resort when hashes match and references differ.

---

3. Common Pitfalls and Red Flags

❌ “Bucket index is calculated via hashCode % capacity.”
Correction: It is calculated via bitwise AND: (capacity - 1) & hash, where hash is perturbed via h ^ (h >>> 16).

❌ “null.hashCode() is called when putting a null key.”
Correction: null is checked explicitly: key == null ? 0 : .... A null key always maps to bucket 0.

❌ “A perfect hashCode() guarantees no bucket collisions.”
Correction: Even if all 32-bit hash codes are unique, projecting them onto 16 buckets via a 4-bit mask guarantees collisions by the Pigeonhole Principle.

---

4. Related Questions

• How HashMap Works Internally
• What is a Bucket in HashMap
• What is a Collision in HashMap
• What is the equals() and hashCode() Contract
• Why String Is Often Used as a Key in HashMap