Why Does libc++ Use Prime Numbers for Hash Table Rehashing?

I’m continuing to explore the internals of libc++ (LLVM’s C++ standard library), and I ran into a small but very intentional line inside the hash table implementation:

__n = std::__next_prime(__n);

At first glance, this looks like a harmless detail — just rounding the bucket count to the next prime. But it raises a deeper question:

Why does a standard library deliberately choose prime numbers for hash table sizes? After all, wouldn’t powers of two be faster?

The Core Idea

Using a prime number of buckets is a classic strategy to reduce hash collisions — especially when the hash function isn’t perfect. This is not about average performance. It’s about robustness under real-world conditions.

How Hash Tables Map Values

Most hash tables compute a bucket index like this:

index = hash % N

Where:

• hash → large integer from the hash function
• N → number of buckets

This is where the choice of N becomes critical.

Power-of-Two Buckets: Fast but Fragile

If N is a power of two (e.g., 16, 32, 64), the modulo operation becomes:

index = hash & (N - 1);

This is extremely fast — just a bitwise AND. But there’s a catch:

It only uses the lowest bits of the hash.

Why this is dangerous

If your hash values share similar lower bits, you get massive collisions. Example: Hashing pointers. On most 64-bit systems, pointers are aligned to 8 or 16 bytes. This means the lower 3 or 4 bits of a pointer are always zero.

If N = 16, every single pointer will map to index 0. You no longer have a hash table; you have a linked list. This is known as catastrophic clustering.

Prime Numbers: Slower but Safer

Now consider:

index = hash % 31

Since 31 is prime:

• The modulo operation involves all bits
• Patterns in the input are less likely to survive
• Distribution becomes more uniform

Even with a mediocre hash function, the table behaves reasonably well.

The Real Problem: Imperfect Hash Functions

In theory, a good hash function distributes values evenly. In practice:

• Users write custom hashers
• Data has patterns (sequences, alignment, repetition)
• Not all hashes are well-mixed

So the standard library has to assume:

The hash function might be flawed

Using primes acts as a defensive layer against that.

A Concrete Failure Case

Imagine hashing pointers:

void* ptr; // aligned to 16 bytes

Binary representation:

...xxxx0000

If N = 16:

index = hash & 15 → always 0

All elements collide. Now with a prime:

index = hash % 17

The higher bits now matter hence distribution improves dramatically.

Strategy trade-offs

So Power of two strategy is very fast (& instead of %) but sensitive to bad hash patterns. And Prime numbers strategy has robust distribution but slower modulo operation. So why does libc++ choose primes?

Why libc++ Picks Primes

The design philosophy is clear:

Prioritize correctness and worst-case behavior over raw speed

libc++ assumes:

• Users may provide weak hash functions
• Data may contain patterns
• The container must still behave predictably

So instead of optimizing for the best case, it protects the worst case.

“But Isn’t Modulo Slow?”

Yes, the % operator is significantly slower than bitwise &. However, libc++ mitigates this in two ways:

1. Precomputed Tables: It doesn’t calculate primality on the fly. It uses a built-in list of primes that roughly double in size (e.g., 5, 11, 23, 47, 97…).
2. Amortization: Since rehashing only happens when the table grows, the cost is spread out over thousands of insertions.

Why Some Implementations Don’t Use Primes

Not all standard libraries make the same choice. The MSVC (Microsoft) STL typically uses power-of-two bucket counts. Their philosophy is different:

• Assume the hash function is already high-quality (or use a “supplemental” hash to mix the bits).
• Prioritize the raw speed of bitwise operations.
• This shifts the responsibility to the user: If your hash is bad, your performance will suffer.

Final Takeaway

That small line:

__n = std::__next_prime(__n);

is a reminder that in systems programming, the "fastest" solution isn't always the most "reliable" one.libc++ chooses reliability. It assumes your hash function might be bad and makes the container work anyway. It’s a defensive, "safety-first" approach that ensures std::unordered_map remains a dependable tool, even in the hands of a developer who doesn't know about pointer alignment or bit-mixing.

Thanks for reading!

If you enjoy exploring C++ internals or C++ in general feel free to connect with me:

LinkedIn: https://linkedin.com/in/rabulyaev GitHub: https://github.com/abulyaev