Hashing and Hash Tables Questions

Direct answer

The real root cause is almost never the map's raw memory footprint, it is allocation churn: Integer is immutable, so map.put(key, map.get(key) + 1) allocates a brand-new Integer object on every single increment. At 100,000 queries per second (QPS) that is 100,000 short-lived objects entering the young generation every second, which is exactly what drives frequent young-generation garbage collection (GC, the JVM's automatic process for reclaiming heap memory that is no longer referenced) pauses. Boxing (wrapping a raw primitive like long in a heap object like Long) also multiplies per-entry memory versus a primitive table, and if the map is made thread-safe via a single lock or synchronizedMap, every request serializes on that one lock regardless of which user it touches. The fix is threefold: stop boxing on the hot increment path, shard the keyspace to spread lock contention, and only go off-heap if key cardinality itself threatens the heap budget.

Structured elaboration

1. Eliminate boxing on the hot path with a primitive collection. Libraries such as Eclipse Collections (LongIntHashMap) or fastutil (Long2IntOpenHashMap) store raw long keys and int values in flat arrays with open addressing, never allocating a Long, Integer, or HashMap.Node wrapper per entry. This removes both the per-increment allocation (the actual GC driver) and the static per-entry overhead.

2. Reduce contention with sharding. Partition the user-id keyspace across N independent shards (shard = hash(userId) % N), each holding its own primitive map and its own lock (or a lock-free structure). Unrelated users updating different shards no longer fight over the same lock, the same effect ConcurrentHashMap gets internally from segment/bin-level locking, but tuned explicitly to the counter workload. Pick N as a small multiple of core count; too few shards under-spreads contention, too many wastes memory on mostly-empty tables.

3. Use LongAdder for the counter itself, not a boxed value. java.util.concurrent.atomic.LongAdder is a JDK class built for exactly this write-heavy pattern: instead of every thread compare-and-swapping one shared counter, it stripes the count across several internal cells (each padded to its own cache line) so concurrent writers usually hit different cells, then sums them on read. It is the right tool when writes vastly outnumber reads, which per-request counters are; it is the wrong tool if the counter is read as often as it is written, because sum() has to walk every cell.

4. Reserve off-heap stores for cardinality, not contention. If the number of distinct users is large enough that even a primitive in-heap table would inflate the heap past its budget (tens to hundreds of millions of distinct keys), move the table off the JVM heap entirely (a memory-mapped structure, or a library such as Chronicle Map) so GC never has to scan it. This trades away JIT-friendly access speed and adds serialization/lifecycle complexity, so it should be the last lever pulled, after boxing and contention are already fixed, not the first.

Worked example

Assume 1,000,000 distinct active users being counted. On a 64-bit JVM with compressed object pointers (the default for heaps under 32 GB), typical object sizes are: a boxed Long is about 24 bytes (12-byte header plus an 8-byte value, padded to 8-byte alignment), a boxed Integer is about 16 bytes, and each HashMap.Node wrapping them is about 32 bytes (header plus hash, key reference, value reference, next reference). That is roughly 24 + 16 + 32 = 72 bytes per live entry, before the bucket array itself, and critically, a fresh 16-byte Integer is discarded and reallocated on every increment.

A flat primitive long-to-int open-addressed table stores 8 + 4 = 12 bytes of live key+value data per slot. At a load factor of 0.5 (kept low so probe chains stay short), that costs about 12 / 0.5 = 24 bytes per live entry, and updates happen in place with zero allocation. For 1,000,000 entries: about 72 MB versus about 24 MB, a 3x static memory reduction, and the incrementing hot path goes from 100,000 allocations/sec to zero.

Trade-offs and pitfalls

Common wrong turn: reaching for ConcurrentHashMap<Long, AtomicInteger> and calling it done. It removes the single-lock bottleneck and stops per-increment allocation (the AtomicInteger is created once, not once per increment), but the Long key is still boxed, and it does nothing about hot-key contention on one AtomicInteger if a single user dominates traffic; that case still needs LongAdder or explicit striping regardless of how the map itself is built. Also watch key skew: sharding by user id only helps if load is roughly uniform across users. A single very hot user still serializes on its own counter no matter how many shards exist.

