---

🟢 Junior Level

Short Interview Answer (30 Seconds)

A bucket (or bin) in HashMap is an individual cell (slot) within the internal array Node<K,V>[] table.

The table array represents the primary hash table, and its length (table.length) is known as the capacity. Each bucket contains either null (if empty) or a reference to the head node stored at that index. When multiple entries hash to the same bucket index (a collision), they form a singly linked list linked via next pointers. Starting in Java 8, if a single bucket reaches 8 elements (and total table capacity is at least 64), the bucket is transformed into a balanced Red-Black Tree (TreeNode).

---

Comparison Table: Structural States of a Bucket

Bucket State	Internal Representation	Memory Footprint (RAM)	Lookup Time Complexity
1. Empty	table[i] == null	4 or 8 bytes (reference in array)	$O(1)$ — immediate null check
2. Single Node	Node<K,V> with next == null	32 bytes (wrapper) + key/value references	$O(1)$ — single key comparison
3. Collision List	Singly linked list of Node<K,V> (2 to 7 items)	32 bytes per node	$O(k)$, where $k \le 7$
4. Red-Black Tree	Balanced tree of TreeNode<K,V> ($\ge 8$ items)	~56–64 bytes per tree node	$O(\log k)$ — logarithmic search

---

Java 21 Demonstration

import java.util.HashMap;

public class BucketInspectionDemo {
    public static void main(String[] args) {
        // Instantiate HashMap (internal table array is still null!)
        HashMap<String, String> map = new HashMap<>();

        // On the first put(), table[] is allocated with 16 buckets (indices 0..15)
        map.put("Java", "Language");
        map.put("Kotlin", "Language");

        // Bucket index is determined by: index = (table.length - 1) & hash
        // The null key is always placed in bucket index 0:
        map.put(null, "DefaultValue");

        System.out.println("Total mappings in map: " + map.size());
    }
}

---

🟡 Middle Level

Bucket Addressing Mathematics: Why Capacity is Strictly $2^n$

The bucket index for an entry is calculated using the bitwise formula:

int index = (table.length - 1) & hash;

Why a Power of Two is Required:

1. Hardware Speed: The CPU integer division instruction (idiv) used for modulo ($hash \pmod n$) requires 20–40 clock cycles, whereas bitwise AND executes in a single CPU clock cycle.
2. Complete Bit Coverage: The number $(2^n - 1)$ in binary is a contiguous sequence of binary 1s:
   • $16 - 1 = 15 = 0000\,1111_b$
   • $32 - 1 = 31 = 0001\,1111_b$
   • $64 - 1 = 63 = 0011\,1111_b$
     This ensures that every low-order bit of the hash code has an equal opportunity to influence bucket slot selection.

---

The tableSizeFor(int cap) Method: Sizing Up to the Next Power of Two

When configuring a custom initialCapacity (e.g., new HashMap<>(10)), the JVM does not create an array of 10 slots. The internal algorithm rounds the number up to the nearest power of two:

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

Input value: 10  ──► tableSizeFor(10)  ──► capacity = 16
Input value: 17  ──► tableSizeFor(17)  ──► capacity = 32
Input value: 500 ──► tableSizeFor(500) ──► capacity = 512

---

Correct Sizing of initialCapacity

If you expect to store 1,000 entries, constructing new HashMap<>(1000) causes an unnecessary resizing step:

1. tableSizeFor(1000) rounds the capacity to 1024;
2. Growth threshold: threshold = 1024 * 0.75 = 768;
3. Inserting the 769th entry triggers an expensive resize, doubling the table to 2048!

Formula for Optimal Pre-Sizing:

\(\text{initialCapacity} = \left\lceil \frac{\text{expectedSize}}{\text{loadFactor}} \right\rceil + 1 = \left\lceil \frac{1000}{0.75} \right\rceil + 1 = 1335 \longrightarrow 2048\)

In Java 19+, use the standard factory method:

Map<String, User> userCache = HashMap.newHashMap(1000); // Automatically computes capacity 2048!

---

🔴 Senior Level

Memory Footprint Analysis: Heap Overhead vs. Cache Locality

In highload systems, engineers must account for the physical memory footprint of the bucket array:

Array Node<K,V>[] table:
- Length: N slots
- Each slot: Pointer reference (4 bytes with Compressed OOPs, 8 bytes without)
- Array object header in heap: 16 bytes

• With capacity = 16: $16 \times 4 + 16 = 80$ bytes.
• With an excessive initialCapacity = 1_000_000: an empty table consumes ~4 MB of RAM even before a single key-value entry is added!

