Why do production hash tables pick power-of-two capacities with bit masking over prime-modulo sizing?

## The index step is the hot path Every insert, lookup and removal begins the same way: take the key's hash, a value spread across the full width of a machine word, and turn it into a slot number in `0..capacity-1`. There are only two mainstream ways to do that, and the choice ripples through the whole design. **Remainder by a prime.** `index = hash mod capacity`, with capacity kept prime. A remainder by a prime blends every bit of the hash into the result, which is exactly the property you want if the hash is poor. If a key type produces hashes that are all multiples of 8 (a common accident when a hash is built from aligned addresses or from a field scaled by a constant), a prime modulus still scatters them, because no small factor is shared with the modulus. **Bit mask on a power of two.** `index = hash AND (capacity - 1)`. When capacity is a power of two, `capacity - 1` is a run of ones, so the AND keeps exactly the low `log2(capacity)` bits and discards everything above. One instruction, no latency worth mentioning, no data dependency beyond the hash itself. ## What the mask actually costs The mask is not free — it is cheap in instructions and expensive in assumptions. It reads only the low bits, so any two hashes agreeing on those bits collide, no matter how different they are higher up. That is not a hypothetical: a symbol table in an interpreter often keys on identifiers whose hashes were built by combining a scope tag with a name hash, and a naive combination can park the distinguishing information above the mask width. Masked designs therefore add a mixing step that pulls high-order entropy down before the AND. The work does not vanish; it moves from the index step into a hash-preparation step, where it is a couple of instructions rather than a division. ## Doubling is a growth policy, not just a size The second, less-discussed benefit of powers of two is what happens on resize. Suppose capacity goes from 16 to 32. The mask widens from `0b01111` to `0b11111`, exposing exactly one new bit. Every key therefore lands either at its old index (new bit 0) or at its old index plus 16 (new bit 1). A bucket splits into precisely two buckets, and the decision needs one bit of a hash you already cached — no key is hashed again, no key comparison is performed, and the split can even be done incrementally, one bucket at a time, if you want to avoid a single long pause. Prime sizing has no such structure. Growing from one prime to roughly twice another prime remaps keys arbitrarily, so every entry's index is recomputed with another remainder. Implementations usually carry a table of precomputed primes to grow through, which also means the capacity sequence is coarse and outside your control. ## The myth worth killing "Table sizes must be prime" is the misconception this question exists to catch. Primality is not a correctness requirement — any capacity works, because collisions are resolved, not prevented. Primality is a **defence against structure in the hash**. Older designs used the raw hash as the index input, so the modulus was the only mixing in the system, and a prime modulus was the cheapest available insurance. Modern masked designs make a different bet: assume nothing about the caller's hash, spend two instructions mixing it, then index with a mask. Mainstream runtimes have genuinely split on this: Java's and Python's hash tables size in powers of two and index by masking, while widely used C++ standard-library unordered containers keep a prime bucket count and take a remainder. Both ship at scale, which is the clearest possible evidence that neither is a correctness issue. ## A third option There is a middle road worth knowing: multiply-shift indexing (often called Fibonacci hashing). Multiply the hash by a large odd constant and take the *top* `log2(capacity)` bits of the product. Multiplication propagates carries upward, so every input bit influences the high bits of the product — you get remainder-like blending at multiplication cost, which is far below division. It keeps power-of-two capacities and the clean doubling split, and it removes the need for a separate fold. Its cost is one multiply on the critical path and a constant that must be chosen sensibly. ## How to answer at interview Name both mechanisms, then state the tradeoff in one line: powers of two buy a one-instruction index and a clean split on growth, at the price of depending on hash quality in the low bits; primes buy tolerance of a bad hash at the price of a division on every operation and an unstructured resize. Then say where you would spend: if you control key types and can insist on decent hashes, mask; if you accept arbitrary key types from arbitrary callers and cannot police their hash quality, the forgiving option earns its division.