How a Hash Table Finds Things

Suppose you keep a list of words and want to know whether a particular word is on it. The obvious way is to start at the top and compare each word with the one you want, until you either find it or run out of list.

Here are 48 animal names, stored in the order they were added. Pick a word to look for, such as otter or badger, and watch the comparisons pile up:

Finding otter takes 45 comparisons, because otter happens to be 45th. A word near the top is found quickly and a word near the bottom slowly, so on average a search reads through half the list. A word that isn't there, like yak, costs the most: the only way to be sure it's missing is to compare it with all 48.

That cost grows in step with the list. With a million words, a lookup takes half a million comparisons on average, and a full million for every word that isn't there. Even at a hundred million comparisons a second, checking each word of a 100,000-word novel against such a list would take over eight minutes.

A hash table does the same job with two or three comparisons per word, however long the list is. The trick is to compute where a word should be, instead of searching for it. The rest of this page is about how that computing works, why it sometimes goes wrong, and what real tables do about it.

Turning words into numbers

Computers are very good at one kind of lookup. Memory is a long row of numbered places, and given a place's number, the computer reads what's there in one step, whether it's place 3 or place 3 million. If every word came with a number saying where to keep it, we could go straight there. A hash function makes that number from the letters of the word itself.

The one I'll use is called FNV-1a, after Glenn Fowler, Landon Curt Noll, and Kiem-Phong Vo, who designed itFNV dates from 1991 and is still used where a small, quick hash is enough: in compilers, DNS servers, and file systems.. Each letter is stored as a number between 0 and 255, its byte: o is 111 and t is 116. The hash is a 32-bit number that starts at a fixed value, 2,166,136,261. For each letter, two things happen. First the letter's byte is mixed in with XOR, which flips every bit of the hash where the byte has a 1. Then the hash is multiplied by 16,777,619, and everything above the lowest 32 bits is thrown away.

Type a word, or keep otter, and step through the recipe with the slider. The dots under the bits mark the ones that changed in the last step:

Each XOR changes only a few bits at the right-hand end, because a byte only has eight bits to flip. The multiplication then spreads the change leftward across the number, flipping about half of the 32 bits in one step. After the last letter, what's left is the word's hash: 2,778,288,937 for otter.

Two things make this useful. The recipe is fixed, so the same word always gives the same number, on any computer, every time. And the result looks random. Turn on Change the last letter and step back through: otter and ottes stay identical until the very last letter, its XOR makes them differ in one bit, and the final multiplication turns that into 9 differing bits spread across the number.

In code the whole recipe is five lines:

function fnv1a(text) {
  let h = 2166136261;                          // the offset basis
  for (const byte of new TextEncoder().encode(text)) {
    h ^= byte;                                 // mix in the byte
    h = Math.imul(h, 16777619) >>> 0;          // times the FNV prime, keep 32 bits
  }
  return h;
}

What makes a hash good

Almost any recipe that turns letters into a number could serve as a hash function. The simplest is to add up the letters' bytes. It's fixed, it's fast, and it gives every word a number. It's also terrible, and seeing why tells us what a good hash has to do.

A good hash has to react to every detail of its input. Change one bit anywhere in the word, and about half of the output bits should change, each with even odds, as if the hash had been drawn again from a hat. This is called the avalanche property. We can measure it directly: take random 4-byte inputs, flip one input bit, and count how often each output bit changes.

In the grid below, each row is one of the 32 input bits and each column one of the 32 output bits. A pale cell means that output bit changed in about half the trials, which is ideal. Blue means it rarely changed, red that it nearly always did; both are patterns an attacker, or just an unlucky set of keys, can exploit. Switch between the four recipes and point at a cell to read it:

Sum is a disaster: flipping a bit in the input changes only the matching bit of the output, plus sometimes a carry into the bits just above it. The grid is a blue field with a red diagonal down its right-hand edge, the only output bits that ever change. Times 31, the recipe Java uses for its strings, does better toward the left of each row, because the multiplications carry changes upward, but nothing ever moves a change down into lower bits: the bottom-right triangle of every block stays blue.

