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.

    A sample run is provided below to help you debug your code.

    $ java HashTableQuadraticProbe↵
    Enter some lowercase characters to store as keys in the hash table 
    (Their uppercase equivalents will be used as the corresponding values):
    quadratic↵
    
    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:
    QUADRATIC
    
    Now enter one or more lowercase character keys to delete from the hash table: 
    rq↵
    
    Testing retrieval after deletion:
    -UAD-ATIC
    

    If one simply deletes a key, then a later search for some other key that followed the deleted key's same probe chain may fail. To combat this potential problem, use the provided "tombstone" array to mark deleted keys. Insertions should be allowed to put an item in a position marked with a tombstone, but searches for a key shouldn't stop at a tombstone.