Hash table

War and Peace has 436,069 words, 47,585 of them different. To count how many times each occurs, a program looks a word up in its dictionary 436 thousand times. In a sorted list such a lookup takes about sixteen comparisons, in a hash table one or two probes. Below are 4096 cells, and the novel’s words pour into them in order: «лев», «толстой», «том», «первый» (“Lev Tolstoy, volume one”)… The colour of a cell shows how many probes it takes to find the word lying in it. Move the load and switch the way the table resolves collisions.

At half full all three methods look equally calm: almost all the words lie in their own cells or nearby. Set 90% with linear probing. The table is covered with long hot stripes: neighbouring occupied cells have merged into clusters, and a word at the tail of a cluster takes dozens of probes to find. Double hashing at the same load stays patchy, and chaining does not even notice that the table is nearly full. On the chart under the table the dots are measurements and the lines Knuth’s formulas. Where these formulas come from and why linear probing is popular all the same is taken apart below.

The idea

An array gives a cell by its number in one step. Turn the key into a cell number, and it can be found as fast as reading by index. The function that makes a number from a key is a hash function; two different keys with one number are a collision. Collisions are inevitable, so the table knows how to resolve them, and to keep them few it keeps part of its cells free.

A hash function maps a key to a large number, and the cell number is the remainder of this number divided by the table size m. If two different keys get one number, that is a collision. The ratio of the number of keys n to the number of cells is called the load factor and written α = n/m. The main fact about hash tables: the mean cost of a lookup depends on α, not on n. A table of a billion keys at α = 0.5 makes as many probes per lookup as a table of a thousand.

Any hash table is four decisions: which hash function to take, where to put a collision, when to move to a bigger table and how to delete. The data sheet promises O(1), but this promise holds only if all four decisions are made correctly. Let us go through them in turn.

Decision one: the hash function

Three things are required of a hash function. Equal keys give equal hashes, always: if a == b, then hash(a) == hash(b), otherwise the table puts a key in one cell and looks for it in another. Different keys give, where possible, different hashes, scattered as if drawn by lot. And speed: the hash is computed at every lookup.

The most obvious functions fail the second requirement. The sum of letter codes gives all anagrams the same hash: «кот», «ток» and «кто» (cat, current, who) land in one cell. Word length takes up a handful of numbers: the novel has no words longer than 24 letters, so forty-seven thousand words would be crammed into a score of cells. In the course chapter on hashing five such functions are tested on the same vocabulary of War and Peace, and a bad one differs from a good one thousands of times over in the number of comparisons (the table in the chapter).

In all the listings and scenes we take FNV-1a: start from a fixed 64-bit number and for each byte of the key do an exclusive or, then multiply by a large prime. The multiplication spreads the influence of each byte over all the bits, so «кот» and «ток» get distant hashes. The same function works in this catalogue’s Bloom filter.

Decision two: where to put a collision

Can collisions be avoided by taking a bigger table? No: this is the birthday problem. In a table of 4096 cells, as in the scene, a collision becomes more likely than not already at the 76th word, at about 1.18·√m keys (derivation in “Mathematics, the Queen of the Sciences”). So a way to live with them is needed. There are two.

Chaining. A cell holds not a key but a list of keys, a chain. A new key is appended to the list of its cell, and a lookup goes through this list. The cells here are usually called buckets. Chains do not mind even α above one: there are fewer buckets than keys, but each chain stays short.

Open addressing. A cell holds at most one key, and on a collision the key looks for another place along a route known in advance. A lookup follows the same route and stops when it finds the key or an empty cell: empty means “no such key”. Open addressing does without lists and pointers, and the whole table is one dense array. The routes vary:

• linear probing: the next cell, the one after: i, i + 1, i + 2, …;
• double hashing: the step is also taken from the hash and differs between keys: i, i + s, i + 2s, … In our listings s is the high half of the same 64-bit hash, made odd: with a power-of-two size such a step goes through all the cells.

Linear probing suffers from primary clustering. Let the table have a run of L occupied cells in a row. A new key extends it if its home cell is any of these L or the free cell after them: probability (L + 1)/m. A long run catches keys more often than a short one, grows faster and merges with its neighbours. At 90% the longest cluster in the scene is 742 cells, almost a fifth of the table. Double hashing separates the routes of different keys, and clusters do not snowball.

How many probes are needed

Let the hash function be perfectly random: each key lands in any of the m cells with probability 1/m, independently of the others. Then on average:

The formulas for double hashing are derived in two lines. An unsuccessful lookup looks at cells until it meets an empty one; each next cell of the route is occupied with probability about α, so the probes average 1 + α + α² + … = 1/(1 − α). A successful lookup of a key repeats the path by which the key was once inserted, and the insertion cost as much as an unsuccessful lookup at the load x of that time. Average 1/(1 − x) over all x from 0 to α and you get (1/α) · ln(1/(1 − α)).