FNV-1a is pale over most of the grid, but not all of it. The last byte of the input gets mixed in by a single multiplication, and a multiplication only carries changes toward higher bits, so its rows still show a blue triangle. Adding a final mix, the three shifts and two multiplications that finish MurmurHash3Austin Appleby's MurmurHash3 ends with this "finalizer": shift right by 16 and XOR, multiply by 0x85EBCA6B, shift by 13 and XOR, multiply by 0xC2B2AE35, shift by 16 and XOR. The shifts carry changes downward, which multiplications can't., makes every output bit depend on every input bit, and the grid goes pale everywhere.

Avalanche is a statement about bits. What a table cares about is the result: do real words spread evenly over the buckets? Here are up to 4,000 made-up words sorted into 1,024 buckets. Each square of the grid is a bucket, darker the more words it holds. The bars compare how many buckets hold 0, 1, 2, … words with what a perfectly random scatter would give, the outlines:

With Sum, more than two thirds of the buckets stay empty while others hold twenty or more words, because sums of short words only reach a few hundred values. The other three recipes all land close to the outlines: about 145 empty buckets at 2,000 words, and the rest holding one, two, or three words, just as random scattering would. Times 31 spreads these words well even though its avalanche grid looked poor, a reminder that a test on one kind of key says little about the next. Hash functions are judged on many kinds of keys, including ones chosen to break themTest suites such as SMHasher feed a hash thousands of structured inputs (sparse bit patterns, keys that differ in one byte, long runs of zeros) and look for any departure from random..

From a number to a place

A 32-bit hash can be anything up to about 4.3 billion, and we don't want 4.3 billion places for a few words. A hash table keeps a much shorter array of buckets and puts each word in the bucket given by the remainder of its hash divided by the number of bucketsMany tables use a power of two for the number of buckets and keep only the low bits of the hash, which is faster than dividing. That only works if the low bits are well mixed, one more reason for the final mix.. With 16 buckets, otter's hash leaves a remainder of 9, so otter lives in bucket 9.

This table holds ten animals in 16 buckets. Pick a word to look up, or type your own in lowercase, and see which bucket it leads to:

Looking a word up repeats the steps that stored it: hash the word, take the remainder, go to that bucket. Only the words in that one bucket get compared, and here that's usually a single word. To learn that yak isn't stored, we don't compare it with anything at all, because its bucket, 12, is empty.

Look up koala, though. Bucket 9 holds two words, drawn in red: koala and otter have different hashes that leave the same remainder. That's a collision, and the price is a second comparison.

Collisions come early

Ten words in 16 buckets is crowded, so a collision there isn't surprising. It's tempting to think a roomier table would make them rare. Here are 365 buckets, one for each day of the year, filling with made-up words. There are in it now; drag that number, or the slider, and watch for red buckets holding two:

In this set the first collision comes with word 22, when the table is 6% full. The red curve is the chance that a random set of words has at least one collision: it passes 50% at 23 words and 99% at 57. Press New words a few times. The first collision moves around, but in a table of 365 it rarely waits past 50 words.

This is the birthday problem: in a room of 23 people, it's more likely than not that two share a birthday. Each new word has only a small chance of landing in an occupied bucket, but every pair of words is a chance to collide, and the number of pairs grows with the square of the number of words. A table with m buckets can expect its first collision after about 1.25\sqrt{m} words. For a million buckets that's only about 1,250 words.

So a hash table can't avoid collisions. It has to handle them, and there are two classic ways.

Two ways to share a bucket

Chains

The simplest is to let each bucket hold a list of words, called a chain. A new word joins the end of its bucket's chain, and a lookup walks along the chain, comparing as it goes. Add words to this table of 8 buckets with the slider, and point at or tap any word to see what finding it costs:

