A Common-Sense Guide to Data Structures and Algorithms

The Great Balancing Act

Ultimately, a hash table’s efficiency depends on three factors:

• How much data we’re storing in the hash table
• How many cells are available in the hash table
• Which hash function we’re using

It makes sense why the first two factors are important. If you have a lot of data to store in only a few cells, there will be many collisions and the hash table will lose its efficiency. Let’s explore, however, why the hash function itself is important for efficiency.

Let’s say that we’re using a hash function that always produces a value that falls in the range between 1 and 9 inclusive. An example of this is a hash function that converts letters into their corresponding numbers, and keeps adding the resulting digits together until it ...