Direct answer

hashCode() and equals() must be defined together and stay consistent: two objects that compare
equal MUST produce the same hash code, or a HashMap can insert a key, then fail to find it again
because it looks in the wrong bucket for the "equal" object. For a composite key, that means basing
both methods on the exact same set of fields, handling any nullable field the same way in both, and
caching the hash so repeated lookups aren't recomputing it from scratch.

Structured elaboration

The one-directional contract. The rule is not symmetric: equal objects must share a hash code,
but two objects sharing a hash code do NOT have to be equal (that's an ordinary collision, which the
table's collision-resolution strategy already handles via a follow-up equals() check within the
bucket). Violate the required direction (equal objects, different hashes) and the table breaks
structurally: insertion computes one bucket from the object's hash at that moment, but a later lookup
with an "equal" object computes a different hash, and therefore checks an entirely different
bucket, never finding the entry that is sitting right there in the other one.

Composite keys make this concrete. A key built from multiple fields (say userId, eventType,
date) needs both equals() and hashCode() to consider exactly the same fields, in the same way.
If equals() compares all three fields but hashCode() only hashes userId, two objects that differ
only in date would (correctly) compare unequal but (incorrectly, though harmlessly) share a hash
code, that's just a collision, not a contract violation, since equals() still separates them within
the bucket. The dangerous direction is the reverse: if hashCode() used all three fields but
equals() only compared userId, two objects with different dates but the same userId would compare
EQUAL yet (correctly, given they differ) hash DIFFERENTLY, silently breaking lookups for one of them.

Handling nulls. Any of the three fields (say eventType) may legitimately be null. Hand-rolled
field.hashCode() and field.equals(other.field) calls throw NullPointerException the moment that
field is null. Java's java.util.Objects utility class exists precisely for this: Objects.hash(a, b, c) treats a null argument as contributing 0 to the combined hash instead of throwing, and
Objects.equals(a, b) returns true when both are null, false when exactly one is null, and
delegates to a.equals(b) only when both are non-null. Using these consistently in both methods means
a null eventType behaves the same way in hashCode() as it does in equals(), which is the actual
requirement, not just "doesn't crash."

Performance. Recomputing a hash from three fields on every bucket lookup is wasted work if the
key object is immutable, since the hash can never change after construction. The standard technique
(the one java.lang.String itself uses) is to compute the hash once, in the constructor or lazily on
first use, and store it in a final int field that hashCode() just returns. This turns hashCode()
into an O(1) field read instead of an O(k) recomputation over k fields on every get/put/containsKey
call, which matters once the key class is hashed millions of times a second.

Why immutability matters here too. Even with a perfectly consistent contract, if any field that
feeds hashCode() mutates after the object has already been inserted as a key, the object's hash
changes but its position in the table (chosen using the OLD hash) does not move. A lookup using the
current (post-mutation) state now computes a different bucket than the one the entry actually lives
in. This is exactly the same "moved key" failure that using an inherently mutable type as a key
causes, just triggered here by careless field mutation instead. Marking every field final and
providing no setters makes this class of bug structurally impossible rather than merely unlikely, and
it's also what makes hash-caching in the constructor safe (a mutable field would invalidate the cache).

Worked example (Java)

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

final class CompositeKey {
    private final String userId;     // may be null
    private final String eventType;  // may be null
    private final String date;
    private final int cachedHash;    // computed once at construction

    CompositeKey(String userId, String eventType, String date) {
        this.userId = userId;
        this.eventType = eventType;
        this.date = date;
        this.cachedHash = Objects.hash(userId, eventType, date); // null-safe
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof CompositeKey)) return false;
        CompositeKey other = (CompositeKey) o;
        return Objects.equals(userId, other.userId)
                && Objects.equals(eventType, other.eventType)
                && Objects.equals(date, other.date);
    }

    @Override
    public int hashCode() {
        return cachedHash;   // O(1), not recomputed per lookup
    }
}