Finding a word costs one comparison for every word down to it in its chain. With 12 words in 8 buckets the chains are 1.5 words long on average, and finding a word takes 1.83 comparisons, close to the 1 + \alpha/2 = 1.75 that theory predicts for randomly scattered words. Here \alpha is the number of words per bucket, the load factor, and it sets the cost. A table of a billion words with a load factor of 1.5 needs the same number of comparisons on average as this one.

Chains are easy to get right, and the table never runs out of room. The price is that every word needs its own small block of memory with a link to the next, and following links jumps around memory. We'll see later how much that costs.

Probing

The other way keeps every word in the array itself, one word per slot. A word's home is the slot its hash points to. If the home is taken, the word goes in the next free slot, wrapping around from the last slot to the first. This is called linear probing, and each slot we look at is a probe. Add words one at a time to 16 slots arranged in a ring:

The blue arc is the path of the newest word, from its home to where it settled. otter's home, 9, belongs to finch, and slot 10 to mole, so otter lands in 11 after three probes. Words in red didn't get their home slot.

Keep adding words and notice how the full slots clump into runs. A word whose home falls anywhere inside a run has to go to the end of it, which makes the run longer, so long runs grow faster than short ones. This is called primary clustering. By the 14th word the runs have merged: raven's home is 13, and it has to walk around through 0, 1, and 2 to land in slot 3 on its seventh probe.

Lookups walk the same path. To find a word, start at its home and step forward until you see it. To be sure a word is missing, you have to step forward until you hit an empty slot, because a missing word could have been pushed anywhere along the run:

function find(slots, key) {
  let i = fnv1a(key) % slots.length;            // the key's home
  while (slots[i] !== null) {                   // an empty slot ends the search
    if (slots[i] === key) return i;
    i = (i + 1) % slots.length;                 // next slot, wrapping around
  }
  return -1;                                    // not stored
}

Misses cost more than hits, and the empty slots are what make lookups stop. That has a consequence that catches out almost everyone who writes their first table: deleting a word.

Step through a short history of one table of 10 slots. Four words go in, one is deleted, and then we look for the others, either by emptying the deleted slot or by leaving a tombstone in it:

With an emptied slot, step 6 goes wrong: the search for zuver starts at its home, 3, steps to the hole at 4, and gives up, although zuver is sitting in slot 5. Step 7 is worse, because rolovi's home is the hole itself. A tombstone fixes both: it's a marker that says "this slot is free to reuse, but keep searching past it". Lookups step over tombstones; insertions remember the first one they pass, make sure the word isn't stored further on, and put it there, which is what step 8 does with podozil.

Tombstones have a cost of their own. They take up slots that lookups have to walk over, so a table with many deletions gets slower even though it holds few words. Real tables count tombstones as part of their load and rebuild themselves when there are too manyFor linear probing there's also an exact alternative: after deleting, walk forward and pull back any word that could sit closer to its home. Knuth gives this as Algorithm R in section 6.4 ..

How full is too full

For a big table the cost depends on how full it is, the load factor again. This table has 997 slots in rows of 32, filled with made-up words using linear probing. Red slots hold words that were pushed from their home, darker the farther they went. It's full now; drag that number or try the presets, and watch the cost of a lookup in the plot:

At half full, finding a stored word takes 1.5 probes on average and ruling out a missing word takes 2.5. At 75% they're 2.4 and 8.5. At 90% a miss takes around 40 probes, and the grid shows why: the runs have merged into long red bands, and a miss has to walk to the end of one. The thin dotted lines are formulas Donald Knuth worked out in 1963 , where \alpha is the fraction of slots in use:

The measured curves, averaged over eight tables, follow them closely until the table is nearly full. The square in the second formula is primary clustering at work: as the table fills, runs get longer and a miss is more likely to land in one, so the two effects multiply.

Chains behave better when crowded, because a chain only grows when a word hashes to that exact bucket: at a load factor of 0.9, a hit costs about 1.45 comparisons and a miss walks a chain of 0.9 words on average. Either way, a table that wants to stay fast can't be allowed to fill up. Before we see how tables make room, there are two cleverer ways to probe.

