Hashing
dsa.fetehadin.com5.1 Hashing Basics
A hash function turns a key into an array index, so search is O(1) on average. Collisions, separate chaining, linear probing and the load factor.
| search / insert / delete, average | O(1) |
| search / insert / delete, worst (all keys collide) | O(n) |
| Space | O(M + n) |
- ✗With linear probing, stopping a search at a slot holding a different key. Only an empty slot means "not found".
- ✗Forgetting to wrap around with
% Mwhen probing. - ✗Claiming hashing is always O(1). The worst case is O(n).
- Hash function:
- Maps a key to an index of the hash table, e.g. h(k) = k mod M.
- Collision:
- Two different keys hashing to the same index.
- Separate chaining:
- Each table slot holds a list of all keys that hash there.
- Linear probing:
- On a collision, try the next slot (h + i) % M until an empty one.
- Load factor:
- α = n / M, how full a hash table is.