public class CompositeKeyDemo {
    public static void main(String[] args) {
        Map<CompositeKey, String> counts = new HashMap<>();

        CompositeKey k1 = new CompositeKey("u1", "click", "2026-01-01");
        CompositeKey k2 = new CompositeKey("u1", "click", "2026-01-01"); // distinct object, equal value
        counts.put(k1, "first-insert");
        System.out.println(k1.equals(k2));                  // true
        System.out.println(k1.hashCode() == k2.hashCode());  // true
        System.out.println(counts.get(k2));                  // "first-insert"

        // Null field: must not throw, and two null-eventType keys must still be equal
        CompositeKey n1 = new CompositeKey("u2", null, "2026-01-02");
        CompositeKey n2 = new CompositeKey("u2", null, "2026-01-02");
        counts.put(n1, "null-event-insert");
        System.out.println(n1.equals(n2));    // true
        System.out.println(counts.get(n2));   // "null-event-insert"
    }
}

Running this prints true, true, first-insert, true, null-event-insert. The first three lines
confirm the standard contract (equal objects, same hash, lookup by an equal-but-distinct object
succeeds); the last two confirm the null-field case behaves identically instead of throwing or
silently miscomparing.

Trade-offs and pitfalls

The most common real bug is hand-editing equals() (often to add or drop one field during a
refactor) and forgetting to update hashCode() to match, since Java does not enforce this
correspondence at compile time, IDEs' "generate equals and hashCode" helpers exist mainly to keep the
two in sync. Marking all key fields final (and re-deriving cachedHash only in the constructor)
makes the mutation-after-insertion bug structurally impossible rather than just unlikely, and using
Objects.hash/Objects.equals throughout removes null-handling as a place to introduce an
inconsistency between the two methods.

Direct answer

Two largely independent levers improve a hash-map-heavy service: cache locality (how memory is
laid out so the processor's cache can prefetch effectively) and concurrency (how many threads
can operate on the map simultaneously without blocking each other). Open addressing (storing
entries directly in one contiguous array) improves locality over separate chaining (where each
bucket is a separately-allocated linked structure); sharding the map into independently-locked
partitions improves concurrency by letting operations on different keys never contend for the
same lock.

Structured elaboration

Cache locality: open addressing vs chaining. Separate chaining stores each bucket as its own
linked list (or growable list) object; walking a bucket during a lookup means following a
pointer to a DIFFERENT heap allocation for each node, which the processor cannot reliably
prefetch, since the next node's address is not predictable until the current one is read. Open
addressing keeps every entry inline in ONE contiguous array; probing during a lookup walks
adjacent array slots, which the processor's hardware prefetcher handles well, since the next
slot's address is simply "next," known in advance. The concrete cost of chaining is not just the
lookup pattern: it also means many small separate heap objects (one per non-empty bucket)
instead of one larger contiguous block, adding real memory overhead beyond the raw data.

Concurrency: sharded hash tables. Instead of one hash map guarded by one lock, partition
keys across N independent shards (each its own map plus its own lock), routing each key to a
shard via hash(key) % N. Two operations on keys that land in DIFFERENT shards structurally
cannot contend, since they acquire two entirely different lock objects; this reduces contention
in proportion to shard count, at the cost of needing N separate locks and maps instead of one,
and losing the ability to do a single atomic operation across the whole table (a size() or
iteration must now touch every shard).

Prefetching. Even within a contiguous open-addressing array, explicit software prefetch
hints (issuing a request to load the next few likely probe slots into cache before they are
needed) can further help, particularly for probe sequences that are not perfectly sequential
(quadratic probing, double hashing); the benefit is workload- and hardware-dependent, so this is
usually the last lever pulled, after locality and concurrency structure are already improved.

Trade-offs in code complexity, memory, and throughput. Open addressing avoids per-node
allocation overhead (helping memory and locality) but complicates deletion (tombstones are
usually needed, since simply clearing a slot can break probe sequences for other keys that
probed past it) and degrades sharply as load factor approaches 1 (probe sequences grow long).
Chaining tolerates a higher load factor more gracefully (buckets just get slightly longer lists)
at the cost of the locality and per-node memory overhead already described. Sharding adds real
code complexity (every operation must first resolve which shard, and whole-table operations must
iterate all shards) in exchange for concurrency.