The square in the linear probing formula is the price of clusters. It was derived by Donald Knuth in 1963, and the derivation no longer fits into a paragraph: one has to count in how many ways n keys can be laid out on a ring of m cells.

Here is what came out on the novel’s real words. This is the output of the novel listing from the code section; the formulas are in brackets:

load  method   hit, formula   miss, formula  longest
 75%  linear   2.66 ( 2.50)   10.38 (  8.50)      144
 75%  double   1.85 ( 1.85)    3.98 (  4.00)       24
 75%  chains   1.39 ( 1.38)    0.75 (  0.75)        5
 90%  linear   8.17 ( 5.50)  109.19 ( 50.40)      742
 90%  double   2.52 ( 2.56)   10.12 (  9.99)       95
 90%  chains   1.47 ( 1.45)    0.90 (  0.90)        5

Chaining and double hashing agree with the formulas to the hundredths. Linear probing at 90% missed by a factor of one and a half to two, and the hash function is not to blame: on random numbers instead of words the spread is the same. The formula describes the average over all possible layouts, and in a particular table one huge cluster can eat a fifth of the cells and double the cost. The closer α is to one, the less predictable linear probing is.

Why is it used, then? Because of the processor cache. Neighbouring cells lie next to each other in memory, and five probes in a row cost almost as much as one: the processor pulls them in with one cache line. A chain of two nodes in different places of memory is two misses. So at a modest load linear probing in practice often turns out the fastest of the methods, and to keep the load from growing, the table is moved to a bigger one early.

Decision three: when to move

The formulas say that speed is set by α, so as the number of keys grows the table has to grow. Each implementation chooses a threshold after which it moves to a table twice as big:

Chains tolerate a high load, open addressing does not; the boldest thresholds belong to Swiss Tables, which compare eight to sixteen cells at once with a single processor instruction. The move itself is expensive: the cell number is the hash modulo the size, so with a new size every key has to be laid out anew. But if the size doubles each time, the moves cost in total less than 2n relocations for n insertions, the same arithmetic as for a dynamic array. So an insertion costs O(1) amortised: a rare expensive move is spread over many cheap insertions.

Amortised does not mean always. A table of a hundred million keys freezes for a noticeable time while moving, and systems for which every millisecond matters cannot accept that. Redis carries entries over to the new table bit by bit, at every operation, and keeps both for a while. Go’s map from version 1.24 is made of many tables of at most 1024 cells, and only the one that has become crowded moves.

Decision four: how to delete

With chaining deletion is trivial: take the key out of the list. With open addressing it is treacherous. A lookup stops at an empty cell, so a hole in the middle of a cluster cuts the route of everyone who lies beyond it and came past it. Delete «николай» (Nikolai) in the scene in “Erase” mode:

«кутузов» (Kutuzov) lives in cell 6, although its home is 5: when it was inserted, cell 5 was already taken by «николай». Clear it, and a lookup of «кутузов» starts at cell 5, sees emptiness and answers “no”. The key is in the table, but it cannot be found. There are two ways to fix this:

• Tombstone. In place of the key a mark “a key was here” is put. A lookup steps over it, an insertion may take it. This is how Python’s dictionary deletes. The downside: tombstones pile up, lengthen routes, and from time to time the table is rebuilt from scratch.
• Backward shift, for linear probing only. After a deletion go on along the cluster and move into the hole the first key whose route from home passes through it; then the same with the new hole, until an empty cell is met. The table stays as if the deleted key had never been there. This is Algorithm R from the third volume of Knuth’s “The Art of Computer Programming”, and the listing implements it.

Code

First, chaining. The buckets are a list of lists, and a bucket holds “key, value” pairs. When there are more keys than buckets, the table moves to one twice as big. The demo uses the names of the novel’s characters and how many times each occurs in the text:

In a table of eight buckets «наташа» and «николай» (Natasha and Nikolai) share bucket 4, «пьер» and «андрей» (Pierre and Andrei) bucket 7. After the move to sixteen buckets both pairs stayed together: their hashes agree not only in the three but in the four low bits. And «наполеон» (Napoleon), added last, landed in bucket 10 with «соня» (Sonya).

Now open addressing with linear probing. Keys and values lie in two parallel arrays, an empty cell is None in Python and an empty string in Go. Deletion in remove is the backward shift from the previous section, and the demo shows what would happen if the cell were simply erased.

And tables over the whole novel. The program reads War and Peace from the server where the code runs, takes the first 20,000 distinct words in order of appearance and puts them into tables of 4096 cells in three ways at loads of 50, 75, 90 and 95%. Unsuccessful lookups are measured on words 10,001 to 20,000: they never get into the table. These are the same numbers the first scene shows.

