Java Reference
In-Depth Information
FIGURE 19-2
An instance of an ADT dictionary has search keys paired with
corresponding values
Search keys
Corresponding values
A dictionary object
Some dictionaries have distinct search keys, but others allow two or more entries to have the
same search key. For example, a dictionary of student records organized by student identification
numbers has distinct search keys, since those numbers are unique. On the other hand, an English-
language dictionary has duplicate search keys, since it often has several meanings for a word. For
example, my dictionary has three entries for the word “book”: One is a noun, one is a verb, and one
is an adjective.
Printed versions of a natural-language dictionary, a telephone directory, a library catalog, and a
thesaurus all have entries sorted by their search keys. These databases are dictionaries, but the ADT
dictionary does not require sorted entries. Some dictionaries do sort their entries by search key,
while other dictionaries have unsorted entries. Why do our examples of printed dictionaries sort
their entries? This makes it easier for the reader to find a particular entry. In contrast, if you
searched a computerized thesaurus for a word, you would not be aware of the order of its entries.
Nor would you care, as long as you could retrieve a particular entry. Thus, whether a dictionary has
sorted or unsorted search keys is more of an implementation detail than a necessary characteristic
of the dictionary. But remember that the details of any implementation affect the efficiencies of the
ADT operations in various ways.
19.2
The ADT dictionary has the same major operations—insert, delete, retrieve, search, and traverse—
that are common to most databases, even if a particular implementation sorts its entries or allows
duplicate search keys. In particular, these operations are
Add a new entry to the dictionary, given a search key and associated value
●
Remove an entry, given its associated search key
●
Retrieve the value associated with a given search key
●
See whether the dictionary contains a given search key
●
Traverse all the search keys in the dictionary
●
Traverse all the values in the dictionary
●
In addition, the ADT dictionary has the following basic operations that are often included in an ADT:
Detect whether a dictionary is empty
●
Get the number of entries in the dictionary
●
Remove all entries from the dictionary
●
