geeksforgeeks hashing
geeksforgeeks Hashing | Set 1 (Introduction)
geeksforgeeks Hashing | Set 2 (Separate Chaining)
geeksforgeeks Hashing | Set 3 (Open Addressing)
geeksforgeeks Double Hashing
geeksforgeeks Load Factor and Rehashing
Rehashing:
As the name suggests, rehashing means hashing again. Basically, when the load factor increases to more than its pre-defined value (default value of load factor is 0.75), the complexity increases. So to overcome this, the size of the array is increased (doubled) and all the values are hashed again and stored in the new double sized array to maintain a low load factor and low complexity.
How Rehashing is done?
Rehashing can be done as follows:
1、For each addition of a new entry to the map, check the load factor.
2、If it’s greater than its pre-defined value (or default value of 0.75 if not given), then Rehash.
3、For Rehash, make a new array of double the previous size and make it the new bucketarray
.
4、Then traverse to each element in the old bucketArray
and call the insert()
for each so as to insert it into the new larger bucket array.