AlgoScope

Separate Chaining

Each bucket holds a chain of colliding entries. A lookup hashes once and compares keys along that chain.

Data structures, data structure, intermediate
Key 7 appended to bucket 2.0123412:57:3
Key 7 appended to bucket 2.0123412:57:3

Hash Map: Filling buckets, with collisions

Step, step 5 of 12

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)

Taught by the same lesson

Hash Map covers these too, in the same run.