How a hash table finds things fast

· 3 min read

#how-it-works#data

A hash table is the structure behind Swift's Dictionary, Python's dict and Java's HashMap. The one idea to keep: it does not search for a key, it computes where the key must be.

The short version

A plain list makes you check entries one by one. A hash table runs the key through a hash function, which turns it into a number. That number picks a slot in an internal array, and the key and its value go into that slot. A later lookup repeats the calculation and lands on the same slot. As long as different keys mostly get different slots, a lookup costs about the same with ten entries or ten million.

How a key is turned into a slot in a hash table The key apple goes into a hash function, which returns the number 42. The number is reduced to slot 2 of an array with eight slots, and the pair apple and 3 is stored in slot 2. Another key, pear, sits in slot 5. Key: "apple" Hash function Number: 42 1 hash it 2 result 3 slot = 42 mod 8 = 2 apple value 3 pear value 7 0 1 2 3 4 5 6 7
Storing and finding "apple" follow the same three steps, so both land on slot 2. The numbers 42 and 8 are made up for the picture.

Step by step

  1. You store "apple" with the value 3. The table feeds "apple" into its hash function and gets back a number.
  2. The number is reduced to a slot index, for example the remainder after dividing by the number of slots. The pair goes there.
  3. Later you ask for "apple". Same function, same number, same slot. The table jumps there and compares the stored key to be sure.
  4. Two keys can land in the same slot. That is a collision, and the table then compares a few keys instead of one. Many collisions are what makes a hash table slow.
  5. When the table gets too full, it allocates roughly twice as many slots and places every entry again, so slots stay mostly free and lookups stay short.

Why it matters

This runs every time you use a Swift Dictionary or Set, which is why their keys must be Hashable. It also explains why a key must not change while stored: a changed key hashes to a different slot, and the entry is lost.

Sources