The Self-Taught Computer Scientist

value pair consists of two pieces of data mapped together: a key and a value. The key is the piece 
of data you use to retrieve the value. The value is the piece of data you use the key to retrieve. As 
a Python programmer, you should already be familiar with key- value pairs because you’ve been using 
Python dictionaries.
There are many different implementations of an associative array, but in this chapter, you will learn 
about hash tables. A hash table is a linear data structure that stores key- value pairs with unique keys, 
which means you cannot store duplicate keys in a hash table. The difference between an associative 
array and a hash table is that an associative array is an abstract data type, whereas a hash table is a data 
structure and therefore is an implementation of an associative array. Python implements dictionaries 
using hash tables.
When you are programming, the system you are running your program from stores the data in a 
hash table inside an array data structure. When you add a piece of data to your hash table, your com-
puter uses a hash function to determine where in the array to store it. A hash function is code that 
takes a key as input and outputs an integer you can use to map a hash table key to an array index 
your computer uses to store the value. The index a hash function produces is called a hash value. 
You can store any type of data as a value in a hash table, but the key must be something your hash 
function can turn into an index, such as an integer or a string. This process makes retrieving values 
from a hash table incredibly efficient, which you will learn more about later.
Let’s quickly review how Python dictionaries work. You store key- value pairs in a Python dictio-
nary. Keys cannot be duplicates, but values can be. Here is an example of storing a key- value pair in 
a Python dictionary:

---