What is Capacity in HashMap

🟢 Junior Level

Short Interview Answer (30 seconds)

Capacity is the length of the internal bucket array (table.length) in a HashMap. It represents the total number of available slots for storing key-value pairs or the heads of collision linked lists and Red-Black trees.

Default Initial Capacity (DEFAULT_INITIAL_CAPACITY): 16 bucket slots.
Power of Two Invariant: The capacity of a HashMap is strictly a power of two ($2^n$): 1, 2, 4, 8, 16, 32, 64, 128, etc.
Maximum Capacity (MAXIMUM_CAPACITY): $2^{30} = 1,073,741,824$.

Code Demonstration in Java 21

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

public class CapacityDemo {
    public static void main(String[] args) {
        // 1. Default constructor: capacity = 16 (array allocated lazily on first put)
        Map<String, Integer> defaultMap = new HashMap<>();

        // 2. Custom initial capacity:
        // Requesting 30 -> HashMap rounds up to the next power of two (32)
        Map<String, Integer> customMap = new HashMap<>(30);

        customMap.put("alpha", 1);
    }
}

Real-World Analogy: Capacity is the number of PO boxes available in a mail sorting center. Even if only two letters have arrived (size = 2), there are 16 PO boxes ready for distribution (capacity = 16). The more boxes available, the lower the chance that two different letters will be sorted into the exact same box.

🟡 Middle Level

The Difference Between `size` and `capacity`

A frequent point of confusion in technical interviews:

size: The actual number of key-value mappings currently stored in the map. Queried via the public method map.size().
capacity: The physical length of the bucket array (table.length). There is no public map.capacity() method in the standard Java API (it is encapsulated as an internal implementation detail).

Why Must Capacity Always Be a Power of Two?

The performance of HashMap centers on how quickly it converts a 32-bit key hash code into a bucket array index.

Mathematically, bounding a hash value to the interval $[0, \text{capacity} - 1]$ requires a modulo remainder operation: $\text{index} = \text{hash} \pmod{\text{capacity}}$

However, the hardware integer division instruction (idiv) requires 15–40 CPU cycles. When $N$ is a power of two ($N = 2^k$), modulo arithmetic is mathematically identical to a bitwise AND with a mask of $(N - 1)$: $\text{index} = (n - 1) \ \& \ \text{hash}$

The bitwise & instruction executes on modern processors in a single CPU clock cycle.

What Happens If Capacity Is NOT a Power of Two?

Consider $n = 15$ (not a power of two): $n - 1 = 14_{10} = 00001110_2$ Because the lowest bit of the mask is 0, performing (15 - 1) & hash will always produce an even index (0, 2, 4, 6, 8, 10, 12, 14). All odd buckets (1, 3, 5, 7, 9, 11, 13) would remain permanently empty and unusable. Half of the allocated table would be wasted, and collision frequency would instantly double!

🔴 Senior Level

Bitwise Rounding Algorithm: `tableSizeFor()`

If a constructor receives an initial capacity that is not a power of two (e.g., new HashMap<>(10)), HashMap normalizes it using the tableSizeFor() algorithm:

// OpenJDK HashMap.java source:
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

Step-by-Step Breakdown:

Why cap - 1? If the requested capacity is already an exact power of two (e.g., 16), omitting the decrement would round it up to the next power of two (32).
Cascading Shifts (>>>) and Bitwise OR (|=):
- Once the most significant 1-bit (MSB) is located, n |= n >>> 1 propagates the 1-bit one position to the right (yielding two consecutive 1s).
- n |= n >>> 2 copies those two 1s two positions rightward (yielding four consecutive 1s).
- Subsequent shifts by 4, 8, and 16 ensure that all bits to the right of the MSB become 1 across the full 32-bit integer.
- For example, if cap = 10: $n = 9$ (00001001). The bitwise cascade turns it into 00001111 ($15_{10}$).
Adding 1 (n + 1): Adding 1 to a contiguous sequence of 1s (00001111 + 1) produces 00010000 ($16_{10}$), the next exact power of two.

Lazy Heap Allocation

Before the first key-value pair is inserted, the array Node<K,V>[] table does not exist on the heap (table == null).

The constructor new HashMap<>(initialCapacity, loadFactor) only validates arguments and records the calculated capacity into the threshold field:
```
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
```
Memory for the table array is allocated on the first put() invocation inside resize(). This saves dozens of megabytes across applications holding thousands of momentarily empty maps.

The `MAXIMUM_CAPACITY` Limit ($2^{30}$)

Why is the maximum capacity capped at $1 \ll 30$ ($1,073,741,824$) rather than $2^{31}$?

In Java, int is a signed 32-bit primitive ranging from $-2^{31}$ to $2^{31} - 1$. Shifting 1 left by 31 bits (1 << 31) produces Integer.MIN_VALUE ($-2,147,483,648$). Therefore, $2^{30}$ is the largest positive power of two representable within a signed 32-bit integer.

