Hash Table Lookups

When we look up items from a hash table, we use a key to find its associated value. Let’s see how this works with our Quickasaurus example hash table.

Suppose we want to look up the value associated with the key "bad". In our code, we’d say:

To find the value associated with "bad", the computer executes two simple steps:

1. The computer hashes the key we’re looking up: BAD = 2 * 1 * 4 = 8.
2. Since the result is 8, the computer looks inside cell 8 and returns the value stored there. In this case, that is the string "evil".

Let’s take a step back and look at the big picture here. In a hash table, the placement of each value is determined by its key; that is, by hashing the key itself, we compute the index number where the key’s associated value should be placed.

Because the key determines the placement of the value, we use this principle to make lookups a cinch. When we have any key and want to find its value, the key itself tells us where the value will be found. Just as we hashed the key to insert the value in the appropriate cell, we can hash the key again to find where we previously put that value.

It now becomes clear why looking up a value in a hash table is typically O(1): it’s a process that takes a constant amount of time. The computer hashes the key, turns it into a number, and jumps to the index with that number to retrieve the value stored there.

We can now understand why a hash table would yield faster lookups for our restaurant menu than an array. With an array, when we look up the price of a menu item, we would have to search through each cell until we find it. For an unordered array, this would take up to O(N), and for an ordered array, this would take up to O(log N). Using a hash table, however, we can now use the actual menu items as keys, allowing us to do a hash table lookup of O(1). And that’s the beauty of a hash table.

One-Directional Lookups

It’s important to point out that the ability to find any value within the hash table in a single step only works if we know the value’s key. If we tried to find a particular value without knowing its key, we’d still have to resort to searching each and every key-value pair within the hash table, which is O(N).

Similarly, we can only do O(1) lookups when using a key to find the value. If, on the other hand, we want to use a value to find its associated key, we can’t take advantage of the hash table’s fast lookup ability.

This is because the whole premise of the hash table is that the key determines the value’s location. But this premise only works in one direction: we use the key to find the value. The value does not determine the key’s location, so we have no way to easily find any key without combing through all of them.

Come to think of it, where are the keys stored? In the previous diagrams, we only saw how the values are stored in the hash table.

While this detail may vary from language to language, some languages store the keys next to the values themselves. This is useful in case of collisions, which I’ll discuss in the next section.

In any case, another aspect of the hash table’s one-directional nature is worth noting. Each key can exist only once in the hash table, but there can be multiple instances of a value.

If we think about the menu example from the beginning of this chapter, we can’t have the hamburger listed twice (nor would we want to, as it only has one price). However, we could have multiple foods that cost $2.50.

In many languages, if we try to store a key-value pair where the key already exists, it simply overwrites the old value while keeping the same key.