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
- open addressing — A way of resolving hash collisions in which all entries live in one array and a colliding key probes forward to another free slot.
- collision — Two different keys producing the same hash, or the same slot in a hash table.
- load factor — The number of items stored in a hash table divided by the number of slots, a measure of how full it is.
- hash table — A data structure that stores key-value pairs in an array and uses a hash of each key to jump almost directly to its slot.
Taught in
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers
- Sorting In Real Systems: Stability, Keys And External Sort — Algorithms & Data Structures for Working Engineers