load factor
The number of items stored in a hash table divided by the number of slots, a measure of how full it is.
In more detail
As the load factor rises, collisions and probe lengths rise with it. Implementations resize, usually doubling the slots and rehashing every key, once the load factor crosses a threshold of roughly two thirds to three quarters. A Bloom filter's false-positive rate also rises with load.
Related terms
- rehashing — Growing a hash table by allocating a larger array and re-inserting every existing key at its new slot.
- 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.
- 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.
- chaining — A way of resolving hash collisions in which each slot holds a small list of all the key-value pairs that hashed there.
Taught in
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers