How a hash table finds things fast
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.
Step by step
- You store "apple" with the value 3. The table feeds "apple" into its hash function and gets back a number.
- The number is reduced to a slot index, for example the remainder after dividing by the number of slots. The pair goes there.
- Later you ask for "apple". Same function, same number, same slot. The table jumps there and compares the stored key to be sure.
- 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.
- 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
- Python, Design and History FAQ: How are dictionaries implemented in CPython? — hash code per key, used to calculate a location in an internal array; constant-time retrieval when keys have different hash values; a mutated key can no longer be found
- Java SE 21, class HashMap — buckets, load factor, rehashing to about twice the buckets when the table gets too full; many keys with the same hash code slow down any hash table
- Swift standard library, Dictionary.swift — "A dictionary is a type of hash table", any
Hashabletype can be the key, amortized O(1) lookup for native dictionaries