Cache Locality in Separate Chaining:

Java’s HashMap uses Separate Chaining. In contrast to Open Addressing (Linear Probing)—where all keys and values reside contiguously in a flat array (as in Python’s dict or high-performance libraries like Eclipse Collections / Agrona):

• Node instances are allocated individually across disparate heap memory locations;
• Traversing a bucket collision list causes repeated CPU cache misses (L1/L2/L3);
• However, Separate Chaining was chosen for its graceful degradation: it does not suffer from Primary Clustering when load factor exceeds $0.7$, and deletion does not require complex tombstone markers.

---

Production Anomaly Analysis: Skewed Buckets

In production telemetry, uneven distribution across buckets (e.g., 95% of entries clustering in 2 or 3 buckets) indicates a broken hashCode() implementation:

// Worst-case bucket distribution scenario:
public class DefectiveKey {
    private final String id;
    public DefectiveKey(String id) { this.id = id; }
    
    // ❌ DISASTER: All entries collide into the same bucket (index = 0)!
    @Override
    public int hashCode() {
        return 42;
    }

    @Override
    public boolean equals(Object o) {
        return o instanceof DefectiveKey other && this.id.equals(other.id);
    }
}

In this scenario, HashMap degrades into a single Red-Black Tree, dropping operations to $O(\log n)$ with constant tree rebalancing penalties during inserts.

---

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

A bucket in HashMap is a slot in the internal array Node<K,V>[] table, indexed via (table.length - 1) & hash. It exists in one of 4 states: empty (null), single node, singly linked list (collisions up to 7 items), or Red-Black Tree (TreeNode at $\ge 8$ items when total capacity $\ge 64$). Table capacity is always a power of two, rounded up via tableSizeFor(). To avoid resizing penalties, pre-size using HashMap.newHashMap(expectedCount) in Java 19+.

---

2. 4 Tricky Questions with Deep Answers

Question 1: What is physically stored in array slot table[index] when multiple items collide in that bucket?

Answer: The slot table[index] contains a single reference (pointer) to the head node of the singly linked list Node<K,V> (or the root TreeNode<K,V>). All subsequent elements in the collision chain are linked sequentially via node.next pointers distributed across the JVM heap. The array table itself never expands multi-dimensionally; it is strictly a flat one-dimensional array of references.

Question 2: How does tableSizeFor(int cap) compute the nearest power of two without loops or branch conditions?

Answer: The method decrements the input by one (cap - 1) and calculates the number of leading zero bits using the CPU LZCNT instruction via Integer.numberOfLeadingZeros(). It then performs an unsigned right shift -1 >>> leadingZeros, filling all positions after the most significant bit with binary 1s (producing a bitmask like 000...01111111). Adding 1 yields the exact power of two ($2^k$). The calculation completes in 2–3 CPU cycles without looping.

Question 3: Why does Java’s HashMap utilize Separate Chaining rather than Open Addressing?

Answer: Open addressing places colliding elements into subsequent slots in the same array, offering superior CPU cache locality. However, it suffers from fatal drawbacks:

1. It degrades exponentially when load factor exceeds $0.5$ due to primary clustering;
2. Deletions require complex TOMBSTONE markers and periodic defragmentation;
3. Separate Chaining combined with Java 8 treeification provides a deterministic upper bound of $O(\log n)$ even under malicious collision attacks.

Question 4: How does the Poisson distribution justify setting TREEIFY_THRESHOLD = 8?

Answer: Under a uniform hashCode() and default load factor of $0.75$, key placement follows a Poisson distribution with $\lambda = 0.5$. The probability of 8 entries hashing into the exact same bucket by chance is approximately $P(8) \approx 6 \times 10^{-8}$ (six in one hundred million). This ensures that under normal operations, treeification almost never occurs, saving memory by avoiding heavy TreeNode allocations while providing insurance against Hash Flooding DoS attacks.

---

3. Common Pitfalls and Red Flags

❌ “Table capacity can be any even number.”
Correction: Table capacity is strictly constrained to powers of two ($2^n$). Passing 10 will round up to 16.

❌ “Calling new HashMap(100) accommodates 100 elements without resizing.”
Correction: 100 rounds up to capacity 128. With load factor 0.75, resize threshold is $128 \times 0.75 = 96$. Inserting the 97th entry triggers a resize.

❌ “Empty buckets consume zero memory.”
Correction: The table array itself allocates contiguous memory for references. A 1,000,000-slot table consumes ~4 MB of RAM even if completely empty.

---

4. Related Questions

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