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 .
 
Search WWH ::




Custom Search