Hashing and Hash Tables Questions

Direct answer

For an approximate-membership structure over billions of 64-bit integers where false positives are tolerable but false negatives are not, a Bloom filter gives the smallest memory footprint but no delete support at all; a quotient filter costs a bit more memory per element in exchange for supporting deletion and better cache locality; and a compact hash table of stored fingerprints gives the most flexibility (deletes, resizing, per-entry metadata) at a real memory premium over the other two. For a recent-items cache specifically, the practical answer is often a pair of rotating Bloom filters rather than reaching for delete support at all.

Structured elaboration

How each one actually stores and checks an item. The comparison below is only meaningful if these
three mechanisms are concrete, so here they are in one pass:

• Bloom filter. A bit array of length m, all zeros to start, plus k independent hash functions.
  To INSERT x, compute the k hashes, and set those k bits to 1. To QUERY x, compute the same k
  hashes and check those k bits: if any is 0, x was definitely never inserted; if all are 1, x is
  probably present. Nothing about x is stored, only evidence that something set those bits — which is
  why it is small, why a false positive is possible (other items' bits can cover x's), and why you
  cannot delete (clearing a bit might erase a bit some other item is relying on).
• Quotient filter. Hash x once to a p-bit fingerprint, then SPLIT that fingerprint: the high q
  bits are the quotient (used as the slot index) and the low r bits are the remainder (stored
  in that slot). So unlike a Bloom filter it stores an actual value per item, and because colliding items
  land in neighbouring slots, a lookup reads a short contiguous run — good cache behaviour. Storing the
  remainder is also what makes deletion safe: you remove one specific remainder rather than clearing
  shared bits.
• Compact hash table of fingerprints. An ordinary open-addressed hash table whose stored value is not
  the key but a short fingerprint of it (say 16 bits). Insert, query and delete work exactly as in any
  hash table; a false positive happens only when two distinct keys share a fingerprint AND a slot. You
  pay for the table's empty slots and for full-width entries, which is the memory premium.

A false NEGATIVE is impossible in all three, because every structure only ever records evidence that an
item was added, never evidence that one was absent.

Worked example

For a target false positive rate of 1% over $n$ elements, the standard Bloom filter sizing formula gives bits per element:

with optimal hash-function count

For $10^9$ (one billion) elements at that same 1% target, this is about $9.6 \times 10^9$ bits $\approx 1.2$ GB total for the whole billion-element set, before any per-element metadata. A quotient filter at a comparable false positive rate typically runs a modest constant factor above this (extra bits per slot for the quotient/metadata portion), and a compact hash table storing, say, 4-byte fingerprints with typical open-addressing slack would run to several times the Bloom filter's footprint for the same false positive guarantee, since it pays for a full fingerprint per slot rather than a handful of shared bits.

Practical design: a recent-items cache

Since a recent-items cache needs RECENCY (old entries should stop counting as "seen") more than true deletion, avoid the delete-support machinery of quotient filters or hash tables altogether: maintain TWO Bloom filters, an "active" one and a "previous" one. Insert only into the active filter; check membership against BOTH. On a fixed rotation interval (matching how long "recent" should mean), the previous filter is discarded, the active filter becomes the new previous filter, and a fresh empty filter becomes the new active one. This gives a bounded, sliding window of "recently seen" with the smallest possible memory footprint and the simplest possible concurrency model (just atomic bit-sets), at the cost of a small amount of aggregate memory (two filters instead of one) and query cost (two lookups instead of one).

Trade-offs and pitfalls

• Reaching for a quotient filter or full hash table purely because "deletes might be needed eventually" pays a real, permanent memory cost for a feature the recent-items design above shows is often avoidable by reframing the problem around rotation instead of deletion.
• A Bloom filter sized for a false positive rate assuming $n$ elements silently degrades (a rising false positive rate) if the actual element count grows past that assumption; size for the target scale explicitly and monitor actual load, do not assume it holds forever.
• Concurrency is not free even for Bloom filters: at very high write throughput, contention on the underlying bit array (even via atomic operations) can become the bottleneck; sharding the filter (multiple smaller filters, one per shard, queried in parallel) is the standard mitigation.

Direct answer

