Hash Tables
O(1) average-case lookup
How Hash Tables Work
Hash tables use a hash function to convert keys into array indices. This enables O(1) average-case lookup, insertion, and deletion. The main challenge is handling collisions—when two keys hash to the same index.
Chaining
Each bucket holds a linked list of entries. Collisions just add to the chain. Simple but uses extra memory for pointers.
Linear Probing
On collision, check the next slot. Better cache locality but can suffer from clustering.
Load Factor: 0.00
Hash function:
hash(key) = sum(charCodes) % 7Chaining Visualization
0
empty
1
empty
2
empty
3
empty
4
empty
5
empty
6
empty
Complexity Analysis
| Operation | Average | Worst |
|---|---|---|
| Insert | O(1) | O(n) |
| Search | O(1) | O(n) |
| Delete | O(1) | O(n) |
Worst case occurs when all keys hash to the same bucket (all collisions). A good hash function and proper load factor management prevent this.