Definition
A hash table stores key-value pairs. It uses a hash function to turn each key into an index in an array, so that lookup, insert and delete take constant time on average. Python's dict and set are hash tables.
In simple words
Rather than reading every name in a register, a formula tells you exactly which page to open. Sometimes two names land on one page, which is a collision, and there's a method to handle that.
Why it matters
It's why dict lookups are so fast, whatever the size. It's also why keys must be immutable: a key that changes would get lost. And it's asked in nearly every coding interview.
How it works
| Operation | List | Dict or set |
|---|---|---|
| Find by value | O(n) | O(1) average |
| Insert | O(1) at the end | O(1) average |
| Delete by value | O(n) | O(1) average |
The maths
In code
class HashTable:
def __init__(self, size=8):
self.buckets = [[] for _ in range(size)]
def _index(self, key):
return sum(ord(c) for c in key) % len(self.buckets)
def put(self, key, value):
bucket = self.buckets[self._index(key)]
for pair in bucket:
if pair[0] == key:
pair[1] = value
return
bucket.append([key, value])
def get(self, key):
for k, v in self.buckets[self._index(key)]:
if k == key:
return v
raise KeyError(key)
table = HashTable()
table.put("Riya", 91)
table.put("Ayir", 80) # the same letters, so the same bucket: a collision
print(table.get("Riya"), table.get("Ayir"))
print("Bucket sizes:", [len(b) for b in table.buckets])
try:
{[1, 2]: "list as key"}
except TypeError as error:
print("Lists can't be keys:", error)Output
91 80 Bucket sizes: [0, 0, 0, 0, 0, 2, 0, 0] Lists can't be keys: cannot use 'list' as a dict key (unhashable type: 'list')
Common mistakes
- Using a list for many membership checks when a set would be far faster.
- Trying to use a list as a dict key. Keys must be hashable.
Check yourself
Summary
- Hash tables find items in O(1) on average.
- A hash function turns a key into an index.
- Keys must be immutable.
Finished reading?