Why Does HashMap Require a Power‑of‑Two Capacity? Unveiling tableSizeFor

We previously discussed secondary hashing; now we examine HashMap's initial capacity.

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

Constructs an empty HashMap with the specified initial capacity and load factor.

The constructor receives initialCapacity and loadFactor . It validates the arguments and then computes threshold by calling tableSizeFor(initialCapacity).

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;
}

Returns a power of two size for the given target capacity.

The method rounds the requested capacity up to the next power of two by first subtracting one, then propagating the highest set bit to all lower bits, and finally adding one.

Step‑by‑step illustration of the bit‑wise expansion:

After the bit‑wise filling, adding one yields the smallest power of two that is greater than or equal to the original capacity.

Why a Power‑of‑Two Capacity?

HashMap stores entries in an array Node<K,V>[] table. Lookup uses the index calculation (n - 1) & hash, where n is the array length. When n is a power of two, this expression is equivalent to hash % n but executed with a single bitwise AND, which is much faster.

transient Node<K,V>[] table;

Therefore, rounding the capacity to a power of two ensures uniform distribution of entries and optimal performance of the hash‑based indexing.