How to benchmark changes. Do not report wall-clock timings as the improvement metric, since
they are hardware- and load-dependent and not reproducible across environments; instead measure
structural, reproducible properties: memory footprint per entry (bytes per key/value pair,
measured directly), number of separate heap allocations (a direct proxy for locality, since fewer
larger allocations mean fewer pointer chases), and lock-contention structure (how many distinct
lock objects exist, and whether two specific keys share one). Where a throughput number is
needed for a real decision, run the SAME benchmark harness on the SAME hardware under controlled
load and report relative improvement with the harness and conditions fully specified, rather than
an isolated absolute number.

Worked example

# Run with PYTHONHASHSEED=0 to reproduce the exact byte counts below: Python randomizes
# string hash() per process by default, so unpinned runs will show slightly different numbers.
import sys, threading

def build_open_addressing_table(num_slots, keys):
    table = [None] * num_slots
    for k in keys:
        idx = hash(k) % num_slots
        while table[idx] is not None:
            idx = (idx + 1) % num_slots
        table[idx] = k
    return table

def build_chained_table(num_buckets, keys):
    buckets = [[] for _ in range(num_buckets)]
    for k in keys:
        buckets[hash(k) % num_buckets].append(k)
    return buckets

keys = [f"key-{i}" for i in range(1000)]
open_table = build_open_addressing_table(2000, keys)
chained_table = build_chained_table(2000, keys)

open_bytes = sys.getsizeof(open_table)
outer_bytes = sys.getsizeof(chained_table)
all_bucket_bytes = sum(sys.getsizeof(b) for b in chained_table)
num_nonempty = sum(1 for b in chained_table if b)
print("open addressing, single array:", open_bytes, "bytes")
print("chained, outer array:", outer_bytes, "bytes")
print("chained, all 2,000 bucket objects combined:", all_bucket_bytes,
      f"bytes ({num_nonempty} non-empty, {2000 - num_nonempty} empty)")
print("chained, total:", outer_bytes + all_bucket_bytes, "bytes")

# Concurrency: shard across independent locks, confirm different shards use different lock objects
num_shards = 16
locks = [threading.Lock() for _ in range(num_shards)]
sample_keys = ["alice", "bob", "carol", "dave", "erin"]
shards = [hash(k) % num_shards for k in sample_keys]
for k, s in zip(sample_keys, shards):
    print(k, "-> shard", s)
for i in range(len(sample_keys)):
    for j in range(i + 1, len(sample_keys)):
        if shards[i] != shards[j]:
            print(f"{sample_keys[i]} vs {sample_keys[j]}: different shards, "
                  f"different lock objects: {locks[shards[i]] is not locks[shards[j]]}")

Building both structures for 1,000 keys at a 0.5 load factor (with PYTHONHASHSEED=0 pinned for
reproducibility): the open-addressing array is a SINGLE object, sys.getsizeof reporting 16,056
bytes. The chained version's outer array alone is 16,184 bytes; summing sys.getsizeof over all
2,000 bucket-list objects (775 non-empty, 1,225 empty) adds 136,800 bytes, for a combined 152,984
bytes spread across 2,001 separate heap allocations (the outer array plus every bucket list,
empty or not). That is the measured, structural basis for the locality argument: a probe sequence
in the open-addressing table walks one array, while a bucket traversal in the chained table
follows a pointer to a different heap object each time. For concurrency, sharding across 16
independent threading.Lock objects and routing the same 5 sample keys by hash lands them on
shards 1, 10, 2, 11, and 8 respectively under this pinned seed, and confirms, by object identity
(is not), that any two keys landing in different shards are guarded by two DIFFERENT lock
objects, meaning writers to those keys are structurally unable to block each other regardless of
thread scheduling.

Trade-offs and pitfalls

