Load Factor and Rehashing

The load factor measures how full a hash table is. If the load factor is exceeded, increase the hash-table size and reload the entries into a new larger hash table. This is called rehashing. Load factor l (lambda) measures how full a hash table is. It is the ratio of the number of
elements to the size of the hash table, that is, l = n / N, where n denotes the number of elements and N the number of locations in the hash table.

Note that l is zero if the hash table is empty. For the open addressing scheme, l is between 0 and 1; l is 1 if the hash table is full. For the separate chaining scheme, l can be any value.

As l increases, the probability of a collision increases. Studies show that you should maintain the load factor under 0.5 for the open addressing scheme and under 0.9 for the separate chaining scheme.

Keeping the load factor under a certain threshold is important for the performance of hashing. In the implementation of the java.util.HashMap class in the Java API, the threshold 0.75 is used. Whenever the load factor exceeds the threshold, you need to increase the hashtable size and rehash all the entries in the map into a new larger hash table. Notice that you need to change the hash functions, since the hash-table size has been changed. To reduce the likelihood of rehashing, since it is costly, you should at least double the hash-table size. Even with periodic rehashing, hashing is an efficient implementation for map.