Rehashing process in hashmap or hashtable
algorithm, hash, hashmap, hashtable, java
Solution
The maximum threshold in the question is called the load factor.
It is advisable to have a load factor of around 0.75. Load factor is defined as (m/n) where n is the total size of the hash table and m is the preferred number of entries which can be inserted before a increment in size of the underlying data structure is required.
Rehashing can be done in two cases:
When the present m'/n ratio increases beyond the load factor
M'/n ratio falls to a very low value say 0.1
In both the cases m' is the current number of entries. Also, both the cases demand the shifting of the present entries into a bigger or a smaller hash table.
In the question's context rehashing is the process of applying a hash function to the entries to move them to another hash table. It is possible to use the hash function which was used earlier or use a new function altogether.
Please note: Rehashing is also done when a collision occurs. (It's a way of handling collisions too.)
To add some more context and a detailed discussion please visit my blog Hashing Basics
Problem
How is the rehashing process done in a hashmap or hashtable when the size exceeds the maxthreshold value? Are all pairs just copied to a new array of buckets? EDIT: What happen to the elements in the same bucket (in linked list) after rehashing? I mean will they remain in same bucket after rehashing?