Pointer Walk

Hash Tables

One key, one bucket, no searching. Then two keys collide: chaining, probing, and when O(1) stops being true.

Data StructuresBeginner13 min read

Finding something without searching

You have a million usernames and need to know if ada is one of them. Checking them one by one could take a million steps. A sorted list and binary search gets that down to about twenty.

A hash table does it in about one step, no matter how many there are. It is the structure behind Python's dict, JavaScript's Map and objects, Java's HashMap, and most caches and database indexes.

The trick: let the key itself tell you where it is stored.

  1. Keep a row of numbered buckets

    A plain array. Bucket 0, bucket 1, bucket 2, and so on.

  2. Turn the key into a number

    A hash function takes the key and produces a number. The same key always gives the same number.

  3. Use that number to pick a bucket

    Divide by the number of buckets and take the remainder.

  4. Store it there, and look for it there

    To find the key later, do the same sum and go to the same bucket. No other bucket is touched.

Watch it fill up

The hash below is simple enough to check by hand: add up the letters (a = 1, b = 2, c = 3, ...) and take the remainder after dividing by 8.

Chaining · ordinary keysInteractive
0
1
2
3
4
5
6
7

Start. Eight empty buckets, numbered 0 to 7. The hash: add up the letters (a = 1, b = 2, ...) and take the remainder after dividing by 8.

Keys stored
0
Longest bucket
0
Extra checks
0

Example

Where does cat go?

c = 3, a = 1, t = 20. That adds up to 24. 24 divided by 8 leaves a remainder of 0. So cat lives in bucket 0, and anyone looking for cat will do the same sum and look in bucket 0.

Two keys, one bucket

In the animation, dog and owl both landed in bucket 2. That is a collision. Collisions are unavoidable: there are far more possible keys than buckets. A hash table needs a plan for them, and there are two common ones.

Chaining

Each bucket holds a small list. Colliding keys go into the same list, and a lookup walks that list. This is what the first animation does.

Linear probing

Each bucket holds one key. If the bucket is taken, try the next one, then the next, until a free one turns up. A lookup walks the same way until it finds the key or hits an empty bucket.

Linear probing · ordinary keysInteractive
0
1
2
3
4
5
6
7

Start. Eight empty buckets, numbered 0 to 7. The hash: add up the letters (a = 1, b = 2, ...) and take the remainder after dividing by 8.

Keys stored
0
Longest bucket
0
Extra checks
0

Probing keeps everything in one flat array, which computers read very quickly. Watch what happens near the end, though. Keys that could not get their own bucket fill up the neighbours, which pushes later keys further still. A run of full buckets forms and every new key that lands in it makes it longer. hen wanted bucket 3 and ended up in bucket 7.

Is it always one step?

"Hash tables are O(1)" is true on average, with a good hash function. Here is the same table with keys chosen to defeat our simple hash. They are anagrams: the same letters in a different order, so the letter sum is identical.

Chaining · keys that all collideInteractive
0
1
2
3
4
5
6
7

Start. Eight empty buckets, numbered 0 to 7. The hash: add up the letters (a = 1, b = 2, ...) and take the remainder after dividing by 8.

Keys stored
0
Longest bucket
0
Extra checks
0

Every key is in bucket 2. Finding one means walking the whole list, exactly like the slow search we were trying to avoid. In the worst case a hash table is just a list.

Real hash functions mix the bits thoroughly so that similar keys land far apart, and many languages add a random secret so that attackers cannot craft colliding keys on purpose.

Try the combinations

Chaining · ordinary keysInteractive
Collisions
Keys
0
1
2
3
4
5
6
7

Start. Eight empty buckets, numbered 0 to 7. The hash: add up the letters (a = 1, b = 2, ...) and take the remainder after dividing by 8.

Keys stored
0
Longest bucket
0
Extra checks
0

What it is good and bad at

Good at

  • Insert, find and delete in about one step on average
  • Works with any key that can be hashed: text, numbers, tuples

Where it bites

  • No order: you cannot ask for the smallest key or the next key after this one
  • Slow in the worst case, when many keys collide
  • Uses extra memory, because it must stay partly empty to stay fast

Key takeaways

  • A hash table turns the key into a bucket number, so it goes straight to the right place.
  • Two keys in one bucket is a collision. Chaining keeps a list per bucket. Probing uses the next free bucket.
  • Probing is fast in memory but forms runs of full buckets as the table fills.
  • Tables resize when they get too full, to keep lookups short.
  • O(1) is the average case. With bad luck or a bad hash, one bucket holds everything.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    9 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress