How a hash table really works

The competency matrix says a level 2 programmer can “explain how hashtables can be implemented and can handle collisions”. I get asked about that line more than any other one, usually by someone who’s used Dictionary<TKey, TValue> for years without needing to know what’s inside it. So here it is, with pictures.

The idea

You want to store key-value pairs and look them up by key in constant time. An array gives you constant-time access by index. A hash table turns a key into an index:

1. Run the key through a hash function to get a big integer. "apple".GetHashCode() might give you 1712946743.
2. Reduce it to the size of your array. With 8 buckets, 1712946743 % 8 = 7.
3. Store the pair at index 7.

Lookup does the same two steps and goes straight to the slot. The whole game is what happens when two keys land on the same index, which they will. With 8 buckets and 5 keys you’re more likely than not to get at least one collision. It’s the birthday paradox again, and one of the rare times my math degree pays off at work. The chance that all 5 land in different buckets is (8·7·6·5·4) / 8⁵ = 6720 / 32768, about 20%, so you get a collision about 80% of the time.

There are two classic ways to handle collisions.

Option 1: separate chaining

Each bucket holds a list. A colliding key just gets appended to that bucket’s list, and lookup walks the list comparing keys.

It’s simple, and it degrades gracefully: even an overfull table still works, just more slowly. Java’s HashMap and .NET’s Dictionary both use chaining. .NET does it cleverly: instead of allocating a linked-list node per entry, it keeps all the entries in one array and stores the “next” pointer as an integer index into that array. You get chaining’s simplicity without a heap allocation per insert, which matters a lot to the garbage collector.

Option 2: open addressing

Everything lives in the one array. If your slot is taken, you probe for another one by a fixed rule. The simplest rule is linear probing: try the next slot, then the next, wrapping around.

Open addressing is very cache-friendly. Probing the next slot is probably on the same cache line, while chasing a linked-list pointer can be a cache miss. That’s why it’s popular in performance-sensitive code. Python’s dict uses open addressing, but with a cleverer probe sequence that mixes in more bits of the hash, so that keys which collide once don’t keep colliding.

The catch is deletion. You can’t just empty a slot, because a later key might have probed past it, and an empty slot would cut its probe chain. So deleted slots get a “tombstone” marker that lookups skip over and inserts can reuse.

Load factor and resizing

Both schemes get slower as the table fills. The load factor is the number of entries divided by the number of buckets. Chaining tables usually resize around 0.75. Open addressing tables have to resize earlier, because probe lengths blow up as you approach 1. Python resizes its dict at two-thirds full.

Resizing means allocating a bigger array (typically double) and reinserting every entry, because each key’s index depends on the table size. That’s an O(n) operation, but it happens rarely enough that the cost averages out. Inserts are O(1) amortized, which is a phrase worth being able to explain in an interview.

One practical tip that falls out of this: if you know you’re about to insert a million items, pass a capacity to the constructor. new Dictionary<string, int>(1000000) skips about eighteen resizes.

When the hash function is the attack

At 28C3 in December 2011, Alexander Klink and Julian Wälde showed that most web platforms were vulnerable to an algorithmic complexity attack on exactly this. If an attacker can choose the keys, say the parameter names in a POST request, and the string hash is predictable, they can generate thousands of keys that all land in the same bucket. Every insert then walks the whole chain, the table turns into a linked list, and a single request can eat a CPU core for minutes.

The obvious fix is to make the hash unpredictable to outsiders by mixing in a random per-process seed, and the runtimes all scrambled to do some version of that. Perl had already randomized its hashing back in 2003 after an earlier version of the attack. Java 7u6 added an alternative seeded string hash for HashMap that you turn on with a system property. .NET 4.5 has the UseRandomizedStringHashAlgorithm config switch, and the ASP.NET patch (MS11-100) capped the number of form keys per request. Python 3.3 turned hash randomization on by default, which is why hash("apple") now gives you a different number every time you start the interpreter. That one has broken a fair bit of code that accidentally depended on dict ordering, which serves it right, a hash table never promised anyone an order.

Then at 29C3 this past December, Jean-Philippe Aumasson and Daniel J. Bernstein (with Martin Boßlet) showed that a random seed isn’t enough if the hash function itself is weak. They found ways to generate keys that collide regardless of the seed for MurmurHash2, MurmurHash3 and CityHash, which a lot of those “fixes” were built on. Their answer is SipHash, a fast keyed hash designed for exactly this job, and Ruby has already switched to it (CVE-2012-5371). I expect we’ll see more of that this year.

I had my own small run-in with this stuff a few years ago, in a much less glamorous way. A custom GetHashCode on a key class in a .NET app returned the sum of two small integer fields, so every key with the same sum landed in the same bucket. The profiler showed Dictionary.FindEntry eating most of a request’s time, and it took me an embarrassingly long time to realize the dictionary had quietly turned into a linked list. No attacker required. If you write your own GetHashCode, spread the bits around.*

So if someone asks you in an interview how a hash table works, I’d want to hear about turning keys into indices, a collision strategy and its trade-offs, load factor and amortized resizing, and the fact that the hash function is a security boundary. Most people stop after the first one.

* The usual trick is to multiply by a prime and add: hash = hash * 31 + field. Not perfect, a lot better than a + b.