Hash Tables, Sharding & Bloom Filters

The most common use of hashing has nothing to do with security: it’s turning a key into a location. Because a good hash spreads inputs uniformly, hash(key) % N picks one of N buckets with roughly equal load, deterministically, without any lookup table.

Hash tables

Every dict, HashMap, Map, and set works this way:

1. Compute hash(key).
2. index = hash % capacity picks a slot in an array.
3. If the slot is taken by a different key (a collision), resolve it — chain a linked list off the slot (Java’s HashMap), or probe the next slots (Python’s dict, open addressing).
4. When the table gets too full (load factor ~0.75), allocate a bigger array and rehash everything.

That gives O(1) average lookup, as long as the hash spreads keys evenly. Two rules follow:

• Keys must hash consistently with equality. If a.equals(b), then a.hashCode() == b.hashCode() — overriding one without the other in Java is a classic bug where a key is “in” the map but get returns null.
• Don’t mutate keys while they’re in a table. The key’s hash changes, and it’s now filed in the wrong bucket.

Sharding: hash(key) % N, and its problem

The same trick spreads data across servers: shard = hash(user_id) % 4. It’s simple and balanced — until you add a fifth server. Then hash % 5 gives a different answer than hash % 4 for about 80% of keys, and nearly all your data has to move (or, for a cache cluster, nearly every lookup misses at once).

Consistent hashing

Instead of % N, hash both servers and keys onto the same circular space (0 to 2³²−1). Each key belongs to the first server clockwise from it. Adding a server only takes over the keys in the arc just before it — about 1/N of keys move, not most of them.

Raw consistent hashing has uneven arcs, so in practice each server is placed at many points on the ring (virtual nodes, often 100–256 per server). More vnodes → smoother load, and a server’s load is spread across all others when it leaves.

Used by: Amazon Dynamo / DynamoDB, Cassandra, Riak, memcached client libraries (ketama), Envoy and NGINX hash ... consistent load balancing, CDNs.

Bloom filters: “definitely not” or “probably yes”

A Bloom filter answers “have I seen this item?” using a tiny fraction of the memory of storing the items themselves, at the cost of occasional false positives.

1. Start with an array of m bits, all 0.
2. Add an item: hash it with k different hash functions, set those k bits to 1.
3. Check an item: hash it the same k ways. If any bit is 0 → the item was definitely never added. If all are 1 → it probably was (or those bits were set by other items).

add("alice")  → bits 3, 9, 14 set
add("bob")    → bits 1, 9, 20 set
check("carol") → bits 3, 7, 20 → bit 7 is 0 → definitely not present
check("dave")  → bits 1, 3, 14 → all 1 (set by alice & bob) → false positive

With ~10 bits per item and 7 hash functions, the false-positive rate is about 1% — regardless of how big the items are. No false negatives, ever. You can’t delete items (use a counting Bloom filter or a cuckoo filter for that).

Other “hash to decide” patterns

• Load balancing with session affinity: hash(client_ip) → backend keeps a client on the same server without shared session state.
• A/B testing and gradual rollouts: hash(user_id + experiment_name) % 100 < 10 puts a stable, random-looking 10% of users in the experiment. Including the experiment name makes each experiment’s buckets independent.
• Sampling: keep only events where hash(trace_id) % 1000 == 0 — every service makes the same decision for the same trace, with no coordination.
• Count-distinct at scale: HyperLogLog hashes each item and tracks the longest run of leading zeros, estimating billions of unique visitors in ~12 KB (Redis PFADD/PFCOUNT).
• Similarity search: MinHash and SimHash produce hashes where similar documents get similar hashes — the opposite of the avalanche effect, on purpose — for near-duplicate detection.