Since a raw Python dict cannot be a set/dict key (dicts are unhashable, by design, because
they are mutable), convert each record to something hashable before deduping: a canonical
serialization (deterministic JSON with sorted keys), a sorted tuple of its items, or a stable
content fingerprint (a SHA-256 digest of the canonical form). The fingerprint approach is
usually best in an ETL (extract, transform, load) pipeline, since it gives a fixed-size, directly
comparable key regardless of record size, but all three require deliberate handling of key order, floating-point
representation, and missing fields, or dedup will silently under- or over-merge records.

Structured elaboration

Why the dict itself cannot be a key. Python requires a key to be hashable, and hashability
requires immutability, since a mutable object's hash could change after it is inserted, which
would break the exact bucket-integrity guarantee hash-based lookup depends on (the same failure
mode discussed for mutable hash keys generally). A plain dict is mutable, so Python disallows
it as a key outright, raising a TypeError rather than allowing a subtly broken key.

Canonical serialization (deterministic JSON). Serialize each record with sort_keys=True so
two dicts with the SAME content but different key insertion order produce the IDENTICAL JSON
string, then use that string (or its hash) as the dedup key. This alone handles key-order
independence but does nothing yet about floating-point noise or missing-versus-null fields; those
need explicit normalization before serialization.

Sorted tuples. Convert sorted(record.items()) into a tuple, which is hashable as long as
every value inside it is also hashable (a nested dict or list value is NOT, so this approach
needs a recursive conversion for nested structures, which canonical JSON serialization handles
more naturally since JSON is already a recursive format).

Stable fingerprints (SHA-256). Hash the canonical serialization with a cryptographic digest
to get a fixed-size, directly comparable identifier, useful when records are large (the
fingerprint is small and constant-size regardless of record size) or when you want to persist the
dedup key separately from the record itself.

The three edge cases the question calls out, and how to actually handle each.

• Ordering: solved by sort_keys=True in JSON serialization, or by sorting the tuple's items
  before hashing; without this, two logically identical records with differently-ordered keys
  fingerprint differently and dedup silently fails to merge them.
• Floating point: two records can represent the SAME business value with different floating-
  point bit patterns (upstream arithmetic noise, different serialization precision), which
  fingerprint DIFFERENTLY unless floats are rounded to a fixed, deliberately chosen precision
  before serialization; skipping this rounding step causes dedup to under-merge (treat identical
  records as distinct).
• Missing fields: a field entirely ABSENT from a dict and the same field explicitly set to
  null/None are different things to a naive JSON serializer (json.dumps omits an absent key
  entirely but writes null for an explicit None), so normalize by explicitly filling every
  expected field via record.get(field, default) before serializing, or two logically identical
  records (one with a field omitted, one with it explicitly null) will fingerprint differently and
  fail to dedup.

Performance and correctness. Fingerprinting is O(record size) per record, done once; the
subsequent dedup itself is then an ordinary O(1) average hash-set membership check per record,
same as any other hash-based dedup. Correctness depends entirely on how faithfully the
normalization step (rounding, explicit field-filling, key sorting) captures "these two records
should count as the same," which is a judgment call specific to the data, not something the
serialization mechanism decides for you.

Worked example

import hashlib, json

fields = ["user_id", "amount", "region", "notes"]
a = {"user_id": "u1", "amount": 19.99, "region": "US", "notes": None}
b = {"region": "US", "notes": None, "amount": 19.99, "user_id": "u1"}       # reordered keys
c = {"user_id": "u1", "amount": 19.99, "region": "US"}                       # 'notes' key ABSENT
d = {"user_id": "u1", "amount": 19.99000000000001, "region": "US", "notes": None}  # float noise

# Confirm the premise: a raw dict cannot be a set element at all.
try:
    literal_set = {a}
except TypeError as e:
    print("TypeError on raw dict in a set literal:", e)

def canonical_fingerprint(record, expected_fields, ndigits=6):
    normalized = {}
    for field in expected_fields:
        value = record.get(field, None)
        if isinstance(value, float):
            value = round(value, ndigits)
        normalized[field] = value
    canonical_json = json.dumps(normalized, sort_keys=True)
    return hashlib.sha256(canonical_json.encode()).hexdigest()

print(canonical_fingerprint(a, fields) == canonical_fingerprint(b, fields))
print(canonical_fingerprint(a, fields) == canonical_fingerprint(c, fields))
print(canonical_fingerprint(a, fields) == canonical_fingerprint(d, fields))

