Unit 06
Hashing
What if you could jump straight to a value without searching or traversing anything? A hash function turns a key into an address, getting you close to that ideal.
// the hash function decides exactly where a key lives
What it is
A hash table stores key-value pairs. A hash function converts each key into a number (an index), which tells the table exactly which "bucket" to store the value in. Looking up a key later just means running it through the same hash function and going straight to that bucket — no scanning required.
Why it's useful
- Near-instant lookup, insert, and delete on average, regardless of how many items are stored.
- Natural fit for "lookup by name" problems — dictionaries, caches, counting word frequencies, checking for duplicates.
Where it struggles
- Collisions. Two different keys can hash to the same bucket. Handling this (via chaining or open addressing) adds complexity and, in bad cases, slows things down.
- No natural ordering. Hash tables don't preserve any particular order of keys, unlike a sorted array or BST.
- Memory overhead from needing extra space to keep collisions infrequent.
Time complexity
| Operation | Average | Worst case |
|---|---|---|
| Insert | O(1) | O(n) |
| Lookup | O(1) | O(n) |
| Delete | O(1) | O(n) |