HW #4 Answer Key
Points: Total
12.11 5
12.12 3
12.13 4
12.16 2
#12.11
What are the causes of bucket overflow in a hash file organization? What can be done to reduce the occurrence of bucket overflows?
Possible causes are:
Possible solutions are:
(3 points for causes including both types of skew; 2 for solutions)
A number of students misunderstood the question as regarding how to handle overflows rather than how to reduce their occurrence. Answers such as "double hashing" or "chaining overflow buckets" were given 1/2 point each for a maximum of 1 point.
#12.12
Extendable hashing on a file with the following search-key values: (2, 3, 5, 7, 11, 17, 19, 23, 29, 31); hash function h(X) = X mod 8 and buckets can hold three records.
See image on the right. The resulting hash table has five buckets.
(three points for a correct answer; two points for a minor error; one point for two minor errors or a major error. Note that the index numbers on each bucket are important.)
#12.13
Using the same data, show how the extendable hash table file structure changes as the result of the following steps.
(one point each for a correct answer. The steps are intended to be computed in sequence -- first do (a), then (b), etc. Note that item (a) may cause the extendable hash table to coalesce, and shrink the bucket access table. Answers showing coalescence and shrinking the b.a.t. are correct. Answers that do not coalesce are correct only if they correctly justify why they did not choose to coalesce. Answers that coalesce but do not shrink the b.a.t. are also correct (shrinking the b.a.t. is quite expensive in comparison).
a) delete 11
(note: the answer shown illustrates coalescing buckets but not shrinking the b.a.t. For grading purposes, answers to (b) through (d) will be considered correct regardless of whether the b.a.t. was shrunk in step (a)).
b) delete 31
As shown on the right. Only the last bucket changes.
c) insert 1
As shown on the left. Only the first bucket changes.
d) insert 15
As shown on the right. Only the last bucket changes
#12.16
Why is a hash structure not the best choice for a search key on which range queries are likely?
Hashing distributes search key values uniformly and randomly across the set of buckets available. Because key values do not occupy consecutive buckets, searching for all values within a range may well require reading every bucket -- far more inefficient than a B+-tree or even a sorted file without index.