O'Reilly logo

Beginning Algorithms by James Ross, Simon Harris

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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: ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required