Memory Footprint of the Bucket Array

The table array stores references to Node<K,V> objects. Under 64-bit HotSpot with Compressed OOPs (-XX:+UseCompressedOops, active by default for heaps $< 32\text{GB}$):

Array header: 16 bytes (Mark Word 8B + Klass Word 4B + Array Length 4B).
Each bucket slot (reference to Node): 4 bytes.
8-byte object alignment padding.

Capacity	Heap Footprint (Compressed OOPs)	Heap Footprint (No Compressed OOPs)
16 (default)	$16 + (16 \times 4) = 80$ bytes	$24 + (16 \times 8) = 152$ bytes
1,024	$16 + (1024 \times 4) = 4,112 \implies \sim 4\text{ KB}$	$24 + (1024 \times 8) = 8,216 \implies \sim 8\text{ KB}$
1,048,576 ($2^{20}$)	$16 + (1048576 \times 4) \approx 4\text{ MB}$	$24 + (1048576 \times 8) \approx 8\text{ MB}$

Instantiating new HashMap<>(10_000_000) immediately claims $\sim 64\text{ MB}$ of heap space for the bucket array alone, before any payload data is inserted.

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

Capacity is the length of HashMap’s internal table array. It defaults to 16 and is strictly constrained to powers of two ($2^n$, up to $2^{30}$) so that bucket index calculation can use the 1-cycle bitmask (capacity - 1) & hash instead of the 40-cycle modulo division hash % capacity. tableSizeFor() uses bit-propagation shifts to round up any user-specified capacity. The array is allocated lazily on the first put() invocation.

2. 4 Tricky Interview Questions with Deep Answers

Question 1: What happens if you pass initial capacity 0 (`new HashMap<>(0)`)? What will the capacity be?

Answer: The constructor completes successfully:

initialCapacity < 0 check passes (0 is permitted).
tableSizeFor(0) computes n = 0 - 1 = -1. The ternary check (n < 0) ? 1 : ... returns 1. The threshold field is initialized to 1.
On the first put(), resize() initializes table with capacity = 1.
The operational threshold becomes (int)(1 * 0.75f) = 0.
On inserting the first element, if (++size > threshold) (1 > 0) evaluates to true, immediately triggering a second resize() that doubles capacity to 2.

Question 2: Can you retrieve the current capacity of an existing `HashMap` without using reflection?

Answer: The standard java.util.HashMap public API does not expose a capacity() method. However, it can be determined indirectly:

Via Java Serialization: HashMap writes its capacity to the output stream via s.writeInt(table.length).

Via reflection accessing the private table field:

Field field = HashMap.class.getDeclaredField("table");
field.setAccessible(true);
Object[] table = (Object[]) field.get(map);
int capacity = (table == null) ? 0 : table.length;

Question 3: Why doesn’t `Hashtable` require capacity to be a power of two, while `HashMap` does?

Answer: Hashtable computes bucket indices using modulo arithmetic: (hash & 0x7FFFFFFF) % tab.length. Its default capacity is 11 (a prime number), and it resizes via (oldCapacity << 1) + 1 to maintain odd numbers that scatter hash codes naturally. HashMap chose single-cycle bitmask indexing (capacity - 1) & hash, which requires a power of two. To compensate for losing the prime-number dispersion property, HashMap introduced the perturbation bit-shift spread function (h = key.hashCode()) ^ (h >>> 16).

Question 4: What happens if a `HashMap` reaches `MAXIMUM_CAPACITY` ($2^{30}$) and continues to receive new entries?

Answer: No exception is thrown. In resize(), HotSpot checks:

if (oldCap >= MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return oldTab;
}

The table permanently freezes array resizing. The threshold is set to Integer.MAX_VALUE ($2^{31} - 1$). All subsequent elements are inserted into existing buckets, lengthening collision chains and Red-Black trees. Query complexity degrades from $O(1)$ to $O(\log N)$ for treeified buckets and $O(N)$ for linked list buckets.

3. Common Pitfalls & Red Flags

❌ “Capacity is the number of elements in the map.”
Correction: That is size. Capacity is the total number of bucket slots in the backing array.
❌ “Calling new HashMap<>(10) allocates an array of length 10.”
Correction: It rounds up to 16 via tableSizeFor().
❌ “Oversizing capacity is harmless if we have enough RAM.”
Correction: Iterating over a 1,000,000-capacity map containing 10 elements requires scanning 1,000,000 slots, causing massive iteration latency ($O(\text{capacity} + \text{size})$).
❌ “The table array is allocated immediately inside new HashMap().”
Correction: Allocation is lazy; the array remains null until the first put() call.

What is a Bucket in HashMap — Internal bucket mechanics
How HashMap Determines Which Bucket to Put an Element In — Index bitmasking math
What is Load Factor in HashMap — Fill ratio and resizing threshold
When Does Rehashing Occur in HashMap — Threshold triggers
How to Choose the Initial Capacity for HashMap — Presizing best practices