2.7 Maps

Searching for data items based on unique key values is a very common application in computer science. An abstract data type that provides this type of search capability is often referred to as a map or dictionary since it maps a key to a corresponding value.

Consider the problem of a university registrar having to manage and process large volumes of data related to students. To keep track of the information or records of data, the registrar assigns a unique student identification number to each individual student as illustrated in Figure 2.7.1. Later, when the registrar needs to search for a student's information, the identification number is used. Using this keyed approach allows access to a specific student record. If the names were used to identify the records instead, then what happens when multiple students have the same name? Or, what happens if the name was entered incorrectly when the record was initially created?

Figure 2.7.1: Unique key/data pairs.

In this section, we define our own Map ADT and then provide an implementation using a list. In later chapters, we will implement and evaluate the map using a variety of data structures. We use the term map to distinguish our ADT from the dictionary provided by Python. The Python dictionary is implemented using a hash table, which requires the key objects to contain the __hash__ method for generating a hash code. This can limit the type of problems with which a dictionary can be used. We define our Map ADT with the minimum requirement that the keys are comparable, which will allow it to be used in a wider range of problems.

As you learned in Chapter 2, there may be multiple data structures and ways to organize the data that are suitable for implementing an abstract data type. Thus, it's not uncommon for language libraries to provide multiple implementations of an abstract data type, which allows the programmer to choose the best option for a given problem. Your ability to choose from among these various implementations will depend not only on your knowledge of the abstract data type itself, but also on understanding the pros and cons of the various implementations. We will explore the implementation details of Python's dictionary later in Chapter 11 when we discuss hash tables and the design of hash functions.

While Python provides its own version of the Map ADT by way of the dictionary container, it is still important to understand how the ADT works and some of the common ways in which it is implemented. Your experience in programming will likely not be limited to the Python language. At some point in the future, you may use one if not several other common programming languages. While some of these do provide a wide range of abstract data types as part of the language itself or included in their standard library, others, like C, do not. Thus, it's important that you know how to implement a dictionary or Map ADT if necessary, when one is not available as part of the language.

The Map ADT

The Map ADT provides a great example of an ADT that can be implemented using one of many different data structures. Our definition of the Map ADT, which is provided next, includes the minimum set of operations necessary for using and managing a map.

The Map ADT

A map is a container for storing a collection of data records in which each record is associated with a unique key. The key components must be comparable.

Map()

Creates a new empty map.
length()

Returns the number of key/value pairs in the map.
contains(key)

Returns a Boolean indicating whether the key is in the map.
add(key,

Adds a new key/value pair to the map if the key is not already in the map or replaces the data associated with the key if the key is in the map. Returns True if this is a new key and False if the value associated with the existing key is replaced.
remove(key)

Removes the key/value pair for the given key. The key must be in the map.
clear()

Clears or empties the map by removing all key/value pairs from the map.
valueOf(key)

Returns the data record associated with the given key. The key must be in the map.
iterator()

Returns an iterator that can be used to iterate over the keys in the map.

In the next section, we explore the use of the map operations with a basic example. Following which, we turn our attention to the physical implementation of the Map ADT.

2.6 Maintaining Ordered Data

Chapter 2. Data Structures

2.8 Map Operations