CISC220 F2014 Lab8

Lab #8

1. Written problems

Suppose you want to hash words into a hash table of size m. Let v_i be the English alphabet place value of the ith letter in a q-letter word W, where the value of 'a' = 0, 'b' = 1, ..., 'z' = 25. One possible hash function is

h(W) = [v_0 + v_1 + ... + v_(q-1)] mod m

For example, if m = 11 and W = "abc", then h("abc") = [0 + 1 + 2] mod 11 = 3

Assume m = 11 and you have the following list of words, in order:

1. dog
2. duck
3. cow
4. mouse
5. horse
6. sheep
7. goat
8. chicken
9. pig

Please answer the following questions about the hash function, table, and list of words above. Feel free to write a short program to ensure that your calculations are correct.

• (2 points) What are the "home positions" of every word? That is, what indices do they hash to before collisions are resolved? Either show your work or include your program code in the PDF.
• (1 point) Show the final hash table if the words are inserted in the order above using separate chaining for collision resolution. Each chain should be an unordered, singly-linked list with the newest item being inserted at the head of the list.
• (1 point) Show the final hash table if the words are inserted in the order above using linear probing with a step size of 1. What is the total number of probes beyond the home position for each word?
• (1 point) Suppose the table is rehashed during linear probing when the load factor exceeds 0.5. Let the new table size be 23, the smallest prime number greater than 2m. Show the new hash table both right after rehashing AND after all the words have been inserted.

2. Submission

• Make a PDF file <Your Name>_Lab8_README.pdf with your answers to the written exercises
• No need to compress or archive the PDF, since that's all you're turning in.
• Submit it in Sakai by midnight at the end of Thursday, November 20