Java Reference
In-Depth Information
20.1
The ability to resize an array, as introduced in Segment 2.32 of Chapter 2, means that an array can
provide as much storage as necessary for the entries in a dictionary. Remember that each entry con-
sists of two parts—a search key and a value. You can encapsulate the two parts into an object, as
Figure 20-1a illustrates. With this approach, you define a class
Entry
to represent the entries. A
second, less attractive approach uses two arrays, as shown in Figure 20-1b. One array represents
the search keys and a second,
parallel array
represents the corresponding values. We will discuss
the first approach and leave the exploration of the second as an exercise. At that time, you will see
that parallel arrays can be awkward to manage.
VideoNote
Array-based dictionaries
FIGURE 20-1
Two possible ways to use arrays to represent the entries in a dictionary:
(a) an array of objects that encapsulate each search key and corresponding
value; (b) parallel arrays of search keys and values
(a)
(b)
Array of entries
Array of search keys
Search key
Instance of
Entry
Parallel array of values
Search key
Value
Value
Question 1
Figure 20-1 shows two ways to represent an array-based dictionary. How do
the memory requirements for the two representations compare?
Beginning the implementation.
Our implementation uses one array, as pictured in Figure 20-1a, to rep-
resent the dictionary. Each entry in the dictionary, and therefore the array, is an instance of a class
Entry
that we must define. We can make this class either public, part of a package, or private and internal to the
dictionary class. We chose the latter approach in defining the private class
Entry
shown in Listing 20-1.
The outer class
ArrayDictionary
begins with its data fields and constructors stated in terms of
type parameters
K
and
V
. These parameters represent the data types of the search keys and their
associated values, respectively.
LISTING 20-1
The class
ArrayDictionary
and its private inner class
Entry
import
java.util.Arrays;
import
java.util.Iterator;
import
java.util.NoSuchElementException;
