Java Reference
In-Depth Information
Among open addressing schemes, double hashing is a good choice. It uses fewer comparisons
than linear probing. Additionally, its probe sequence can reach the entire table, whereas quadratic
probing cannot.
FIGURE 22-4
The average number of comparisons required by a search of the
hash table versus the load factor
for four collision resolution
techniques when the search is (a) successful; (b) unsuccessful
λ
(a) Successful search
(b) Unsuccessful search
18
16
18
16
14
14
12
12
10
10
8
8
6
6
4
4
2
0
0
2
0
0.2
0.4
0.6
0.8
1.0
0
0.2
0.4
0.6
0.8
1.0
Linear probing
Quadratic probing, double hashing
Separate chaining
The efficiency of separate chaining makes it a desirable method for resolving collisions that occur
during hashing. Because its implementation is relatively straightforward, we leave it to you to
implement. Instead, we will implement the linear probing method of open addressing. Most of this
dictionary implementation is independent of the particular open addressing technique that you use.
Adapting it to use quadratic probing or double hashing involves few changes.
VideoNote
Implementing a dictionary
Our hash table will be like the array in Figure 20-1a of Chapter 20 that we used to implement the dic-
tionary. Each array location can reference an object that contains a search key and an associated value.
The class
TableEntry
of these objects is similar to the class
Entry
that you saw in Segment 20.2.
However, with open addressing, each location in the hash table is in one of three states: occu-
pied, empty, or available. (See Segment 21.16 of the previous chapter.) An empty location contains
null
. Rather than altering the structure of the hash table to indicate the other states, we make the
entry objects indicate whether they are currently in the table or have been removed from it. Hence,
