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

Taught in

References