• Do not report wall-clock benchmark numbers as if they were portable facts. They depend on
  the specific machine, load, and even the run; report the reproducible structural properties
  above, or a relative comparison from a fully specified, shared benchmark harness.
• Sharding trades whole-table operations for concurrency. An operation that needs a
  consistent view across the whole map (exact size(), a full iteration) now has to coordinate
  across all shards, which is easy to get subtly wrong (for example, reading each shard's size
  without synchronization while writes are in flight gives an approximate, not exact, count).
• Open addressing's deletion complexity is a common trip-up: naively clearing a slot on
  delete can silently break lookups for a DIFFERENT key whose probe sequence passed through that
  slot; tombstones (a special "deleted" marker distinct from "empty") are the standard fix, at
  the cost of needing periodic table rebuilds to reclaim tombstoned slots.
• Prefetching is the smallest, most hardware-dependent lever; validate it actually helps on
  your target hardware before adding the complexity, rather than assuming it always pays off.

Approach

Open addressing stores every entry directly inside one flat array (no linked chains); on a collision, double hashing computes a second, independent probe step so different keys that collide at the same starting slot still spread out across the table instead of clustering along a fixed stride. Concretely, slot i for probe attempt p is (h1(key) + p * h2(key)) mod capacity, where h2 is forced to never be zero and, with a prime table capacity, is guaranteed to eventually visit every slot. Deletion cannot simply null out a slot, because later entries may have probed past that slot to resolve their own collision; nulling it would break their probe chain and make get stop early and report them missing. The fix is a tombstone: a special "deleted, but keep probing past me" marker distinct from both "live entry" and "truly empty."

Code (Java)

public class DoubleHashTable {
    private static final Object TOMBSTONE = new Object();
    private Object[] keys;
    private Object[] values;
    private int capacity;
    private int size;   // live entries
    private int used;   // live entries + tombstones, drives resize

    public DoubleHashTable(int capacity) {
        this.capacity = capacity;
        this.keys = new Object[capacity];
        this.values = new Object[capacity];
    }

    private int h1(Object key) {
        return (key.hashCode() & 0x7fffffff) % capacity;
    }

    private int h2(Object key) {
        int h = key.hashCode();
        return 1 + ((h & 0x7fffffff) % (capacity - 1));  // never 0
    }

    public void put(String key, Integer value) {
        if ((double) (used + 1) / capacity > 0.6) resize();
        int idx = h1(key), step = h2(key), firstTombstone = -1;
        for (int probe = 0; probe < capacity; probe++) {
            int slot = (idx + probe * step) % capacity;
            if (keys[slot] == null) {
                int target = (firstTombstone != -1) ? firstTombstone : slot;
                if (keys[target] == null) used++;
                keys[target] = key; values[target] = value; size++;
                return;
            } else if (keys[slot] == TOMBSTONE) {
                if (firstTombstone == -1) firstTombstone = slot;
            } else if (keys[slot].equals(key)) {
                values[slot] = value;
                return;
            }
        }
        throw new IllegalStateException("table full, resize invariant violated");
    }

    public Integer get(String key) {
        int idx = h1(key), step = h2(key);
        for (int probe = 0; probe < capacity; probe++) {
            int slot = (idx + probe * step) % capacity;
            if (keys[slot] == null) return null;
            if (keys[slot] != TOMBSTONE && keys[slot].equals(key)) return (Integer) values[slot];
        }
        return null;
    }

    public boolean delete(String key) {
        int idx = h1(key), step = h2(key);
        for (int probe = 0; probe < capacity; probe++) {
            int slot = (idx + probe * step) % capacity;
            if (keys[slot] == null) return false;
            if (keys[slot] != TOMBSTONE && keys[slot].equals(key)) {
                keys[slot] = TOMBSTONE; values[slot] = null; size--;
                return true;
            }
        }
        return false;
    }

    private void resize() {
        Object[] oldKeys = keys, oldValues = values;
        capacity = nextPrime(capacity * 2);
        keys = new Object[capacity]; values = new Object[capacity];
        size = 0; used = 0;
        for (int i = 0; i < oldKeys.length; i++) {
            if (oldKeys[i] != null && oldKeys[i] != TOMBSTONE) {
                put((String) oldKeys[i], (Integer) oldValues[i]);
            }
        }
    }

