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