Hash Tables
DSA · Hashing
Theory
A hash table stores key-value pairs. A hash function converts each key into an index in an internal array, so insert, lookup and delete take O(1) on average. Different keys can map to the same index (a collision); implementations resolve this with chaining or probing, and resize the array when it gets too full. Python dict is a highly optimised hash table.
Why we use it
Hash tables give near-constant-time lookups, which turns many O(n²) solutions into O(n).
When to use it
Use them for counting, caching, indexing records by ID, grouping, de-duplication and the classic two-sum pattern.
How it works
- key
- hash(key) -> integer
- index = hash % table_size
- Bucket already has other keys? Yes: Collision: chain or probe. No: Store (key, value).
- Lookup repeats the same hash: O(1) average
Syntax
d = {}
d[key] = value insert O(1) avg
d.get(key, default) lookup O(1) avg
del d[key] delete O(1) avg
key in d membership O(1) avg
Worst case (all collisions): O(n)Example
words = "to be or not to be that is the question".split()
counts = {}
for w in words:
counts[w] = counts.get(w, 0) + 1
print("Word counts:", counts)
def two_sum(nums, target):
seen = {}
for i, n in enumerate(nums):
if target - n in seen:
return [seen[target - n], i]
seen[n] = i
return None
print("Two sum indexes:", two_sum([2, 7, 11, 15], 9))Key points
- Average O(1) insert, lookup and delete
- Keys must be hashable (immutable)
- Collisions handled by chaining or probing
- Python dict and set are hash tables