Java Reference
In-Depth Information
Note:
Double hashing
•
Resolves a collision during hashing by examining locations in the hash table at the
original hash index plus an increment defined by a second hash function. The second
hash function should
■
Differ from the first hash function
Depend on the search key
■
Have a nonzero value
■
•
Reaches every location in the hash table, if the size of the table is a prime number
•
Avoids both primary clustering and secondary clustering
Question 5
What size hash table should you use with double hashing when the hash func-
tions are
h
1
(
key
)
=
key
modulo 13
h
2
(
key
)
=
7
-
key
modulo 7
Why?
Question 6
What probe sequence is defined by the hash functions given in the previous ques-
tion when the search key is 16?
The previous three open addressing schemes for collision resolution assume that each table location
is in one of three states: occupied, empty, or available. Recall that only empty locations contain
null
. Frequent additions and removals can cause every location in the hash table to reference either
a current entry or a former entry. That is, a hash table might have no location that contains
null
,
regardless of how many or how few entries are actually in the dictionary. If this happens, our
approach to searching a probe sequence will not work. Instead, every unsuccessful search can end
only after considering every location in the hash table. Also, detecting the end of the search will be
somewhat more involved and costly than simply looking for
null
.
You should safeguard your implementation against this failure. Increasing the size of the
hash table (see Segment 22.7 in the next chapter) can correct the problem, if you act in time. Sep-
arate chaining—which we consider next—does not have this problem.
Note:
Open addressing can be simplified when an application does not require removals.
Such is the case, for example, when a compiler builds a symbol table. It can use a dictionary
that does not permit removals. Locations in the hash table will either reference a dictionary
entry or contain
null
. Defining the three states given in Segment 21.16 is not needed.
Project 1 at the end of this chapter asks you to develop this implementation.
21.23
A second general approach to collision resolution alters the structure of the hash table so that each
location can represent more than one value. Such a location is called a
bucket
. Anytime a new
search key maps into a particular location, you simply place the key and its associated value in the