# Confirm rounding is doing real work: a naive fingerprint WITHOUT rounding
# should fail to match a and d, even though the rounded version matches.
def naive_fingerprint(record, expected_fields):
    normalized = {f: record.get(f, None) for f in expected_fields}
    return hashlib.sha256(json.dumps(normalized, sort_keys=True).encode()).hexdigest()

print(naive_fingerprint(a, fields) == naive_fingerprint(d, fields))

Running this: attempting {a} (a literal set containing a plain dict) raises
TypeError: cannot use 'dict' as a set element (unhashable type: 'dict'), confirming the
premise. Record a (natural key order) and record b (identical content, shuffled key order)
fingerprint IDENTICALLY (True). Record c, where the notes key is entirely absent rather than
explicitly None, ALSO fingerprints identically to a (True), because both normalize through
record.get("notes", None) to the same value. Record d, where amount carries floating-point
noise (19.99000000000001 instead of 19.99), fingerprints identically to a (True) once
rounded. The final line confirms rounding is actually load-bearing: the naive (unrounded)
fingerprint of a and d comes out False, a false negative that would leave two logically
identical records undeduped if the rounding step were skipped.

Trade-offs and pitfalls

• Rounding precision for floats is a business decision, not a technical default. Too coarse a
  rounding (few digits) can merge genuinely different values; too fine (many digits) can leave
  float noise unresolved. Pick the precision that matches the field's real-world meaningful
  granularity (for a currency amount, cents is usually the right granularity).
• Silently defaulting missing fields to None can mask real data-quality problems if a field
  is SOMETIMES missing due to an upstream bug rather than legitimately absent; log or flag records
  that rely on the default rather than silently normalizing them away.
• Nested structures (a dict value containing another dict or a list) need the SAME
  normalization recursively applied, or a nested float or nested key-order difference reproduces
  the exact same bugs one level down.
• A fingerprint collision is theoretically possible but not the practical risk here: SHA-256's
  collision probability is negligible at any realistic ETL scale; the actual, common failure mode
  is a NORMALIZATION bug (missed rounding, missed default-fill, unsorted nested keys), not a hash
  collision.

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

Build the vocabulary for natural language processing (NLP) model training in two phases: a mutable counting phase (stream every token array through a hash map that tallies frequency), then freeze it into an immutable, id-assigned lookup structure for training and inference. Reserve the first few ids for special tokens, PAD (padding), UNK (unknown / out-of-vocabulary), BOS (beginning-of-sequence), and EOS (end-of-sequence), so every consumer of the vocabulary can hardcode those ids instead of looking them up. At roughly 50 million entries, the STRUCTURE chosen to store the final mapping matters far more for memory and load time than the counting logic itself.

Counting tokens and assigning ids

Stream through the training corpus's token arrays, incrementing a count in a hash map keyed by token string. Once counting finishes, apply a frequency cutoff (drop tokens seen fewer than some minimum number of times) to bound vocabulary size, then assign ids in a fixed order, most commonly by descending frequency, so common tokens get low ids; this also tends to compress better downstream, since low ids repeat more often in a frequency-skewed corpus.

Reserving special tokens

Special tokens need a small, fixed set of ids that never collide with a real corpus token and never depend on which corpus happened to be used for training:

• PAD (padding): fills unused positions in a fixed-length batch so every sequence in a batch has equal length; typically id 0 so padded positions can be masked cheaply.
• UNK (unknown): the fallback id for any token encountered at inference that isn't in the vocabulary.
• BOS (beginning-of-sequence): marks where a sequence starts, useful for generation and for models needing an explicit start signal.
• EOS (end-of-sequence): marks where a sequence ends, so a generative model learns when to stop.

Reserve these before assigning any corpus-derived ids, so their meaning stays stable across vocabulary rebuilds even if the corpus changes.

Handling out-of-vocabulary tokens at inference

A token seen at inference that never appeared (or fell below the training cutoff) has no assigned id. The simplest handling maps it to UNK's id and accepts the information loss. A stronger approach used by most modern pipelines is subword tokenization (byte-pair encoding or WordPiece): tokens are built from smaller sub-units, so a genuinely novel word usually still decomposes into known pieces rather than becoming one opaque UNK, which is why subword vocabularies handle open-ended text far better than whole-word vocabularies.

Memory and storage at roughly 50 million entries: hash maps vs sorted arrays

A hash map keyed by token string needs, per entry: a stored hash, a pointer to the key string (heap-allocated, variable length), the id, and spare capacity (load-factor headroom, typically kept below 0.7) to keep lookups fast. A sorted array of (hash, id) pairs, searched with binary search instead of hashing, is far more compact, since it needs no pointer indirection and no load-factor slack:

