Exercises - Hash Tables

1. In a given hash table with an associated array of size $11$, integer keys of 9, 26, 50, 15, 2, 21, 36, 22, and 31, are inserted in that order. For each of the methods listed below, draw the internal structure of the hash table after these insertions have been made.

1. linear probing
2. separate chaining

2. Complete the class HashTableQuadraticProbe so that it implements a hash table using the quadratic probing where the array size $m$ is always an integer power of $2$ and the cell with index $p(k,i)$ as defined below is probed after the $i^{th}$ collision in seeking to insert (or retrieve) key $k$ with hash function $h$.

$$p(k,i) = \left[ h(k) + \frac{1}{2}i + \frac{1}{2}i^2 \right]\pmod{m}$$

Recall, this means that for the insertion (or retrieval) of key $k$ the sequence of indices probed starts at $h(k)$ and makes successively larger jumps to the right with each collision, wrapping back to the start of the array as needed. In particular, the jumps made are of size $1,2,3,\ldots$.

Your HashTableQuadraticProbe class should support deletion of key-value pairs and resizing (double size when 1/2 full, halve size when 1/8th full). Do not add any instance variables or methods to this class beyond those already provided.

The HashTableQuadraticProbeTest class, which takes the following actions, can be used to test your code.

1. The user will first be prompted to enter some lowercase characters to store as keys in the hash table, using their uppercase equivalents as the corresponding values.

2. Then, the internal state of the resulting hash table is printed.

3. The uppercase values stored using the lowercase characters as keys are then retrieved and printed (in the same order they were inserted into the hash table).

4. Finally, to test retrieval after one or more deletions, the user is then prompted to enter some lowercase keys to delete from the hash table (along with their corresponding values, of course). These are deleted and again the uppercase values stored using the lowercase characters as keys are retrieved and printed (in the same order they were inserted into the hash table). Of course, some of these will now be missing. Dashes will be printed for these missing keys.

\$ java HashTableQuadraticProbe↵
Enter some lowercase characters to store as keys in the hash table
(Their uppercase equivalents will be used as the corresponding values):

0 : null/null
1 : q/Q
2 : a/A
3 : r/R
4 : d/D
5 : u/U
6 : c/C
7 : t/T
8 : null/null
9 : i/I
10 : null/null
11 : null/null
12 : null/null
13 : null/null
14 : null/null
15 : null/null

Testing retrieval: