DSA · Chapter 11 of 40
Hashing and Hash Tables
A hash table stores key-value pairs and uses a hash function to convert a key into an index, giving average O(1) insert, lookup and delete. Python dictionaries and sets are hash tables.
Collisions happen when two keys hash to the same slot; they are resolved by chaining (a list per slot) or open addressing (probing for the next free slot).
Why O(1) is only average
If many keys collide, operations degrade toward O(n). Good hash functions and resizing keep the load factor low.
Sets vs maps
Use a set when you only need membership, and a map when you need an associated value such as an index or count.
Example 1 (python)
counts = {}
for ch in 'banana':
counts[ch] = counts.get(ch, 0) + 1
print(counts)Output
{'b': 1, 'a': 3, 'n': 2}Frequency counting is the most common hash-map pattern.
Example 2 (python)
seen = set()
for n in [1, 2, 2, 3]:
if n in seen:
print('duplicate', n)
break
seen.add(n)Output
duplicate 2A set detects duplicates in a single O(n) pass.
Key points
- Hash tables give average O(1) insert, lookup and delete.
- Collisions are handled by chaining or open addressing.
- Worst case degrades to O(n).
- Hash keys must be immutable and hashable.
💡 Note: When a problem needs 'have I seen this before?', reach for a set or dict.