Rehash
The likelihood 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 array to the new array, will not work with hash table.
Why not?
The table size affects the index returned by the hashing procedure. If a key was inserted at index $x$ in the smaller table, it will not necessarily be mapped to the same index in a larger table. Therefore, search operation may not be able to find an element that exist in the table after the table is resized.
The solution is to
- Allocate a new hash table (with twice the capacity of the original)
- Reinsert each old table entry (that has not been deleted) into the new hash table
The process described above is called rehashing.