CS245 Winter 2000 Assignment 4 due in class on Thursday February 3 PROBLEM 1 Problem 1 Suppose someone has implemented the dynamic hashing mechanisms using the *opposite* bits than we did in class. That is, assume that linear hashing uses i high order bits, while extensible hashing uses i low order bits. Suppose that you insert the following records into an initially empty hash tables: record A: hash(key(A)) = 0011 record B: hash(key(B)) = 1111 record C: hash(key(C)) = 0110 record D: hash(key(D)) = 0000 record E: hash(key(E)) = 1001 record F: hash(key(F)) = 1100 Also assume that buckets can hold two records at most. (a) Suppose that for linear hashing, m is initially 3 (i.e., 11 in binary) and i is 2. Show what the linear hash table would look like after records A through F are inserted (use the labels A through F to indicate what record(s) are in each bucket). Assume you use the i high order bits of each hash, but do not change anything else in the algorithm as discussed in class. (No threshold is set for automatically changing i and m, so i and m stay at their initial values.) (b) Next suppose that you decide to change i to 3, without changing m. (The next step would be to grow m to extend the table, but let us not worry about that part here.) Show what the hash table would look like after changing i to 3. (c) What is the problem that occurred (if any) because we used the high order bits instead of the low order ones? Is this problem serious? (d) Next, show what an extensible hash table would look like after inserting our records, assuming you use the low order hash bits. Assume that i = 2, and that initially the directory points to four different empty buckets. (e) Now you insert record G with hash(key(G)) = 0111, causing you do increase the directory to i = 3. Show the state of the table after this insertion. (f) What is the problem that occurred (if any) because we used the low order bits instead of the high order ones? Is this problem serious? PROBLEM 2 Consider an extensible hash structure where buckets can hold up to three records. Initially the structure is empty. Then we insert the following records, in the order below, where we indicate the hashed key in parenthesis (in binary): a [111001] b [000011] c [101000] d [101111] e [010110] f [101000] g [010110] h [100101] i [100101] j [110001] Show the structure after these records have been inserted. PROBLEM 3 For the same records, hash keys, and assumptions as PROBLEM 2, show the *linear* hash structure for this file. Initially the structure is empty. Assume that the threshold value is 2. (i.e., when the average number of keys per non-overflow bucket is greater than 2, we allocate another bucket). END OF HOMEWORK 4