Separate Chaining
Each bucket holds a chain of colliding entries. A lookup hashes once and compares keys along that chain.
Hash Map: Filling buckets, with collisions
Compared against 1 key, none equal: a collision, 7 shares bucket 2 with them and is appended to the chain. Load 2/5.
Cost
- Insert
- O(1)
- Search
- O(1 + load factor) expected
- Space
- O(n + buckets)
Before this
Related
Taught by the same lesson
Hash Map covers these too, in the same run.