    private static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; (long) i * i <= n; i++) if (n % i == 0) return false;
        return true;
    }

    private static int nextPrime(int n) {
        int candidate = Math.max(n, 2);
        while (!isPrime(candidate)) candidate++;
        return candidate;
    }

    public int size() { return size; }
    public int capacity() { return capacity; }

    public static void main(String[] args) {
        DoubleHashTable t = new DoubleHashTable(7);
        t.put("a", 1); t.put("b", 2); t.put("c", 3);
        System.out.println("get a -> " + t.get("a"));
        System.out.println("get missing -> " + t.get("zzz"));
        t.delete("b");
        System.out.println("get b after delete -> " + t.get("b"));
        t.put("d", 4);
        System.out.println("get d after reusing tombstone slot -> " + t.get("d"));
        System.out.println("get a still resolves past tombstone -> " + t.get("a"));
        for (int i = 0; i < 30; i++) t.put("k" + i, i * 10);
        System.out.println("size after bulk insert -> " + t.size() + " capacity -> " + t.capacity());
        boolean allCorrect = true;
        for (int i = 0; i < 30; i++) if (!Integer.valueOf(i * 10).equals(t.get("k" + i))) allCorrect = false;
        System.out.println("all 30 post-resize keys correct -> " + allCorrect);
        System.out.println("c survived resize -> " + (t.get("c") == 3));
        System.out.println("b stays deleted after resize -> " + (t.get("b") == null));
    }
}

Output (compiled with javac and executed as shown; starting capacity 7):

get a -> 1
get missing -> null
get b after delete -> null
get d after reusing tombstone slot -> 4
get a still resolves past tombstone -> 1
size after bulk insert -> 33 capacity -> 79
all 30 post-resize keys correct -> true
c survived resize -> true
b stays deleted after resize -> true

Key points

