Why do many hash tables use a power-of-two capacity with a bitmask instead of modulo?

A strong answer

To map an arbitrary 64-bit hash code into an array of capacity slots, a hash table needs a remainder in the range 0 to capacity - 1. In general, hash % capacity requires an integer division instruction (div or idiv on x86-64), which costs roughly 10 to 30 CPU cycles and cannot be easily pipelined. When capacity is a power of two ($2^k$), the remainder is simply the lowest $k$ bits of the hash. The table can compute the slot with a single bitwise AND instruction: hash & (capacity - 1), which executes in 1 cycle.

The trade-off is that hash & (capacity - 1) ignores all bits above the lowest $k$ bits. If the hash function has weak avalanche properties in its low bits—for example, if keys are multiples of 16 or pointers aligned to 8-byte boundaries—every key's low bits are identical, and they all collide in the same small subset of slots even while the rest of the table sits empty.

Prime-sized tables using hash % prime naturally mix information from all bits of the hash into the remainder, making them more forgiving of weak hash functions. Power-of-two tables solve this without giving up fast bitmasking by applying a fast finalizer or bit-mixing step (such as XORing the high bits into the low bits, h ^ (h >>> 16) in Java's HashMap, or using a mixing constant from MurmurHash/wyhash) before applying the mask.

What the interviewer is listening for

• The mathematical identity: for $C = 2^k$, h % C equals h & (C - 1) for unsigned integers.
• The hardware reason: integer division takes 10–30 cycles, whereas bitwise AND takes 1 cycle.
• The pitfall of masking: it discards the upper bits, so patterns in the low bits cause severe clustering unless the hash is mixed first.

Common mistakes

• Writing hash & capacity instead of hash & (capacity - 1) (which only produces 0 or capacity).
• Applying % to a signed integer in languages like C, C++, or Java without masking the sign bit, which can produce a negative array index.
• Assuming power-of-two sizing is always better without mentioning the need for bit mixing or finalizers.