What it costs

The O(1) average rests on two conditions: the hashes are spread evenly, and α is bounded by a constant. The worst case is all keys in one cell, and the table turns into a list. Memory is O(n), but with a margin: a third or a quarter of the cells are empty on purpose, and chaining adds a pointer to each key.

A hash table has no order. It cannot find the nearest word alphabetically, all the keys from «а» to «б», or the minimum, except by going over everything. If such queries are needed, a search tree or a sorted array with binary search is taken: they search in O(log n) but remember the order. Below is a benchmark: looking up existing keys in random order in a dictionary and by binary search in a sorted list, on tables from a thousand to a million keys.

Hashing wins at any n, but look at its line: it is not horizontal. On a million keys a lookup in a Python dictionary costs about three and a half times more than on a thousand, and in Go five times more, although the number of probes is about the same on average. A small table sits entirely in the processor cache, a big one does not, and each probe becomes a trip to main memory. O(1) promises that the number of steps does not grow with n, but promises nothing about the cost of a step.

Where it breaks: a collision attack

Everything said about speed relied on the hashes behaving as if random. And what if the keys are chosen by an adversary? Java’s string hash formula is public: s[0]·31ⁿ⁻¹ + … + s[n−1] modulo 2³². The strings “Aa” and “BB” have the same hash: 65·31 + 97 = 66·31 + 66 = 2112. And since the hash of two strings glued together is the hash of the first multiplied by 31 to the power of the second’s length plus the hash of the second, any string of eleven blocks “Aa” and “BB” gets one and the same hash. There are 2¹¹ = 2048 such strings.

2048 words of the novel spread over 1024 buckets, the longest chain is 10, and inserting them all cost 2138 key comparisons. The attacker’s 2048 keys landed in one bucket, and each new key is compared with all the previous ones: 2048·2047/2 = 2,096,128 comparisons, a thousand times more. Twice the keys, four times the work: the attack turns O(n) into O(n²).

This is no textbook threat. In 2003 Scott Crosby and Dan Wallach demonstrated such attacks on Perl and the Squid proxy server. In December 2011 Alexander Klink and Julian Wälde showed at the Chaos Communication Congress that the parameters of an HTTP request in many popular web platforms, PHP, Java, Python, Ruby and the V8 JavaScript engine, are put into a hash table with a known hash function. A request of a megabyte with tens of thousands of chosen parameters kept a processor core busy for tens of seconds and even minutes.

There are three defences, and all are in use.

• A secret seed. The hash function depends on a random number that the program chooses at start-up and shows to nobody; collisions cannot be found without knowing it. This needs a function from whose outputs the seed cannot be computed: SipHash. Python made a random seed for strings the default in version 3.3 and moved to SipHash in 3.4, Rust uses SipHash-1-3 by default, and every map in Go has its own random seed. Switch the scene to “Secret seed”: the same attack keys scatter over the buckets.
• Trees in buckets. Since Java 8 a HashMap chain longer than eight (if the table has at least 64 buckets) turns into a red-black tree, and even with a total collision a lookup costs O(log n), not O(n). The “Trees” mode in the scene counts comparisons by this rule.
• Limits. PHP 5.3.9 in January 2012 simply limited the number of request parameters with the max_input_vars setting.

How real tables are built

The Swiss Table was devised at Google and presented in 2017. A separate array holds a byte per cell: whether it is free, deleted or occupied, and in the last case seven bits of the key’s hash. A lookup compares its seven bits with sixteen bytes at once (eight in Go) in one processor instruction and looks only into the cells where they matched. Keys are compared rarely, and a load of 7/8 stops being frightening. There are other techniques for high loads too: Robin Hood hashing, where a key that has gone far from home takes a cell from a key that has not gone far, and cuckoo hashing with a lookup in exactly two probes.

History

In January 1953 Hans Peter Luhn wrote in an internal IBM memo that a bin number could be computed from a key, and that records landing in one bin could be linked into a chain. A year later Gene Amdahl, Elaine McGraw (then Boehme) and Arthur Samuel were writing an assembler for the IBM 701 and came up with putting a record in the next free cell: linear probing. Andrei Ershov arrived at it independently while writing a programming program for the BESM, and published it in 1958. This story is told in detail in the course chapter.

In the summer of 1963 the young Donald Knuth derived the formula for the mean number of probes of linear probing, the very one with the square. Knuth later called this note the first analysis of an algorithm of a long career, and the analysis of algorithms as a field of its own is often dated from it.

Problems

In the first problem a hash table gathers anagrams from the novel’s vocabulary, and it is important not to confuse the key with the hash. In the second it turns a quadratic search over pairs into one pass, and the main thing there is not to pair a book with itself.