Taking from the rich

Look again at the ring with 15 words. Most words sit in their home slot or one past it, and raven walked six slots to find a place. The average lookup is fine; the trouble is the unlucky few. In 1985 Pedro Celis, Per-Åke Larson, and Ian Munro proposed a small change to insertion that evens this out . They called it Robin Hood hashing, because it takes from the rich and gives to the poor.

While a new word probes, it compares how far it has come from its home with how far the word in each slot came from its own. If the new word has traveled farther, it takes the slot, and the word it displaced carries on probing in its place. Words that got lucky give up their slot to words that didn't. The numbers under each slot are distances from home; switch between the two rules with the same 15 words:

Under plain probing, raven ends up 6 slots from home and zebra 5, while eight words sit at home. Switch to Robin Hood and the longest distance drops to 3. Step back to 14 words and forward again to watch raven: on its way it meets words sitting at their home slots, which are "rich", and pushes them along. The extra moves cost a little at insertion time, but every word gets its share.

The effect is easiest to see in a big table. Here are the same words in two 997-slot tables, one filled by plain linear probing, the other by Robin Hood, at full. The bars show what share of words takes 1, 2, 3, … probes to find:

At 85% full both tables average 3.5 probes per word, but plain probing has words that need 53 probes, and Robin Hood's worst needs 12. Robin Hood's bars are piled up around the average; plain probing has a long thin tail running off to the right. That tail is what a program feels as an occasional slow lookup. Robin Hood also gives misses an early exit: once the search reaches a word that's closer to its home than the missing word would be, the missing word can't be further on.

function insertRobinHood(slots, dist, key) {
  let i = fnv1a(key) % slots.length, d = 0;     // d: how far key has come
  while (slots[i] !== null) {
    if (dist[i] < d) {                          // the resident is richer:
      [slots[i], key] = [key, slots[i]];        // take its slot, and carry it
      [dist[i], d] = [d, dist[i]];              // on as the word to place
    }
    i = (i + 1) % slots.length;
    d++;
  }
  slots[i] = key;
  dist[i] = d;
}

Two homes for every key

Robin Hood shortens the worst case. Cuckoo hashing, published by Rasmus Pagh and Flemming Friche Rodler in 2001, gets rid of it . It keeps two tables and two different hash functions, and every word may live in only two places: its slot in table 1 or its slot in table 2. A lookup checks those two slots and nothing else, so it never takes more than two probes, however unlucky the words.

The work moves to insertion. A new word goes into its slot in table 1 or table 2, whichever is free. If both are taken, it evicts the word in one of them, the way a cuckoo chick pushes another egg out of the nest. The evicted word then moves to its other slot, perhaps evicting another, and so on until someone lands in an empty slot. Step through eight animals going into two tables of 8 slots each:

The first five words find a free slot at once. Whale, at step 6, finds both its slots full, takes slot 7 of table 1 and evicts zebra, which moves to its slot in table 2 and is done: one eviction. Then wolf arrives. Its eviction knocks out heron, heron knocks out newt, newt knocks out wolf again, and the chain goes round the same few words. Step through the circle: these words have only a handful of slots between them and there's no arrangement that fits them all.

When the evictions go on for too long, here after nine in a row, the table gives up, picks two new hash functions, and places every word again. That's expensive, but it's rare as long as the tables are less than half full: two tables with one word per slot work reliably up to about 50% load, and variants that let each slot hold four words run well past 90%. In exchange, every lookup is at most two probes, which makes cuckoo tables popular in network hardware, where a lookup has to finish in a fixed number of clock cycles.

Making room

Every scheme so far needs spare room. When a table gets too full, it allocates an array twice as big and moves every word across. A word's slot depends on the number of slots, so each word has to be placed again: take the remainder with the new size, then probe. This table starts with 8 slots and doubles whenever one more word would make it more than two-thirds full. Add words with the slider and watch what each insertion costs:

