Implementing Resize of a Hash Table
Resizing a Hash Table is important to maintain consistent performance and efficiency, but how do we actually implement it?
Resize is all about
allocating a new array of the desired size
insert existing keys in this new array
delete the old array
But a few granular details are specific to the type of hash table.
Resizing a Chained Hash Table
Resizing a table happens when the load factor hits a threshold. To implement an efficient resize, a Hash Table that uses chaining needs to keep track of
number of keys
total number of slots
This would help us avoid reevaluation, and we can instantly compute the load factor.
Resize during insert
While we are inserting a key in the Hash Table, we keep on checking the load factor. If it breaches the threshold, we trigger the resize.
insert_key(k, table) { ------ LF = count_keys / total_slots; if (LF >= 0.5) { resize(table, total_slots * 2) } }
Shrinking during delete
While we delete a key from the Hash Table, we check the load factor. If it breaches the threshold, we trigger the shrink. The pseudocode is fairly similar to the above one.
Two ways to implement resize
Chained Hashing is implemented using Linked List and there are two ways to resize
we iterate through the keys and re-insert them into the new array
we iterate through the keys and just adjust the pointers of the nodes, instead of re-allocating the new set of nodes.
Resizing a Hash Table with Open Addressing
In open addressing, we always soft delete so that we can reach the elements placed further in the collision chain. To handle this gracefully, we need two counters at the hash table
Key Counter: number of active keys in the table
Used Counter: number of used slots in the table
For open addressing, the load factor will be counted as the used counter divided by the total slots. The deleted keys also affect the performance as we have to go past them looking for the keys.
Hence, the Key Counter will increase and decrease upon every insert and delete, while the used counter would increase upon insert but would reduce only when we do a resize.
Resize during insert
While we are inserting a key in the Hash Table, we check the load factor. If it breaches the threshold, we trigger the resize. Resize operation would skip the deleted keys and re-insert only the active keys.
Shrinking during delete
The shrinking of the hash table will be triggered when the number of active keys falls beyond the threshold, and hence here our load factor for this operation would be active keys / total_slots.
Similar to the insert phase, we would skip the deleted keys and re-insert only the active keys in the new array. The key counter and the user counters are adjusted accordingly.
Here's the video of my explaining this in-depth 👇 do check it out
Thank you so much for reading 🖖 If you found this helpful, do spread the word about it on social media; it would mean the world to me.
If you liked this short essay, you might also like my courses on