$\text{bytes}_{\text{array}} = n \times (\text{hash\_bytes} + \text{id\_bytes})$

For n = 50,000,000 with an 8-byte hash and a 4-byte id, that is 50,000,000 x 12 bytes = 600,000,000 bytes, about 600 MB (572 MiB). A hash map's per-entry cost is roughly:

$\text{bytes}_{\text{hashmap}} \approx \frac{n \times \text{entry\_bytes}}{\text{load factor}}$

With a typical entry cost of 24 to 32 bytes (hash, id, and a pointer to the string) and a load factor of 0.5 to 0.7, that works out to roughly 1.7 to 3.2 GB for the same 50 million entries, several times the sorted array's footprint, purely from pointer indirection and load-factor slack. This is a formula-based engineering estimate, not a measured benchmark of any specific library implementation.

Persistence format for fast load

A sorted array of fixed-width records maps directly onto a flat binary file: loading it is a single memory-map call, and binary search needs no deserialization step at all. A hash map is usually serialized as a list of key-value pairs and has to be walked and reinserted into fresh buckets on load (rehashing), which is both slower and momentarily doubles memory during the rebuild. For a static, read-only, roughly 50-million-entry vocabulary that never changes after training, a memory-mapped sorted array (or a minimal perfect hash function built once offline) is usually the better production choice; a hash map is the right tool for the mutable COUNTING phase, not for the frozen artifact that gets shipped.

Trade-offs and pitfalls

• Shipping a hash map as the FINAL served artifact (rather than only using it during counting) is the most common mistake: it optimizes for a mutability no longer needed and pays for it in memory and cold-start latency.
• Binary search on a sorted array costs O(log n) per lookup ($\log_2(50{,}000{,}000) \approx 26$ comparisons) versus O(1) average for a hash map; for 50 million entries this is still fast in absolute terms, but it's a real trade-off if vocabulary lookup sits on a hot path.
• Forgetting to reserve special-token ids before assigning corpus ids means a vocabulary rebuild (a different corpus, a different frequency cutoff) can silently shift what PAD, UNK, BOS, or EOS mean, a subtle and hard-to-detect training bug.

Direct answer

For sharding, a well-tested non-cryptographic hash (such as MurmurHash) is almost always the
right choice over both naive modulo-of-raw-key and a cryptographic hash (such as SHA family):
it is fast, spreads structured or skewed keys uniformly (which naive modulo does not), and
sharding is not a security boundary, so cryptographic collision-resistance is wasted cost. The
one place cryptographic properties matter is when key choice is adversarial (an external actor
can choose keys that intentionally collide), which is fixed by keying/salting the hash with a
server-side secret, not by switching hash families outright.

Structured elaboration

Why naive key % num_shards fails on structured keys. Real-world keys are rarely uniform
random. Sequential ids, timestamps, or ids assigned by a fixed number of parallel writers often
share arithmetic structure (for example, every id being a multiple of the writer count). Taking
modulo of the RAW key preserves that structure directly into the shard assignment, producing
severe skew: an entire batch of structured keys can land on a single shard while others sit idle.

Why hash-then-modulo fixes it. Passing the key through a well-mixed hash function BEFORE
taking modulo destroys the key's original arithmetic structure: the hash output has no
relationship to whatever pattern the raw keys followed, so hash(key) % num_shards spreads
structured keys close to uniformly, even though the raw keys were not uniform at all.

Modulo-based vs cryptographic vs non-cryptographic, compared.

Adversarial inputs and when they matter. If the party choosing keys is untrusted (for
example, a hash function is used to route arbitrary user-controlled input, like HTTP request
parameters, into buckets), an attacker who knows the hash function and shard count can
deliberately choose keys that all collide onto one shard (a hash-flooding attack), overloading
it. The fix is NOT necessarily switching to a cryptographic hash; it is keying the hash with a
secret seed the attacker does not know: an HMAC (Hash-based Message Authentication Code, a
construction that mixes a secret key into the hashing process) style keyed hash, or a
non-cryptographic hash that accepts a seed parameter. Without knowing the seed, an attacker's precomputed
colliding-key set no longer collides, because the seed changes which bucket every key maps to.

