Java Reference
In-Depth Information
•
You can add new entries to a chain in sorted search-key order. Although sorted chains can improve search
time somewhat, they usually are unnecessary, as typical chains are short. You add new entries to an unsorted
chain either at the beginning, if duplicates are allowed, or at the end if not.
•
With separate chaining, you retrieve or remove an entry by mapping its search key into a table location. You
then search the bucket that the location references.
•
An iteration of the entire hash table will not be in sorted order even if separate chaining with sorted buckets
is used to resolve collisions.
E
XERCISES
1.
Define a
hashCode
method for the class
Name
, as given in Segment B.16 of Appendix B.
2.
Quadratic probing uses the following indices to define a probe sequence:
(
k
+
j
2
) modulo
n
for
j
≥
0
where
k
is the hash index and
n
is the size of the hash table.
a.
If the hash table contains 17 locations and the hash index is 3, what are the first six indices of the array
locations in the probe sequence that quadratic probing defines?
b.
You can compute the indices for the probe sequence more efficiently by using the recurrence relation
k
i
+1
=
(
k
i
+
2
i
+
1) modulo
n
for
i
≥
0 and
k
0
=
k
Derive this recurrence relation.
c.
Demonstrate that you can replace the modulo operation in Part
b
with one comparison and an occasional
subtraction.
3.
Project 11 in Chapter 20 revised the class
Entry
, which is in Listing 20-1, to make it public, and then used it in an
implementation of a dictionary. Consider a hash table of
Entry
objects. Without further changes to the definition
of
Entry
, how could you indicate a removed entry?
4.
Suppose that the size of your hash table is 31, that you use the hash code described in Segment 21.8, and that
you use separate chaining to resolve collisions. List five different names that would hash to the same location
in the table.
5.
Assume the hash table and hash function described in Exercise 4, but use open addressing with linear probing to
resolve collisions. List five different names that do not all hash to the same location in the table yet would
nonetheless result in collisions and clustering.
6.
Repeat Exercise 5, but instead use open addressing with quadratic probing to resolve collisions.
7.
Give an example of a probe sequence produced by quadratic probing that does not reach the entire hash table,
even if the size of the table is a prime number.
8.
Demonstrate that quadratic probing will guarantee a successful addition, if the hash table is at most half full and
its size is a prime number.
9.
Demonstrate that double hashing will produce a probe sequence that reaches the entire table, if the size of the hash
table is a prime number.
Hint
: Show that this is true if the increment and the table size are relatively prime. Then,
if the table size is prime, all increments will be relatively prime to it.
10.
Imagine that you alter the linear probing scheme of Segment 21.13 as follows. When a collision occurs at
hashTable[k]
, you check
hashTable[k
+
c]
,
hashTable[k
+
2
*
c]
,
hashTable[k
+
3
*
c]
, and so on, where
c
is
a constant. Does this scheme eliminate primary clustering?
