Homework 4

Due: October 31st, 2012 at the beginning of class
Homework turned in after class will not be accepted.
Homework turned in during class but after I have collected it will lose 20%.

Do your own work for this assignment; do not work with others. Consult the book and your professor for help if you need it. Please write neatly, or preferably type your answers. Use good grammar, spelling, and complete sentences.

(10 points) Do problem 5.1 in your textbook. Insert the inputs in the given order. If any insertion fails, indicate that (but do not resize the table). The hash table size is implied by the hash function.
(10 points) Do problem 5.2 in your textbook. Show the result for each of the four parts of the answer for 5.1. The hash table size should be a prime number at least as large as twice the original size, and the primary hash function should change to reflect the new table size.

(20 points) Study the behaviors of different hashing and probing functions in an open-addressing hash table. Implement a limited-functionality hash table for strings, which keeps track only of whether a given slot is filled or empty. Then count the total number of probes required to insert all the words in the given dictionary for various methods and report those numbers. The number of probes to insert something that has no collisions is 1. The number of probes to insert something that has 3 collisions is 4, etc.

Use the hash table sizes and functions given below. Note that some has table sizes are prime numbers (e.g. 1753) while others are not (e.g. 2048).

Use the following hash functions for strings:

int hash_string_1(const string &key, int tableSize) {
    return (key.size() * key.size() * 4) % tableSize;
}

int hash_string_2(const string &key, int tableSize) {
    return (key[0] + 27 * key[1] + 729 * key[2]) % tableSize;
}

int hash_string_3(const string &key, int tableSize) {
    // come up with your own hash function and see if you can do better on any
    // of the test cases
}

Provide your test code. Test your hash functions and table sizes on this dictionary (insert the words in the order given). Then report your results in a 12-by-6 table that displays the total number of probes required for each method. The columns for hash_string_1 and hash_string_2 are filled in so you can compare your results with mine. Your results should be the same as mine for hash_string_1 and hash_string_2.

PLEASE NOTE: some of the inserts may fail because the probes will overflow (especially quadratic probing — when the probe number is large, then its square will be too large to fit into a 32-bit integer). To deal with this, we will count up to N probes, where N is the table size, and then stop probing. So that insert will fail, but we will still count the N probes we used to find that it failed.

Table Size	Linear Probing with hash_string_1	Quadratic Probing with hash_string_1	Linear Probing with hash_string_2	Quadratic Probing with hash_string_2	Linear Probing with hash_string_3	Quadratic Probing with hash_string_3
1753	175967	56546	2902	2077
1786
2039
2048
3067
3072
4093
4096
5119
5120
8191
8192

EXPLAIN your results. What do you notice about the different hash functions, table sizes, probing strategies, and why do you think they behave differently?

valid html and css