Load Factor and Resizing

The load factor of a hash table is the number of keys it holds divided by its number of buckets, and a table keeps it low by growing: once the load factor passes a threshold, the table doubles its buckets and places every key again. This card covers the load factor, the growth, and why every key's bucket has to be worked out again.

In a table that chains, the load factor is the average length of a list, so it sets the expected cost of a lookup. Java's HashMap grows once its load factor passes 0.75. A run put the keys 5, 13, 21, 37, 8, 30 and 42 into eight buckets with the same rule. The load factor rose by 0.125 with each key and reached 0.75 at the sixth. The seventh took it to 0.875, so the table grew to 16 buckets, and its load factor fell to 7 / 16 = 0.4375.

Growing cannot leave each key where it was, because a key's bucket is its hash code mod the number of buckets, and that number has just changed. The run worked out each key's bucket at both sizes:

Four of the seven keys moved, and the list of four in bucket 5 split: 13 went to bucket 13 while 5, 21 and 37 stayed. When the capacity doubles, each key either stays or moves to its old bucket plus the old capacity, so 13 went to 5 + 8 and 30 to 6 + 8.

Placing every key again is called rehashing, and it costs O(n) for n keys. Insertion still costs O(1) amortised, meaning averaged over many inserts. In the first 100 inserts the run grew the table at the 7th, 13th, 25th, 49th and 97th key. Each growth comes after about twice as many keys as the one before, so all the rehashing together moved 191 keys, under two for each key inserted.

The threshold is a trade. A lower one keeps lists shorter and leaves more buckets empty; a higher one saves memory and lengthens every lookup.