Hash Tables
Hash functions, collisions, and average O(1) lookup.
What you will learn
- Explain hash → bucket
- Use dict/HashMap
- Know collision strategies exist
A hash table maps keys to buckets via a hash function. Average lookup is O(1); worst case O(n) when many keys collide.
python
cache = {}
cache["user:42"] = {"name": "Amar"}
print(cache.get("user:42"))Try it yourself
Implement a function that returns the first duplicate character in a string using a set.