Homework 3 Programming Part (20 points)

The following files provide an interface to a hash table:

You are to implement this hash table. The table itself should be a dynamic array: that is, an array that doubles when you try to insert and it is full and halves whenever it becomes one quarter (or less) full. The size of the array should start at 0. To hash into this table, use open addressing with double hashing probing. For the two hash functions, use the multiplication method. For example:
h_1(k) = |_m x fract(0.3874971020310k)_| and h_2(k) = |_m x fract(0.8764734163224k)_| where m is the current size of the array.

The directory test_files.tar contains some basic examples of how to work with the interface.

Tips:

If you can't download the files from this page, you can get them by logging into CDF and looking in /h/u1/bureshop/pub.

Submission Instructions: Please submit all files needed to compile your code by 6pm on Tuesday, July 27. You can submit from within your CDF account by using submit -c csc263h -a prog3 {filenames}. You can get more information about submit in the man page.