Testing a candidate hash function before adopting it. Generate a large, representative
sample of real or realistic keys (including the structured/adversarial patterns you actually
see in production), hash them, and check the resulting bucket distribution for uniformity (for
example a chi-square goodness-of-fit test against the expected even split). Separately, test the
avalanche property (a single-bit input change should flip roughly half the output bits) to catch
functions with insufficient mixing before they reach production.

Worked example

from collections import Counter

def fnv1a(data: bytes, seed=0x811c9dc5):
    h = seed
    for byte in data:
        h ^= byte
        h = (h * 0x01000193) & 0xFFFFFFFF
    return h

num_shards = 16
structured_keys = [i * 16 for i in range(10_000)]  # every key a multiple of 16

# Naive modulo of the raw key
naive = {k % num_shards for k in structured_keys}
print("distinct shards used by naive modulo:", len(naive))

# Hash first, then modulo (FNV1a stands in for the MurmurHash family)
hashed_counts = Counter(fnv1a(str(k).encode()) % num_shards for k in structured_keys)
max_hashed = max(hashed_counts.values())
print("distinct shards used after hashing:", len(hashed_counts))
print(f"largest shard after hashing: {max_hashed} keys = {max_hashed/10_000*100:.1f}% "
      f"(perfectly even = {100/num_shards:.2f}%)")

# Adversarial case: brute-force 200 keys that all collide on shard 0 under a PUBLIC seed
PUBLIC_SEED = 0x811c9dc5
SECRET_SEED = 0xdeadbeef
colliding_keys, candidate = [], 0
while len(colliding_keys) < 200:
    k = f"user-{candidate}".encode()
    if fnv1a(k, seed=PUBLIC_SEED) % num_shards == 0:
        colliding_keys.append(k)
    candidate += 1
public_counts = Counter(fnv1a(k, seed=PUBLIC_SEED) % num_shards for k in colliding_keys)
print("under the PUBLIC seed, all 200 crafted keys land on:", dict(public_counts))

secret_counts = Counter(fnv1a(k, seed=SECRET_SEED) % num_shards for k in colliding_keys)
max_secret = max(secret_counts.values())
print("the SAME 200 keys under a SECRET seed:", dict(sorted(secret_counts.items())))
print(f"largest shard under secret seed: {max_secret}/200 = {max_secret/200*100:.1f}%")

Running this on 10,000 keys that are all multiples of 16, with num_shards=16: naive
key % 16 puts ALL 10,000 keys on shard 0 and leaves shards 1 through 15 completely empty.
Hashing first (FNV1a(key) % 16, a real non-cryptographic hash used here as an executable
stand-in for the MurmurHash family) spreads the same 10,000 keys across all 16 shards, with the
largest shard holding 6.3% of keys against a perfectly even 6.25%, repairing the pathological
skew.

For the adversarial case: 200 keys deliberately chosen (by brute-force search) to all hash to
shard 0 under a PUBLIC, known seed do exactly that, all 200 landing on shard 0. Re-hashing those
SAME 200 attacker-crafted keys with a different, secret seed spreads them across 4 shards
(28, 52, 70, and 50 keys respectively), with no single shard holding more than 35% of them,
confirming that the secret seed breaks a precomputed collision set the attacker built against
the public seed, even though it did not achieve a perfectly even spread across all 16 shards for
this specific crafted input.

Trade-offs and pitfalls

• Cryptographic hashing is not "safer by default" here. It defends against finding a
  preimage or a second colliding input given the digest, which is a different property than
  what sharding needs (uniform, fast bucket assignment); paying its computational cost buys
  security guarantees sharding does not require, unless the specific threat is a knowledgeable
  adversary choosing keys.
• A secret seed alone is not a magic uniform-distribution guarantee for every possible
  attacker-crafted key set, as the demo above shows (4 shards instead of 16 for this specific
  crafted set); rotate the seed periodically and monitor real shard-load distribution rather than
  assuming a keyed hash is a one-time fix.
• Testing on your OWN production key patterns matters more than a generic uniformity claim
  about the hash algorithm. A hash function can be excellent in general and still interact
  badly with an unusually structured key space your service happens to generate; validate against
  real keys, not just random test data.
• Resharding cost: modulo-based bucket assignment (hash(key) % num_shards) means changing
  num_shards remaps nearly every key to a different shard. If shard count needs to change
  often, consider consistent hashing instead, which minimizes remapping on shard-count changes at
  the cost of a slightly more complex lookup structure.