[FIXED] How to calculate the average fill rate of a hash table?

Issue

I'm looking at a hash table implementation and it says that the table will grow by doubling in size when it's 75% full, which gives it an average fill rate of:

(75 + 75 / 2) / 2 = 56%.

How did the author arrive at this formula? If the table tripled in size, would the 2's become 3's?

Solution

(75 + 75 / 2) / 2 = 56%.

It's basically saying that when it comes times for resizing, the table will be 75% full (the first 75), but the prior resizing would have happened when the table was half as big, so at that time the number of elements would have been half as much as needed for this resize, so 75 / 2. Outside the parentheses, the trailing / 2 takes the average of these two load factors.

If the table tripled in size, then we'd have:

(75 + 75 / 3) / 2 = 50%.

That reflects the load factor after a resize being only 25% now, but we still have a trailing / 2 to get an average over that initial 25% load factor and the 75% load factor at which it will resize again.

Answered By - Tony Delroy

Answer Checked By - Cary Denson (PHPFixing Admin)