{"id":134,"date":"2026-11-12T16:40:00","date_gmt":"2026-11-12T16:40:00","guid":{"rendered":"https:\/\/tothepowerof2.com\/blog\/?p=134"},"modified":"2026-11-11T03:37:53","modified_gmt":"2026-11-11T03:37:53","slug":"hash-table-capacities-near-powers-of-two","status":"publish","type":"post","link":"https:\/\/tothepowerof2.com\/blog\/hash-table-capacities-near-powers-of-two\/","title":{"rendered":"Sizing Hash Table Capacities Near Powers of Two"},"content":{"rendered":"

TL;DR \/ Summary:<\/strong> Many hash tables size their buckets to a power of two so index mapping can use bitwise masks instead of slow modulo operations. Before you hard-code 1024 or 4096, confirm 2\u207f with tothepowerof2.com<\/a>, plan a load-factor resize, and know when prime capacities are the wiser tradition.<\/p>\n

Why buckets love 2\u207f<\/h2>\n

A hash function yields a wide integer; the table must fold that integer into an index. If capacity is 2\u207f, hash & (capacity - 1)<\/code> replaces hash % capacity<\/code>. On modern CPUs the mask is cheap and branch-friendly. Languages and libraries that promise amortized constant-time lookups often document power-of-two growth for that reason.<\/p>\n

Growth policies commonly double: 16 \u2192 32 \u2192 64 \u2192 \u2026 Doubling preserves the power-of-two invariant and spreads entries after a rehash. Understanding the exponent helps you predict memory spikes when a table crosses a load-factor threshold mid-request. That prediction matters on latency-sensitive paths more than on batch jobs that can pause.<\/p>\n

Load factor is the real dial<\/h2>\n

Capacity alone does not define performance. Load factor\u2014entries divided by buckets\u2014decides how often collisions chain or probe. A 2\u00b9\u00b2-bucket table at 0.9 load can feel worse than a 2\u00b9\u2070 table at 0.5. When estimating memory, multiply expected entries by your max load factor, then round up<\/em> to the next power of two so you do not resize during a latency-sensitive window.<\/p>\n

Worked sketch: 1,800 session tokens, max load 0.75 \u2192 need at least 2,400 buckets \u2192 next power of two is 2\u00b9\u00b2 = 4096. Compute that ceiling with a calculator instead of guessing \u201cabout four thousand.\u201d Write the assumption in a code comment so the next engineer knows why 4096 appeared rather than 3000.<\/p>\n

When primes still appear<\/h2>\n

Some older guidance prefers prime bucket counts to reduce patterned collisions when hash mixing is weak. If your hasher is low quality or identity-based on sequential keys, a prime modulus can help. High-quality mixers plus power-of-two masks are the common modern pairing\u2014especially in systems languages that control both hasher and table.<\/p>\n

Read your standard library notes. Blindly forcing 2\u207f in a structure that already rounds to primes wastes time and may fight its resize heuristics. Interop layers that wrap two different map types should not assume identical sizing philosophies.<\/p>\n

Cache lines, allocator pressure, and servers<\/h2>\n

Doubling a large table briefly needs old and new storage. On a memory-tight VPS or mobile runtime, that spike matters more than the elegance of bitwise indexing. Pre-size tables when you know the cardinality (dictionaries of feature flags, caches of SKUs) so traffic does not trigger a mid-day rehash.<\/p>\n

Also watch pointer-heavy entries: the bucket array may be 2\u207f, but each collision node allocates separately. Profiling allocations often reveals more pain than the mask versus modulo debate. Sometimes a denser open-addressing table with a slightly larger power-of-two array beats a chaining design that looks smaller on paper.<\/p>\n

Debugging checklist for \u201cmysterious\u201d slow maps<\/h2>\n