Rehashing (Hashing)

To keep hashing performance up, we need to keep the load factor $\alpha$ low. We use rehashing to do so:

• whenever the load factor becomes too large (e.g. greater than 0.5):
• create a new bucket approx. double the size of the old one
• iterate all elements in old bucket array and put them in the new bucket