Beginning Algorithms

Chapter 13. Maps

Maps—also known as dictionaries, lookup tables, and associative arrays—are especially useful for building indexes.

This chapter discusses the following topics:

• The basic operations of a map

• A map implementation designed for small amounts of data, the list map

• Another implementation that efficiently manages large amounts of unordered data, the hash map

• A third type of map that has predictable iteration order, the tree map.

Understanding Maps

A map holds an association between a key and a value. Each key within a map is unique and enables you to quickly set and retrieve an associated value. This can be useful for creating lookup tables in which a code is entered and a description is obtained or for building indexes that enable you to locate information—for example, a person's record based on some pertinent details. Figure 13-1 shows a map in which the people's names represent the keys, and the values are database record numbers.

One thing to remember about maps is that while the keys in a map are guaranteed to be unique, no such promise is made about the values. This can be useful, however. Imagine an index that maps telephone numbers to database records so that you can easily find someone using his or her phone number. It's conceivable that a person might have more than one telephone number—home, business, cellular, and so on. In this case, multiple keys might map to the same record number. In Figure 13-2, you can see that Leonardo da Vinci can be contacted at two numbers: ...