G64ADS Homework #4

1. (Weiss 5.1) Given input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function h(x) = x mod 10, show the resulting:

i. Separate chaining hash table

ii. Hash table using linear probing

iii. Hash table using quadratic probing

iv. Hash table with a second hash function h2(x) = 7 – (x mod 7)

2. Show the result of rehashing the hash table in question 1.

3. (Weiss 5.8) What is the advantages and disadvantages of the following collision resolution strategies

· Separate chaining

· Linear probing

· Quadratic probing

· Double hashing