Most insertions take a probe or two, the blue bars. Each time the table doubles, one unlucky insertion pays for moving everything, the purple spikes: 5 words at the first doubling, then 10, 21, 42, 85, and 170. The spikes get bigger, but they also get rarer at the same rate. Each doubling moves about as many words as were added since the last one, so spread over every insertion, moving costs about two extra probes per word. The black line, all the work so far divided by the words stored, wobbles between about 2 and 5 probes and doesn't climb, however many words we addThis "spread the cost over every insertion" accounting is called amortized analysis. It's why programmers can say a hash table insert takes constant time even though an occasional insert takes far longer..

Growing at two-thirds full also means the table is never more than two-thirds full, and right after a doubling it's only a third full. From the measurements, that caps the average lookup at about 2 probes for a word that's there and 5 for one that isn't.

Memory is not flat

So far every probe and every comparison has counted the same. On a real computer they don't. A processor keeps recently used memory in a small, fast cache, and it fetches main memory in blocks of 64 bytes called cache lines. Reading something already in the cache takes about a nanosecond. Reading something that isn't takes around 100 nanoseconds, during which the processor mostly waitsThe exact figures vary by machine: a few cycles for the closest cache, tens for the larger ones, and roughly 60 to 120 ns for main memory on desktop and server processors..

That changes the comparison between chains and probing. A probing table keeps its words side by side, so if a slot is 8 bytes, one cache line holds 8 slots, and a run of probes mostly reads slots that came in with the first one. A chained table follows a link to each word, and each link usually leads somewhere new in memory, so each step down a chain is likely another 100 ns wait. Here's a simple model of both, at a load of :

For lookups that find their word, probing wins at every load in this model, by up to a factor of two: probing pays for one trip to memory and a few cheap reads, while chaining pays for the bucket array and then at least one node. Switch to misses and the picture changes past about 70% full: a miss in a crowded probing table reads so many slots that it spills across many cache lines, while a chained miss only walks one short chain. That is why probing tables are usually kept below 70 or 80% full, and why many of the fastest modern tables use probing with small groups of slots that the processor can compare all at once.

The model leaves a lot out. Real chains can be allocated close together, small tables fit entirely in cache, and the processor can fetch several lines at once. But the main lesson holds on real hardware: counting probes is not the same as counting time, and the layout of memory matters as much as the number of steps.

Keys chosen by an attacker

Everything so far assumed that keys arrive by chance, so the hash scatters them like random numbers. A web server that stores the names of form fields, the parameters of a request, or the keys of an uploaded JSON object in a hash table doesn't get to choose its keys. Someone else does.

FNV-1a is public, so anyone can search for words that land in the same bucket. Here are 60 made-up words I found by trying a few thousand and keeping the ones whose FNV-1a hash is a multiple of 64, so they all go to bucket 0 of a 64-bucket table. Insert of them into a chained table, which has to compare each new key against the chain to make sure it isn't already there:

With FNV-1a, all 40 keys pile into bucket 0, and inserting them takes 780 comparisons, one for every pair of keys. The work grows with the square of the number of keys, so the 60th key alone costs 59 comparisons, and an attacker who sends a hundred thousand such keys in one request makes the server do about five billion. In 2003 Scott Crosby and Dan Wallach showed this kind of attack against real programs , and in 2011 Alexander Klink and Julian Wälde showed that the web frameworks of most popular languages could be stalled for minutes by a single crafted request .

The cure is a hash the attacker can't predict. Switch the server to SipHash, a keyed hash designed by Jean-Philippe Aumasson and Daniel J. Bernstein for exactly this job . It mixes a secret 128-bit key, chosen at random when the server starts, into every hash. The attacker's words were chosen to collide under FNV-1a; under SipHash with an unknown key they're just 60 ordinary words, scattered like any others. Press Restart with a new secret and they scatter differently each time, which is the point: without the key, there's no way to find words that collide.

