Separate chaining

Store colliding keys together in the same bucket.

Remember: Same bucket, separate entries.

Example: 10 and 17 both go in bucket 3 when capacity is 7.

Time: Expected O(1) / key. Auxiliary space: O(m + n).

Formula: bucket = ((key % m) + m) % m

m is capacity. Prime capacities keep double-hash strides coprime to m. Duplicate keys use set semantics; expected O(1) assumes bounded load and suitable distribution. Worst case is linear. Deletion is not part of this lesson.

Complexities describe the underlying algorithm; tutorial snapshots and rendering can use additional resources.

The interactive workspace loads here when JavaScript is available. You can still browse the learning notes and links above without it.