CMSC 420 Section 0401 - Programming Assignment 1, Part D
GonnetMunro Scheme on Double Hashing
Due April 14, 11:45PM

Overview

In part D, you will extend the work you did in parts A, B, and C.
  1. You need to update your implementation of HashTable.java of part B to be GonnetMunroHashTable.java in order to support the Gonnet-Munro variation
  2. You also need to provide a driver class Gonnet-Munro HashTablePlotData.java, which will generate gnuplot data.
The plots will attempt to (empirically) show that the extra effort in Gonnet-Munro programming (quantified by the graph moves.ps) is worth the benefit (for example, see longest.ps).

Details

Recall that in parts A and B, you wrote HashTable.java. In part C, you need to implement the class AbstractGonnetMunroHashTable which extends AbstractHashTable. Note that the AbstractHashTable.java here is the same as it in part B. Your implementation should be named GonnetMunroHashTable as shown below: 
public class GonnetMunroHashTable extends AbstractGonnetMunroHashTable {
	public GonnetMunroHashTable (int tableSize);
	private GonnetMunroHashTable ();
	// Methods in Part B
	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 GonnetMunroPut()
	public int longestProbe ();

	// New data member in Part D
	public int gonnetMunroMoveCount;
	// New method in Part D
	public boolean gonnetMunroPut (String key, Object value);
    }
Observe that in part D, a new method and a new instance variable has been defined: Next the driver. The driver class GonnetMunroTablePlotData will output a gnuplot data file which in turn will generate a PostScript file like success.ps, longest.ps, and moves.ps. The goal is to produce charts of average cost(probes) of successful search with collisions handled by GonnetMunro scheme of double hashing. How do we produce these files? Use probeCount and gonnetMunroMoveCount wisely to implement GonnetMunroHashTablePlotData. 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