Building a Thesaurus for Fun and Profit, but Mainly Profit

On nights and weekends, you’re single-handedly working on a stealth startup that will take over the world. It’s…a thesaurus app. But this isn’t any old thesaurus app—this is Quickasaurus. And you know that it will totally disrupt the billion-dollar thesaurus market. When a user looks up a word in Quickasaurus, it returns just one synonym, instead of every possible synonym, as old-fashioned thesaurus apps do.

Since every word has an associated synonym, this is a great use case for a hash table. After all, a hash table is a list of paired items. Let’s get started.

We can represent our thesaurus using a hash table:

Under the hood, a hash table stores its data in a bunch of cells in a row, similar to an array. Each cell has a corresponding number. For example:

(We left off index 0 since nothing would be stored there given our multiplication hash function.)

Let’s add our first entry into the hash table:

In code, our hash table now looks like this:

Let’s explore how the hash table stores this data.

First, the computer applies the hash function to the key. Again, we’ll be using the multiplication hash function described previously. So this would compute as:

BAD = 2 * 1 * 4 = 8

Since our key ("bad") hashes into 8, the computer places the value ("evil") into cell 8:

Now, let’s add another key-value pair:

Again, the computer hashes the key:

CAB = 3 * 1 * 2 = 6

Since the resulting value is 6, the computer stores the value ("taxi") inside cell 6.

Let’s add one more key-value pair:

To sum up what’s happening here: for every key-value pair, each value is stored at the index of the key, after the key has been hashed.

ACE hashes into 15, since ACE = 1 * 3 * 5 = 15, so "star" gets placed into cell 15:

In code, our hash table currently looks like this: