Hashing

Turning a key into a slot number so that a lookup never has to search.

5 topics2 lessons1 families

A hash table computes a slot from the key and goes straight to it. That is the whole idea: rather than comparing the key against the contents until one matches, you compute where the contents ought to be. When it works, insert, lookup and delete are one array access each, whatever the size of the table.

It works most of the time and not every time. Two keys can land on the same slot, and then something has to give. Linear probing walks forward to the next free slot, quadratic probing jumps further each attempt, double hashing gives each key its own stride, and separate chaining hangs a list off the bucket. All of them turn one array access into a short walk, and the length of that walk is governed by the load factor, entries divided by buckets. Past roughly 0.7 the walks get long, which is why tables double and reinsert everything.

So the cost is expected O(1), not guaranteed O(1): the worst case, every key in one bucket, is O(n), and the occasional rehash is an O(n) operation hidden inside an average. In exchange you give up order. A hash table cannot tell you its smallest key, the next key after this one, or everything between two bounds.

After this you can

Insert, look up and delete a key, and follow the probe path each of them walks
Explain why a deleted slot becomes a tombstone rather than an empty one
Compute a load factor and say what it predicts about the next probe length
Say what a rehash costs, when it fires, and why inserts stay O(1) on average anyway

Slot 1 holds 12, not 45. Walk on to slot 2.

Open in the player →or start at step 3

In this order

Where people go wrong

Clearing the slot on delete

With open addressing, a genuinely empty slot is what tells a lookup to stop. Empty the slot of a key that other keys probed past, and those keys become invisible even though they are still in the table. Mark it used-and-emptied instead.

Trusting the hash function

Key mod capacity spreads badly when the keys share a factor with the capacity: multiples of 10 in a table of 100 buckets use ten of them. Every operation then becomes a linear scan of one long chain, and no probing strategy repairs it.

Holding a slot index across a rehash

Doubling the table recomputes every key mod the new capacity, so entries move to different buckets. Anything that cached an index, or an iterator part way through, is pointing at the old layout.

Or a different category

Tree Algorithms

You need the keys in order: the minimum, the next one up, or everything between two bounds.

Searching

The data is already sorted and halving it costs less than building a table over it.