chaining

A way of resolving hash collisions in which each slot holds a small list of all the key-value pairs that hashed there.

In more detail

Lookup hashes the key to a slot and then scans that slot's short list. Deletion is simple, just remove the pair from the list, but every entry carries a pointer's worth of memory overhead. If all keys collide, one list holds everything and lookups become linear.

Example

The course's ChainMap class is a chaining hash map with eight bucket lists (unrelated to collections.ChainMap).

Related terms

Taught in

References