Java Reference
In-Depth Information
21.15
Retrievals.
Now that we've used linear probing to resolve collisions while adding our four entries,
how do we retrieve the street address associated with the last search key we added, 555-2072? That
is, if the statement
String streetAddress = addressBook.getValue("555-2072");
is executed, what will
getValue
do? Since
getHashIndex("555-2072")
is 52,
getValue
will
search consecutive locations in the array beginning at
hashTable[52]
until it finds the street
address associated with the search key 555-2072. But wait! How can we tell which street address is
the right one? We can't, unless we package a search key with its value. Segment 20.2 of Chapter 20
provided a class
Entry
that we could use for this purpose. Figure 21-4 shows the hash table given in
Figure 21-3 after we make this revision.
FIGURE 21-4
A revision of the hash table shown in Figure 21-3 when linear
probing resolves collisions; each entry contains a search key
and its associated value
h
(555-1214)
h
(555-8132)
h
(555-4294)
h
(555-2072)
52
555-1214 150 Main Street
53
555-8132 75 Center Court
54
555-4294 205 Ocean Road
55
555-2072 82 Campus Way
56
null
Hash table
Now the search for 555-2072 can follow the same probe sequence that was used to add this
search key and its value to the hash table. This fact will be useful later when we assess the effi-
ciency of hashing.
Note:
A successful search for an entry that corresponds to a given search key follows the
same probe sequence used to add the entry to the hash table.
What happens if the search key is not in the hash table? The search of the probe sequence
would encounter a
null
location, indicating an unsuccessful search. But before we can reach this
conclusion, we need to know what the
remove
method does, because it has the potential to
adversely affect subsequent retrievals.
