[Data Structure] Hash Table - 4 | Hash Table Resizing

Resize Operation

A hash table resize opeartion increases the number of buckets, while preserving all existing items.

A hash table with N buckets is commonly resized to the next prime number ≥ N * 2. 

A new array is allocated, and all items from the old array are re-insrted into the new array, making the resize opeartion's time complexity O(N). 

 

 

Let's take a look into an example of hash table resizing. 

 

Suppose the hash table below is resized. The hash function used both before and after resizing is: hash(key) = key % N, where N is the table size.

 

1) What is the most likely allocated size for the resized hash table?

→ Current size = 7 → Next prime = 17

2) How many elements are in the hash table after resizing? 

→ Currently existing elements in the table should be copied to the resized table, so there are same number of elements.  = 4

3) At what index does 99 reside in the resized table? 

→ New size = 17 → 99 % 17 = 14 

---

 

But when do we actually have to resize a hash table? 

 

Resize Operation

A hash table's load factor is the number of items in the hash table divided by the number of buckets. 

Ex. A hash table with 18 items and 31 buckets has a load factor of 18/31 = 0.58. 

This load factor may be used to decide when to resize the hash table. 

 

An implementation may choose to resize the hash table when one or more of the following values exceeds a certain thrshold:

• Load factor
• When using open-addressing, the number of collisions during an insertion
• When using chaining, the size of bucket's linked-list 

Resizing when a chaining bucket is too large

Resizing when the load function ≥ 0.6

Resizing when an insertion causes more than N / 3 collisions