rehashing
Growing a hash table by allocating a larger array and re-inserting every existing key at its new slot.
In more detail
Because each key's slot depends on the table size, keys cannot simply be copied across; each must be hashed again. A single resize costs O(n), but doubling the size makes it rare enough that inserts stay O(1) amortised. It is the hash-table version of a dynamic array's grow-and-copy step.
Related terms
- load factor — The number of items stored in a hash table divided by the number of slots, a measure of how full it is.
- amortised analysis — Measuring the average cost per operation over a long sequence of operations, so rare expensive steps are spread across many cheap ones.
- dynamic array — An array that grows on demand by allocating a larger block and copying the existing items across when it runs out of room.
Taught in
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Arrays: Contiguous Memory And Constant-Time Access — Algorithms & Data Structures for Working Engineers