• Tombstones on delete: a deleted slot is marked with a distinct TOMBSTONE sentinel (not null), so get keeps probing past it instead of stopping early, while put is free to reclaim that slot for a brand-new key. The demo confirms both halves: get("b") correctly returns null after delete, and get("a") still resolves even though its probe sequence now passes through b's tombstone.
• Rehashing strategy during resize: the table grows to the next prime at least double the old capacity (kept prime so h2's stride never shares a factor with the table size), and every live entry is walked and re-inserted through the normal put path; tombstones are dropped rather than copied, since a resize is exactly the natural point to reclaim their space. This is why used (live plus tombstones) rather than size (live only) drives the resize trigger: a table can fill up with tombstones alone and still needs to compact even though size looks small.
• Amortized O(1) argument: each resize costs (O(n)) (every live entry is rehashed once), but a resize only fires after roughly doubling the entries admitted since the last one, so the total rehashing work after (n) inserts is bounded by (n + n/2 + n/4 + \cdots < 2n), a constant multiple of (n). Spread over (n) inserts, that is (O(1)) amortized per insert, on top of the already-(O(1))-average probe cost.
• Production concurrency: this implementation is single-threaded only. Making open addressing thread-safe is harder than chaining, because a resize physically relocates every entry, so a reader mid-probe during a concurrent resize can land on a slot that no longer means what it did. Practical options are a single coarse lock around every operation (simple, but serializes all access), sharding into N independently-locked sub-tables (much better throughput, standard production pattern), or a lock-free design with versioned/CAS slots and a copy-on-resize scheme, which is substantially more complex to get correct and is usually reached for only when a proven mature implementation (like java.util.concurrent.ConcurrentHashMap, which uses chaining internally rather than open addressing for exactly this reason) is not applicable to the constraints.

Complexity

• Average case, insert/get/delete: (O(1)), assuming a good hash and load factor kept under the resize threshold (here 0.6) so probe sequences stay short.
• Worst case: (O(n)), a pathological hash or a table nearly saturated with tombstones can force a scan of most of the table.
• Resize: (O(n)) when triggered, (O(1)) amortized per insert overall, per the argument above.

Edge cases

• Deleting then reinserting a different key: must be able to reuse the tombstoned slot (put("d", 4) above lands where b was deleted).
• A key whose probe sequence crosses a tombstone left by an unrelated deleted key: must still resolve correctly (get("a") after b's deletion).
• A table that has accumulated many tombstones without much live growth: resizing on used rather than size prevents probe sequences from silently degrading toward (O(n)) even while the map looks small.
• Deleting a key that was never present: the loop reaches an empty (null) slot and returns false without touching the table.

Direct answer

A power-of-two capacity lets the table find a key's slot with a single bitwise AND (hash & (capacity - 1)), while a prime capacity needs a true modulo operation. The AND is faster, but it only ever looks at the hash's LOW bits, so a hash function with weak low-bit randomness clusters badly against a power-of-two table in a way it would not against a prime-sized one, which is exactly why real implementations that use power-of-two tables also add a step that mixes the hash's higher bits down into the low bits before masking.

Structured elaboration

Speed of indexing

• hash & (capacity - 1) is a single, branchless bitwise AND when capacity is a power of two, which is why array-backed hash tables overwhelmingly default to power-of-two sizes.
• hash % capacity for an arbitrary (prime) capacity is a true division/modulo operation, historically notably slower than a bitmask; though the practical gap has narrowed on modern hardware, it remains the reason power-of-two sizing is the default choice when raw indexing speed matters.

Distribution quality for bad hash functions

• The bitmask approach uses ONLY the low $\log_2(\text{capacity})$ bits of the hash value, so if a hash function's low bits are not well distributed (a common failure mode: multiplying by a constant, or hashing structured data like consecutive integers or aligned memory addresses), a power-of-two table clusters keys into far too few buckets, regardless of how well-distributed the hash's HIGH bits might be.
• A prime-sized table with true modulo uses the hash value's full range in a way that is much more forgiving of a hash function with poor low-bit quality but reasonable overall distribution; prime moduli tend not to share small common factors with structured input patterns the way a power-of-two mask does.

Modern mitigations for poor low-bit quality

• Many production hash tables keep the power-of-two capacity, for the indexing speed, and instead fix the hash function: apply a supplemental spreading step that XORs or mixes the higher bits down into the low bits before masking, so even a hash with weak low bits gets some entropy from its higher bits reflected into the bits that actually get used. Java's HashMap, for example, applies hash ^ (hash >>> 16) to every key's hash code before masking, for exactly this reason.
• CPython's dict and set implementation takes a related but different approach: rather than only fixing the hash, its open-addressing probe sequence itself incorporates the hash value's higher bits across successive probes, so even if the initial masked slot collides due to poor low-bit quality, subsequent probes are informed by bits the first probe ignored, recovering good behavior over the course of a probe chain rather than a single lookup.

Worked example

Consider hashing the values $0, 256, 512, 768, \dots$ (a plausible pattern: a field always populated as a multiple of 256, such as a scaled fixed-point value). With a power-of-two capacity of 16 (mask 15): $256 \bmod 16 = 0$, so EVERY one of these keys maps to bucket 0, no matter how many there are, total clustering. With a prime capacity of 17: $256 \bmod 17 = 1$, so consecutive multiples of 256 land at buckets $0, 1, 2, 3, \dots$ (since $256k \bmod 17 = k \bmod 17$), spreading cleanly across the table instead of collapsing onto one bucket.

Trade-offs and pitfalls

• Choosing prime capacities "to be safe" without knowing whether your hash function actually has weak low bits trades away real, measurable indexing speed for a problem that a good hash function's supplemental mixing step already solves.
• Conversely, assuming a power-of-two table is always safe because "the language's hash function is probably fine" is risky for custom or user-supplied hash functions (a hand-written hashCode on a composite key) that were never validated for low-bit quality.
• The right question is not "power-of-two or prime" in isolation, it is whether the hash function feeding the table has been checked for exactly the failure mode, poor low-bit distribution, that only power-of-two masking is vulnerable to.