Rehash
- Understand rehashing well enough to implement it.
The probability of a collision is proportional to how full the table is.
When the hash table becomes sufficiently full, a larger table should be allocated, and the entries should be reinserted.
Unlike growing a dynamic array, simply copying the values from the original collection to the new one will not work with a hash table.
Why not?
The table size affects the index returned by the hashing procedure. For example, suppose a key was inserted at index $x$ in the smaller table. In that case, it will not necessarily be mapped to the same index in a larger table. Therefore, the search operation may not find an element in the table after the table is resized.
The solution is rehashing:
-
Allocate a new hash table (e.g. with at least twice the capacity of the original).
-
Reinsert each old table entry (that has not been deleted) into the new hash table.