CS 14 - Homework 3

Due Thursday, May 2 (at beginning of class)

1. An empty table has a capacity of 100, and you insert 6 entries with keys 100, 0, 1199, 1299, 1399, and 2. Using linear probing and the basic hash function (key%size), specify where these entries will be placed in the table? Where will they be placed with double hashing (with HF₂ = 1 + (key%98))?

2. Using a hash table with a size of 811 that uses separate chaining, specify where the following entries will be inserted. Use a basic hash function (key%size). Insert 811, 0, 1623, 2435, 3247, and 2.

3. Using a hash table size of 11 and the basic hash function (key%size). Insert the following items using quadratic probing, 2, 14, 21, 36, 70, 18, 47, 32, and 11. Show the resulting hash table.

4. Rehash the resulting table from problem 3 to a table size of 23.