# 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_1Quadratic Probing

with hash_string_1Linear Probing

with hash_string_2Quadratic Probing

with hash_string_2Linear Probing

with hash_string_3Quadratic Probing

with hash_string_31753 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?

Copyright © 2012 Adam Sealey, based
largely on a syllabus by Greg Hamerly .

Computer Science Department

Baylor University