Hash Table Visualizer

A hash table makes one promise that sounds too good. Hand it a key and it will tell you, in about the same time whether it holds ten keys or ten million, whether that key is there.

The trick is to stop searching and start computing. A hash function turns the key into a number, the number names a slot in an array, and the table looks in that slot. The idea is old. In January 1953 Hans Peter Luhn described hashing with chaining in an internal IBM memorandum, and linear probing was in use by 1954 in an assembler for the IBM 701.

The promise has a qualifier that is easy to read past. A well-dimensioned table gives constant time on average. Everything interesting about hash tables lives inside those two words, because the average is taken over where the keys land, and where the keys land is decided by a function somebody chose.

Collisions are not bad luck

Two keys that hash to the same slot collide. It is tempting to treat that as an accident a better function would avoid. It cannot be avoided. A function that produces N bits must repeat itself somewhere among more than two to the power N inputs, and a table with 47 slots has far fewer places than there are possible strings.

Collisions also arrive long before the table is full. If the hash spreads keys evenly, the number of keys that call any one slot home follows a Poisson distribution whose mean is the load factor, the count of keys divided by the count of slots. At a load factor of 0.6 just over half the slots are empty, and about one in eight is home to two keys or more.

So every design is an answer to one question: what happens to the second key. There are two families of answer. Separate chaining lets the slot hold a list. Colliding keys queue up in the same place, and a search walks the queue. Open addressing keeps exactly one key per slot and sends the newcomer elsewhere in the array, along a probe sequence that a later search can retrace until it finds the key or reaches an empty slot.

The probe sequences differ in how they wander. Linear probing tries the next slot, then the next. Quadratic probing takes growing strides. Double hashing lets a second hash of the key set the stride, so two keys that start together soon part. Robin Hood hashing changes who moves: on a collision the key that has already travelled farther keeps the slot and the other one walks on, which evens out the lengths of the walks.

Deleting is the subtle part

Insertion and search are simple in every scheme. Deletion is where a plausible implementation is quietly wrong.

Here is a case small enough to hold in your head. Take a table of 11 slots and a deliberately poor hash, the code of the key’s first character. The letter k is 107, and 107 mod 11 = 8, so kiwi, kale and kelp all ask for slot 8. Under linear probing kiwi gets slot 8, kale is pushed to 9 and kelp to 10. Now delete kiwi by emptying slot 8, then search for kelp. The search starts at slot 8, finds it empty, and reports that kelp is not in the table. Kelp is sitting two slots away, unreachable.

Nothing was corrupted. The table simply relied on a fact that the delete destroyed: between a key’s home slot and its resting place there must be no gap. A search treats the first empty slot as proof of absence, so an empty slot in the wrong place is a false proof.

There are two honest repairs. One leaves a marker in the vacated slot, usually called a tombstone, that is treated as empty when inserting and as occupied when searching. The other, possible when the probe step is a single slot, closes the gap at once by moving later keys back toward home until nothing is stranded.

Tombstones are easy and they have a cost. They count toward how full the table is, so a table that has seen many deletions behaves like a fuller one, and eventually it has to be rebuilt just to clear them out.

What the load factor costs

Under the uniform hashing assumption, that the function spreads keys evenly over the slots, the classical results for linear probing are short. A search that finds its key takes about half of one plus 1 over (1 minus the load factor) probes. A search that fails takes about half of one plus the square of that same fraction.

Put numbers in. At half full, a hit costs 1.5 probes and a miss 2.5 probes. At 90 percent full a hit costs 5.5 and a miss 50.5 probes. The table did not get 80 percent busier; a failed search got twenty times dearer. Keys in a linear probing table gather into runs, long runs are the easiest to hit and each hit makes them longer, a habit known as primary clustering that Donald Knuth analysed in 1963. His treatment of hashing is in Sorting and Searching, the third volume of The Art of Computer Programming.

Chaining degrades gently by comparison: about one plus half the load factor for a hit, and at a load factor of 1 a miss costs about 1.37 probes. That difference is why the usual advice keeps open addressing tables no more than 60 to 75 percent full while chained tables run comfortably at loads between 1 and 3.

The cure is to grow. When the next insertion would pass the chosen load, the table allocates a larger array, commonly double the size, and inserts every key again, because a key’s slot depends on the size. One insertion in many is therefore expensive, and the cost is spread over the cheap ones before it.

The size itself has rules. With a prime number of slots, quadratic probing only ever reaches half of them, so it is safe only while the table is at most half full. With a power of two and strides that grow by one each time, it reaches every slot. Double hashing needs a stride that shares no factor with the table size, which a prime size gives for free and a power of two gives if the stride is forced to be odd.

The function carries the whole promise

Every figure above assumed an even spread. Take that away and the same table becomes a list. In the default example here, 30 seeded words sit in 47 slots under FNV-1a, a hit takes 1.93 probes against an expected 1.88, and a chi-square test of the home-slot counts gives 0.02 against a critical value of 3.841. Switch the hash to the first character and the keys pile into a handful of runs.

Bad functions are not always that obvious. Read a string as one long base-256 number and take the remainder by the table size, and the result is respectable for a prime size. Make the size 1,024 and the remainder depends only on the last characters: four different keys ending in zz all land in slot 634. This is the reason a prime modulus is the textbook choice for division hashing, and why a multiplicative hash uses a constant such as 2,654,435,769, which is two to the power 32 divided by the golden ratio.

FNV-1a is the plain workhorse of the four on offer. It starts from the offset basis 0x811C9DC5, and for each byte it takes an exclusive or and multiplies by the prime 16,777,619. Its authors placed it in the public domain, and its own specification is blunt that it is not a cryptographic hash.

That bluntness matters because a predictable hash is an attack surface. In 2003 Scott Crosby and Dan Wallach showed that carefully chosen input turns a hash table into a linked list, and used it against Perl, the Squid proxy and the Bro intrusion detection system with less bandwidth than a dialup modem. In 2011 an advisory reported the same weakness, by then in Java, PHP, Python, Ruby and others: crafted web requests full of colliding form parameters could hold a processor at full load for hours. Python later adopted SipHash as its default string hash, in version 3.4.

The defences follow from the diagnosis. Key the hash with a value the attacker cannot know, or notice an improbable pile of collisions and rehash with a changed function.

What the formulas do not say

The classical figures are approximations for large tables. Measured here over 200 seeded tables of 1,021 slots at 90 percent load, a failed search under linear probing averaged about 40 probes, not 50.5, and with 2,039 slots about 45. The small table is not better. The formula describes a limit that a small table has not reached, and single tables scattered widely around those averages.

Nor does a small demonstration say anything about real hardware, where linear probing’s habit of touching neighbouring memory is one reason it remains among the fastest tables in practice. What the pictures can do is make the structure of the argument visible: a key, a slot, a collision, a walk, and the one empty slot that every search trusts.