Quiz 3, Thursday, 10/9

(20 minutes. Open notes)

  1. We want to build a class called ProbingHashTable that implements a hash table that is quadratically probed. Suppose that the items that we want stored in the table are String objects. So we define the following data members for this class: 
    	String[] table; // the hash table containing the strings
	int numStrings; // keeps track of the number of string in table
    Suppose that you have already implemented a method called hash in the ProbingHashTable class. This method takes a String object s and returns the "hash value" of s, which is guaranteed to be an integer in the range 0 through table.length - 1.

    Implement the insert method for the ProbingHashTable class using the probing function

    h(s, i) = (h(s) + i2) mod M.

    In the above equation h(s) is the "hash value" of String s and it is computed by the method hash mentioned above. The method should have the following header: 

    	boolean insert(String s)
    The method returns true if it succesfully inserts s into the table; it returns false otherwise. The method may not be able to successfully insert s if the probing function never finds an empty slot. For this quiz, you do not have to check to see if the array is "too full" and resize in response.