TL;DR:
A hash table stores items in buckets chosen by a hash function, so a lookup jumps straight to the right bucket instead of searching.
Two keys can land in the same bucket. That is a collision, and it is handled by keeping a short list in each bucket.
On average a lookup takes constant time, O(1), as long as the table is not overfull and the hash spreads keys evenly.
Your phone's contacts app has hundreds of names, and typing one finds the number instantly. It does not read the list from the top. Somewhere under the hood, a structure takes the name and goes almost straight to where its number is stored. That structure is a hash table, and it is also how Python's dictionaries work.
The idea in plain words
A hash table is an array of slots called buckets. A hash function takes a key, such as a name, and turns it into a bucket number. To store a contact, hash the name and put the entry in that bucket. To find it later, hash the same name, go to that bucket, and look there.
The cost does not depend on how many contacts there are. Computing the hash and jumping to a bucket takes the same effort for 10 names or 10,000. A list would need to be searched item by item.
Why a good hash function matters
A hash function must give the same bucket for the same key every time, and it should spread different keys evenly over the buckets. If every key landed in one bucket, the table would behave like a plain list. Real hash functions mix the bits of the key thoroughly to avoid this.
Worked example: a contacts app
To keep the numbers small, use a toy hash function and 5 buckets, numbered 0 to 4. The hash of a lowercase name is the sum of its letter values (a = 1, b = 2, up to z = 26), divided by 5, keeping the remainder.
def toy_hash(name):
return sum(ord(c) - 96 for c in name) % 5
for n in ["ann", "bob", "cy", "eve"]:
print(n, toy_hash(n))Name | Letter values | Sum | Sum mod 5 (bucket) |
|---|---|---|---|
ann | 1 + 14 + 14 | 29 | 4 |
bob | 2 + 15 + 2 | 19 | 4 |
cy | 3 + 25 | 28 | 3 |
eve | 5 + 22 + 5 | 32 | 2 |
The program prints ann 4, bob 4, cy 3, eve 2. Now store all four.
Bucket | Contents |
|---|---|
0 | empty |
1 | empty |
2 | eve |
3 | cy |
4 | ann, bob |
Ann and Bob both hash to bucket 4. That is a collision. One common fix is chaining: each bucket holds a short list of the entries that landed there.
Lookup for bob. Hash gives 4. Look in bucket 4: the list has ann, then bob. Compare names: ann is not bob, bob matches. Two comparisons, not four. Lookup for cy. Hash gives 3, and the bucket holds only cy: one comparison. Lookup for zed. 26 + 5 + 4 = 35, and 35 mod 5 is 0. Bucket 0 is empty, so zed is not in the table, found in one step.
Comparing with a plain list
Suppose the app holds 10,000 contacts in a list and you search for one that is in it. On average you would check about half the list, around 5,000 names, and in the worst case all 10,000. A hash table with enough buckets would, on average, check one or two entries. Doubling the contacts doubles the list's work, while the table's work stays about the same.
The trade-off is memory and order. A hash table keeps spare empty buckets so that chains stay short, and it does not keep the keys in alphabetical order. If you need the contacts sorted by name, a sorted list is the better tool.
What keeps it fast
Spread. The better the hash spreads keys, the shorter the chains.
Load. If the table fills up, chains get longer. Real tables resize themselves, making more buckets and moving the entries, before that happens.
Worst case. If every key collides, lookup falls back to searching one long list, which is O(n). Good design makes this extremely unlikely.
That is why we say lookups take O(1) on average, but not always. For more on those terms, see Big O notation with everyday examples.
When the table gets crowded
Our toy table has 5 buckets and 4 entries. The load factor is entries divided by buckets: 4 ÷ 5 = 0.8. Add four more contacts and it would be 8 ÷ 5 = 1.6, which means that on average each bucket holds more than one entry, so chains grow. Real implementations watch this ratio and, when it passes a limit, allocate a bigger array and re-insert every entry using the new bucket count.
How to check your answer
Recompute each hash. The same key must always give the same bucket.
Every stored item must be in the bucket its own hash points to.
A lookup that follows the same steps as the store must find the item.
Count comparisons per lookup. They should be small, and mostly one.
Common mistakes
Thinking a hash is encryption. A table hash is not meant to be secret, and it is not reversible by design.
Assuming no two keys can collide. With more keys than buckets, some must.
Storing mutable keys. If a key changes, its hash changes, and the entry is lost.
Assuming the order of items in a hash table means anything.
Where you will use it next
Hash tables are behind Python dictionaries and sets, as you used in lists, dictionaries and sets, caches, and duplicate checks. A different kind of structure, the graph, models connections instead: see graphs and shortest paths.
Frequently asked questions
Why does Python give different hashes for strings each run?
Python randomises string hashes on purpose in each run, to make certain attacks harder. Your own code should not depend on the numbers.
Is a hash table faster than a sorted list with binary search?
On average yes for single lookups, but a sorted list can also give ordered results, such as all names between B and D.
Get started
