CMSC 420 Section 0401 - Programming Assignment 1, Part C
Due March 22, 11:45PM

Part C - Brent Variation on Double Hashing

In part C, you will extend the work you did in parts A and B.

  1. You need to update your implementation of HashTable.java to be BrentHashTable.java in order to support the Brent variation
  2. You also need to provide a driver class BrentHashTablePlotData.java, which will generate gnuplot data to empirically prove that the programming is worth the benefit, specifically with reference to successful search.
  3. Optional Extra credit: let B(m) be the length of longest successful probe sequence of a full loaded table, where m is the table size/capacity.
    4. Come up with a big Oh expression B(m) for large m consistent with your experimental result. Similarly, come up with a big-Oh expression for the cost of successful search.
Recall that in parts A and B, you wrote HashTable.java. In part C, you need to implement the class AbstractBrentHashTable which extends AbstractHashTable. Note that the AbstractHashTable.java here is the same as it in part B. Your implementation should be named BrentHashTable as shown below: 
public class BrentHashTable extends AbstractBrentHashTable {
	// Methods in Part B
	public BrentHashTable (int tableSize);
	private BrentHashTable ();
	public int getSize ();

	// hashValue(String key) and probleHashValue(String key)
	// are inherited from AbstractHashTable.
	public int hashValue (String key);
	public int probeHashValue (String key);

	public int probeCount; // doesn't need to declare, inherited from AbstractHashTable.
	public boolean put (String key, Object value);
	public boolean containsKey (String key);
	public boolean remove (String key);
	public Object get (String key);

	// You may need to modify longestProbe() for BrentPut()
	public int longestProbe ();

	// New method in Part C
	public boolean brentPut (String key, Object value);
    }
If you note carefully, you will find that in Part C, a new method is defined: Next the driver. The driver class BrentHashTablePlotData will output a gnuplot data file which in turn will generate a PostScript file like success.ps and longest.ps. The goal is to produce charts of average cost(probes) of successful search with collisions handled by Brent's variation of double hashing. How do we produce these files? Use HashTable.probeCount wisely to implement BrentHashTablePlotData. That basically finishes your programming task. Here is some post processing. Visualization is accomplished with gnuplot. You can figure out how this works by the examples provided below.

Grading:

Submission:

Web Accessibility