Hashing
Hashing
Hash tables, maps, sets and how collisions are handled.
Hash Table
▶ viz
An array of buckets indexed by a hash of the key, giving expected O(1) insert, lookup, and delete.
O(1) search · O(n) space
Hash Map
▶ viz
A key → value store backed by a hash table with expected O(1) get, put, and delete.
O(1) search · O(n) space
Hash Set
▶ viz
A collection of unique keys backed by a hash table, with expected O(1) add, contains, and remove.
O(1) search · O(n) space
Collision Handling
▶ viz
Strategies for storing two keys whose hashes map to the same bucket without losing either.
O(1 + α) search · O(n + m) space
Separate Chaining
▶ viz
Collision resolution where each bucket holds a linked list (or small array) of all entries that hash to it.
O(1 + α) search · O(n + m) space
Open Addressing
▶ viz
Collision resolution where every entry lives in the bucket array itself and collisions are resolved by probing other slots.
O(1/(1-α)) search · O(m) space