Python Tutorial
Hash Tables
Store key-value pairs with average O(1) lookup by turning keys into array indexes.
The Big Idea
A hash table stores data in an array of "buckets". A hash function converts a key into an integer, which (mod the array size) picks the bucket. Because the index is computed directly, insert, lookup, and delete average O(1) — dramatically faster than scanning a list.
Python's dict and set are hash tables. Understanding them explains why membership tests are so fast.
Python dict and set
phone = {"alice": 123, "bob": 456}
print(phone["alice"]) # 123 -> O(1) average
phone["carol"] = 789 # insert -> O(1) average
print("bob" in phone) # True -> O(1) average
del phone["bob"] # delete -> O(1) average
seen = set()
seen.add(10)
print(10 in seen) # True -> O(1) averageUse a set or dict for "have I seen this?" checks. Replacing x in a_list (O(n)) with x in a_set (O(1)) is one of the biggest easy speedups in Python.
Handling Collisions
Two keys can hash to the same bucket — a collision. The two standard fixes:
- Chaining: each bucket holds a small list of entries.
- Open addressing: probe for the next free slot (CPython uses a form of this).
As long as the table stays under-filled (a low "load factor"), collisions are rare and operations stay near O(1). Worst case, everything collides and it degrades to O(n).
Building a Hash Table from Scratch
class HashTable:
def __init__(self, size=8):
self.buckets = [[] for _ in range(size)]
def _index(self, key):
return hash(key) % len(self.buckets)
def put(self, key, value):
bucket = self.buckets[self._index(key)]
for pair in bucket:
if pair[0] == key: # update existing
pair[1] = value
return
bucket.append([key, value]) # chaining
def get(self, key):
bucket = self.buckets[self._index(key)]
for k, v in bucket:
if k == key:
return v
raise KeyError(key)
ht = HashTable()
ht.put("x", 1); ht.put("y", 2)
print(ht.get("x"), ht.get("y")) # 1 2Keys Must Be Hashable
Only immutable, hashable objects can be dict keys or set members: strings, numbers, tuples of immutables. Lists and dicts are mutable and unhashable.
ok = {("lat", "lon"): "point"} # tuple key works
# {["a"]: 1} -> TypeError: unhashable type: 'list'Everyday Patterns
from collections import Counter, defaultdict
words = ["a", "b", "a", "c", "b", "a"]
print(Counter(words)) # Counter({'a': 3, 'b': 2, 'c': 1})
groups = defaultdict(list)
for w in words:
groups[w[0]].append(w) # auto-creates the listBest Practices
- Use dict/set for fast lookups, counting, grouping, and deduplication.
- Keys must be immutable/hashable; use tuples for compound keys.
- Remember: average O(1), but no guaranteed ordering by hash (dicts do keep insertion order since Python 3.7).
- Reach for
Counteranddefaultdictbefore writing manual counting logic.
Try It Yourself
Exercise 1: Use a dict to count word frequency in a sentence.
Show solution
from collections import Counter
text = "the cat sat on the mat"
print(Counter(text.split()))
# Counter({'the': 2, 'cat': 1, ...})Exercise 2: Why can a list not be used as a dictionary key?
Show solution
Lists are mutable and therefore unhashable. Keys must be hashable (immutable) — use a tuple instead.
📘 Real-World Deep Dive
Knowing <strong>DSA Hash Tables (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.
Real-Life Scenario
An end-to-end usage of DSA Hash Tables that you'd actually see in a data pipeline or analytics notebook.
Real-Life Example
class HashTable:
def __init__(self, cap=8):
self.cap, self.buckets = cap, [[] for _ in range(cap)]
def _h(self, k): return hash(k) % self.cap
def put(self, k, v):
for i, (kk, vv) in enumerate(self.buckets[self._h(k)]):
if kk == k:
self.buckets[self._h(k)][i] = (k, v); return
self.buckets[self._h(k)].append((k, v))
def get(self, k):
for kk, vv in self.buckets[self._h(k)]:
if kk == k: return vv
raise KeyError(k)
h = HashTable()
h.put("alice", 30); h.put("bob", 25)
print(h.get("alice"), h.get("bob"))Expected Output
(see source)Common mistakes
- Off-by-one errors in binary-search: the standard idiom is
while lo <= hiwithmid = (lo + hi) // 2. - Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
- Comparison algorithms (
sorted(iterable)) are stable by default in Python — surprising for Java/C++ users. - Treating DSA Hash Tables as a black box without reading the docs — the API has subtle defaults that bite when you scale.
🚀 Performance & Best Practices
- Use
bisect.bisect_left/bisect_rightinstead of writing your own binary search. - Convert a sorted search into a tuple-access pattern with
numpy.searchsortedfor huge arrays. - Use
heapqfor priority queues instead of maintaining a sorted list manually. - When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.
🧪 Try It Yourself
- Reproduce the snippet on a representative slice of your own data.
- Profile the snippet with
cProfileortimeitand find the single biggest improvement. - Generalise the snippet into a small, reusable function you can drop into future projects.