Resizing a Hash Table

Let's review. A Hash table consists of an array (or Vector) of Lists, where each List contains a small number of key-value pairs. To add a new entry to a table, we calculate the hash code of the new key and add the entry to the corresponding List.

To look up a key, we hash it again and search the corresponding list. If the lengths of the lists are bounded then the search time is bounded.

So how do we keep the lists short? Well, one goal is to keep them as balanced as possible, so that there are no very long lists at the same time that others are empty. This is not easy to do perfectly---it depends on how well we chose the hash function---but we can usually do a pretty good job.

Even with perfect balance, the average list length grows linearly with the number of entries, and we have to put a stop to that.

The solution is to keep track of the average number of entries per list, which is called the load factor; if the load factor gets too high, we have to resize the table.

To resize, we create a new table, usually twice as big as the original, take all the entries out of the old one, hash them again, and put them in the new table. Usually we can get away with using the same hash function; we just use a different value for the modulus operator.