The Self-Taught Computer Scientist

13Hash Tables

For self-educated scientists and thinkers such as Charles Darwin, Srinivasa Ramanujan, Leonardo da Vinci, Michael Faraday, myself, and many others, education is a relentless voyage of discovery. To us, education is an everlasting quest for knowledge and wisdom.

Abhijit Naskar

An associative array is an abstract data type that stores key-value pairs with unique keys. A key-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 computer uses a hash function to determine where in the array ...