Java Reference
In-Depth Information
return
value;
}
// end getValue
private
void
setValue(T newValue)
{
value = newValue;
}
// end setValue
}
// end Entry
}
// end ArrayDictionary
Notice that the inner class
Entry
has no method
setKey
to set or change the search key. Even
though
setValue
can be useful in the implementation of
add
, you never need to change the search
key. Without
setKey
, a default constructor would be useless, so none is defined.
Note:
Compiler warning
The constructor for
ArrayDictionary
, as shown in Listing 20-1, allocates memory for the
array
dictionary
as follows:
dictionary =
new
Entry[initialCapacity];
The compiler sees an array whose elements have type
Entry
assigned to an array whose ele-
ments are of type
Entry<K,
V>
. It therefore warns us of an unchecked conversion. An attempt to
cast the new array to
Entry<K,
V>[]
results in a similar warning. In either event, all should be
well despite the compiler's concern. Thus, we suppress the warning as we have done in the past.
20.3
Some private methods.
One problem with array-based implementations of an ADT is the finite
size of the array. To avoid a full dictionary, we double the array's size as necessary, just as we did in
earlier chapters. We will use a private method as we did then. Its specification is as follows:
// Doubles the size of the array of entries if it is full.
private void
ensureCapacity()
Adding, removing, or retrieving an entry requires a sequential search, since the search keys are
not sorted. A sequential search must look at all the search keys in the array to conclude that an entry
is not present in the dictionary. Implementing this search as the following private method will sim-
plify the definitions of these three dictionary operations:
// Returns the index of the entry that contains key or
// returns numberOfEntries if no such entry exists.
private int
locateIndex(K key)
20.4
Adding an entry.
Another potential problem with array-based implementations is the shifting of
array entries that often occurs. When a dictionary's search keys are unsorted, however, we can add
or remove an entry without shifting other entries. When adding a new key-value entry, we can
insert it after the last entry in the array and not move any other entry, as Figure 20-2 shows. In this
case,
add
returns
null
. However, if the search key was in the dictionary already, we replace its
corresponding value with the new value and return the original value. The following algorithm
performs these steps:
Algorithm
add(key, value)
//
Adds a new key-value entry to the dictionary and returns
null
. If
key
already exists
//
in the dictionary, returns the corresponding value and replaces it with
value
.