5.5. Hash Tables¶

If you have used a Python dictionary, then you have used a hash table. A hash table is a collection of associated pairs of items where each pair consists of a key and a value. Hash tables are often called the more general term map because the associated hash function “maps” the key to the value. Nevertheless, it is better to use the more precise term, hash table because other kinds of maps are sometimes implemented with a different underlying data structure.

Each hash table has a hash function which given the key as input to the hash function returns the location of the associated value as the output. This makes look up fast.

In Python, the dictionary data type represents the implementation of the hash table. In C++, the unordered_map implements the hash table, and the <unordered_map> library must be included as follows:

#include <unordered_map>

The syntax for hash table access is much like we might expect except that instead of using the index of the item for look-up, we use the key. In both Python and C++, hash tables can be initialized with key-value pairs and key-value pairs can also be added later as we see in the following example. In C++, the keyword first is used for the key, and second is used for the associated value.

It is important to note that hash tables are organized by the location given by the hash function rather than being in any particular order with respect to the keys. This makes look-up extremely fast. Hence, although it is possible to iterate through a hash table in both C++ and Python, it is an odd thing to do because the data is not typically stored sequentially. Iterators of an unordered_map are implemented using pointers to point to elements of the value type as we see in the following example.

Hash Tables have both methods and operators. Table 7 describes them, and the session shows them in action.