Java Reference
In-Depth Information
Each of these examples involves a kind of dictionary. This chapter describes and uses an
abstract data type that generalizes our everyday notion of a dictionary. Subsequent chapters will
examine implementations of this ADT.
The previous examples—finding a word's definition, a friend's address, or someone's tele-
phone number—are all examples of searching a dictionary. The previous chapter examined how to
search a list. You will see that a dictionary provides a more powerful way to organize data that will
be searched.
19.1
The ADT
dictionary
—also called a
map
,
table
,or
associative array
—contains entries that each
have two parts:
A keyword—usually called a
search key
—such as an English word or a person's name
●
A value—such as a definition, an address, or a telephone number—associated with that key
●
The search key enables you to locate the desired entry.
Figure 19-1 illustrates an everyday English dictionary. Each entry has a word as the search key
and the word's definition as the value associated with the key. In general, the search keys and val-
ues in an ADT dictionary are objects, as shown in Figure 19-2. Each search key is paired with a
corresponding value.
The ADT dictionary organizes and identifies its entries by their search keys, rather than by
another criterion such as position. Thus, you can retrieve or remove an entry from a dictionary
given only the entry's search key. The fact that every entry in a dictionary has a search key distin-
guishes the dictionary from other ADTs such as a list. Although you certainly could put an entry
that has a search key in a list, a list's data is organized by position, not by search key.
VideoNote
The ADT dictionary
FIGURE 19-1
An English dictionary
computer
A device for the
processing and storage of
information.