Java Reference
In-Depth Information
9.16 Assume that you have a ten-slot closed hash table (the slots are numbered
0 through 9). Show the final hash table that would result if you used the
hash function h(k) = k mod 10 and pseudo-random probing on this list of
numbers: 3, 12, 9, 2, 79, 44. The permutation of offsets to be used by the
pseudo-random probing will be: 5, 9, 2, 1, 4, 8, 6, 3, 7. After inserting the
record with key value 44, list for each empty slot the probability that it will
be the next one filled.
9.17 What is the result of running
sfold
from Section 9.4.1 on the following
strings? Assume a hash table size of 101 slots.
(a) HELLO WORLD
(b) NOW HEAR THIS
(c) HEAR THIS NOW
9.18 Using closed hashing, with double hashing to resolve collisions, insert the
following keys into a hash table of thirteen slots (the slots are numbered
0 through 12). The hash functions to be used are H1 and H2, defined be-
low. You should show the hash table after all eight keys have been inserted.
Be sure to indicate how you are using H1 and H2 to do the hashing. Func-
tion Rev(k) reverses the decimal digits of k, for example, Rev(37) = 73;
Rev(7) = 7.
H1(k) = k mod 13.
H2(k) = (Rev(k + 1) mod 11).
Keys: 2, 8, 31, 20, 19, 18, 53, 27.
9.19 Write an algorithm for a deletion function for hash tables that replaces the
record with a special value indicating a tombstone. Modify the functions
hashInsert
and
hashSearch
to work correctly with tombstones.
9.20 Consider the following permutation for the numbers 1 to 6:
2, 4, 6, 1, 3, 5.
Analyze what will happen if this permutation is used by an implementation of
pseudo-random probing on a hash table of size seven. Will this permutation
solve the problem of primary clustering? What does this say about selecting
a permutation for use when implementing pseudo-random probing?
9.7
Projects
9.1 Implement a binary search and the quadratic binary search of Section 9.1.
Run your implementations over a large range of problem sizes, timing the
results for each algorithm. Graph and compare these timing results.
