Java Reference
In-Depth Information
21.16
Removals.
Suppose that after the four additions illustrated in Figure 21-4, we removed two entries
by executing the following code:
addressBook.remove("555-8132");
addressBook.remove("555-4294");
The simplest way to remove an entry from an array location is to place
null
in the location. Figure 21-5
shows the hash table after
remove
places
null
into
hashTable[53]
and
hashTable[54]
. But now an
attempt to find the search key 555-2072 will terminate unsuccessfully at
hashTable[53]
. Although a
location in the hash table that was never used should end a search, a location that had been used and is
now available again for use should not.
FIGURE 21-5
A hash table if
remove
used
null
to remove entries
h
(555-1214)
555-1214 150 Main Street
52
h
(555-2072)
53
null
54
null
55
555-2072 82 Campus Way
56
null
Hash table
Thus, we need to distinguish among three kinds of locations in the hash table:
•
Occupied—the location references an entry in the dictionary
•
Empty—the location contains
null
and always has
•
Available—the location's entry was removed from the dictionary
Accordingly, the method
remove
should not place
null
into the hash table, but instead should
encode the location as available. The search during a retrieval should then continue if it encounters
an available location and should stop only if it is successful or reaches a
null
location. A search
during a removal behaves in the same way.
Question 4
Suggest ways to implement the three states of a location in a hash table. Should
this state be a responsibility of the location or of the dictionary entry that it references?