After 2011, Python, Ruby, and Perl added random keys to their string hashing, and Python and Ruby moved to SipHash, which Rust had used from the start. The price is speed: SipHash does more work than FNV-1a, which is why tables that only ever see trusted keys, such as a compiler's symbol table, still use faster unkeyed hashes.

Many machines, one ring

One last problem appears when a table outgrows a single computer. A cache spread over many servers needs to decide which server holds each key, and the obvious rule is the one from the start of the page: hash the key, take the remainder by the number of servers. That works until a server is added. Then nearly every key's remainder changes, nearly every key moves to a different server, and the whole cache goes cold at once.

Consistent hashing, from David Karger and colleagues in 1997 , avoids this. Hash both the servers and the keys onto a circle, and give each key to the first server clockwise from it. Adding a server takes over only the keys between it and the server before it. The dots below are 300 keys, colored by the server that holds them; ringed dots are the ones that moved when the last server joined. There are now:

On the ring, adding a fifth server moves the keys it takes over and leaves everything else where it was. With hash mod n, going from four servers to five moves about 80% of the keys. But the ring has a flaw of its own: with one mark per server, the arcs between marks are uneven, and so are the loads; one server here holds several times as many keys as another. The fix is to put each server on the circle many times. Turn on virtual nodes: with 40 marks per server the arcs average out, the loads even up, and adding a server still moves only about one key in n, a few from every other server instead of a big piece from one.

Consistent hashing was invented for web caches, and it was at the heart of Akamai's content delivery network, founded by two of its authors. It now spreads data in distributed databases such as Amazon's Dynamo and Apache Cassandra, and spreads requests across servers in many load balancers.

Back to the million words

Put the pieces together for a list of a million words. Scanning took half a million comparisons per lookup. A hash table hashes the word, which takes a few operations per letter, divides once for the remainder, and looks at about two slots, usually within one cache line. The million words don't enter into it: the cost depends on how full the table is, and resizing keeps that in check.

Real hash tables are refinements of the same few ideas. Python's dictionaries grow at two-thirds full and probe in a scrambled order instead of slot by slot, which avoids primary clustering. Java's HashMap uses chains, grows at 75% full, and turns any chain longer than eight into a small balanced tree, a second line of defense against colliding keys. Google's and Rust's tables probe groups of 16 slots at once with a single processor instruction. Python, Ruby, and Rust hash strings with a secret key. Distributed systems put the whole idea on a ring.

All of them still work the way the figures above do: turn the key into a number that looks random, turn the number into a place, and keep enough empty space that the place is almost always the right one.

References

1. Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998. Section 6.4, “Hashing”.
2. Pedro Celis, Per-Åke Larson, and J. Ian Munro, “Robin Hood hashing”, 26th Annual Symposium on Foundations of Computer Science (FOCS), 1985. Celis's PhD thesis, Robin Hood Hashing (University of Waterloo, 1986), has the full analysis.
3. Rasmus Pagh and Flemming Friche Rodler, “Cuckoo hashing”, Journal of Algorithms 51 (2004), 122–144. First presented at ESA 2001.
4. Scott A. Crosby and Dan S. Wallach, “Denial of service via algorithmic complexity attacks”, 12th USENIX Security Symposium, 2003.
5. Alexander Klink and Julian Wälde, “Efficient denial of service attacks on web application platforms”, talk at the 28th Chaos Communication Congress (28C3), Berlin, December 2011.
6. Jean-Philippe Aumasson and Daniel J. Bernstein, “SipHash: a fast short-input PRF”, INDOCRYPT 2012, Lecture Notes in Computer Science, Springer, 2012.
7. David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, and Daniel Lewin, “Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web”, 29th ACM Symposium on Theory of Computing (STOC), 1997.
8. Giuseppe DeCandia and others, “Dynamo: Amazon's highly available key-value store”, 21st ACM Symposium on Operating Systems Principles (SOSP), 2007.