Hashing in practice: hash functions, sets and consistent hashing
What a hash function does, how hash sets give fast lookups, why hash mod n reshuffles everything when servers change, and how a consistent hash ring with virtual nodes fixes it.
Hashing turns any key into a number. That one idea gives you O(1) lookups, duplicate detection, and a way to spread data over many servers.
What a hash function does
A hash function maps a key (a string, a number, a URL) to a fixed-size number:
- Deterministic: the same key always gives the same hash.
- Spread out: similar keys (
user1,user2) give very different hashes. - Not unique: different keys can collide; everything built on hashes must handle that.
A simple, well-known example is 64-bit FNV-1a:
h = 14695981039346656037
for each byte b of the key:
h = (h XOR b) * 1099511628211 (mod 2^64, i.e. let it wrap)In C++, do that in std::uint64_t, where wrap-around is defined.
Hash sets: "have I seen this?"
A hash set answers "is this in the set?" in O(1) on average. That's how a password checker tests a candidate against a list of a million leaked passwords without scanning it:
leaked = hash set of every password in the list (built once)
is_leaked(p) = leaked.contains(normalise(p))Normalise before inserting and before looking up, the same way both times: lowercase,
replace common substitutions (@ → a, 0 → o), trim. Anything you forget to normalise on one
side is a bypass. See password rules for Lockstep.
Why hash mod n reshuffles everything
The obvious way to pick a server for a key is hash(key) % n. It spreads keys evenly, until n
changes. Going from 4 to 5 servers changes % n for about 80% of keys: nearly every cache
entry is suddenly on the wrong server, and they all miss at once.
The hash ring
Consistent hashing places servers and keys on the same circle of hash values (0 to 2⁶⁴−1, wrapping around). Each key belongs to the first server at or after its position, clockwise:
ring = sorted map: hash(server) -> server
owner(key):
it = ring.lower_bound(hash(key))
if it == end: it = begin # wrap around the circle
return it.serverAdding a server only takes over the keys between it and its predecessor: about 1/n of them.
Removing one hands its keys to the next server. Everything else stays put. The sorted map and
lower_bound make each lookup O(log n); see
binary search.
Virtual nodes and weights
With one point per server, the arcs between them are very uneven: one server might own 40% of the
circle. Give each server many points instead, hashing "server-a#0", "server-a#1", … up to,
say, 100. The arcs average out. A server with twice the capacity gets twice the points.
For replicas ("store each key on 3 servers"), keep walking clockwise from the key's position and collect points until you have 3 distinct servers, skipping further points of servers you already have.
Testing a distribution
You can't test "evenly spread" with one example. Hash many keys (say 100,000) and check the share of each server against its expected share, with a tolerance (within 10%, for example). Use fixed key names so the test gives the same result on every run, and test the movement property directly: add a server and check that only keys now owned by the new server changed owner. Build it in sharding with a hash ring for Shardline.
Questions and answers
- What is consistent hashing used for?
- Spreading keys over servers (caches, database shards) so that adding or removing a server moves only about 1/n of the keys, instead of nearly all of them as with hash(key) mod n.
- Is std::hash good enough for consistent hashing?
- Not for anything that must agree across machines or runs: std::hash isn't specified, may differ between compilers and versions, and for integers is often the identity. Use a fixed, documented function such as FNV-1a or a 64-bit mixer.
Practise it in a project
These projects put this guide to work, with tickets, tests and code review.
Shardline
Sharding with a hash ring for Shardline
Replace modulo sharding with consistent hashing: a ring with virtual nodes that moves few keys when servers come and go, then replicas and weighted servers.
- consistent hashing
- ordered maps
- hash functions
- statistical testing
Lockstep
Password rules for Lockstep
Check new passwords against Lockstep's policy and a list of leaked passwords, and tell users every problem at once.
- character classes
- UTF-8 basics
- hash sets
- normalisation
Hopwire
Link shortener for Hopwire
Build the core of Hopwire's link shortener: turn long campaign URLs into short codes and back again, then give the support team a console to use it.
- hash maps
- number bases
- input validation
- streams
- unit tests
Quickcart
A product cache for Quickcart
Put a least-recently-used cache in front of Quickcart's slow product service, with O(1) operations, statistics and live resizing.
- hash maps
- linked lists
- iterator stability
- amortised O(1)
Read next
- Big-O in practice: amortised cost, worst cases and memory
What Big-O tells you on the job: the costs of common operations, amortised O(1), inputs that trigger the worst case, memory as a cost, and when to measure instead of guessing.