Hash Tables

Most programming languages include a data structure called a hash table, and it has an amazing superpower: fast reading. Note that hash tables are called by different names in various programming languages. In Python they’re called dictionaries, and other languages call them hashes, maps, hash maps, dictionaries, or associative arrays. We’ll refer to them as hash tables, since that’s a common universal way to refer to this data structure.

Here’s an example of the menu as implemented with a hash table:

A hash table is a list of paired values. The first item in each pair is called the key, and the second item is called the value. In a hash table, the key and value have some significant association with one another. In this example, the string, "french fries" is the key, and 0.75 is the value. They are paired together to indicate that french fries cost 75 cents.

In Python, you can look up a key’s value using this syntax:

This would return the value 0.75.

Alternatively, you can look up a key’s value this way:

However, this latter approach triggers an error if the key doesn’t exist in the hash table. Therefore, we’ll use the former approach, which simply returns None if the key isn’t found.

Looking up a value in a hash table has an efficiency of O(1) on average, as it usually takes just one step. Let’s see why.