CMSC 420 Section 0401 - Programming Assignment 1, Part A
Due Feb. 21, 8:00AM

Part A - Hash table handling collisions by double hashing

Write class HashTable which extends AbstractHashTable. It should support the following functionality (see description below):

public class HashTable extends AbstractHashTable {
	public HashTable (int tableSize);
	private HashTable ();
	public int getSize ();

	public void setHashArgument (int a);
	public void setMADArguments (int a, int b);
	public int hashValue (String key);
	public int probeHashValue (String key);

	public int probeCount; // don'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 HashTable (int tableSize) is to initialize the hash table size. If the input tableSize is not a prime, the table size will be the smallest prime number larger than tableSize. Unlike JDK class Hashtable, the hash table in this programming assignment is not expandable.
• private HashTable() is to prevent instances without being initialized.
• getSize() returns the size of hash table.
  [2/19/02 added by TA:] Unlike Hashtable.size() in JDK, getSize() returns the capacity of HashTable instead of number of items in the table.
• setHashArgument (int a) sets the argument for converting the key to an integer value. See 3rd slide of lecture notes. In this programming assignment, the default argument a is 37.
• setMADArguments (int a, int b) sets the arguments of MAD function: h(k)=a*k+b mode m. m is the smallest prime number equal to or larger than table size. By default, a=1 and b=0.
• For grading purposes, your hashValue() must match the sample hash function discussed in class. See 4rd slide of lecture notes. Note that 37 in the slide may be changed by setHashArgument (int a).
  [2/19/02 added by TA:] There was a typo here. 37 in the slide may be changed by setHashArgument (int a), not setMADArguments (int a, int b).
• To handle collision by double hashing, another hash function probeHashValue (String key) is required as offset for probing. This is what you will design by yourself. For full credits, your probeHashValue (String key) must guarantee that (1) if load factor is not 100%, a new item can always be inserted and no cell is probed twice. (2) Your double hashing is more efficient than linear probe.
• Variable probeCount is for grading purpose. For each probe in the following 3 member functions, increase probeCount by 1.
• put (String key, Object value) puts the key-value pair into the hash table. If the key is already in the table or cannot probe an empty place to put the key-value pair, it returns false. Otherwise, put the key-value pair into the hash table and returns true.
• containsKey (String key) returns true/false if the key "is"/"is not" in the hash table, respectively.
• remove (String key) removes the key and its corresponding value out of hash table, returns true/false if succeed/fail.

Grading:

• The maximum points of part A is 100.
• The public drivers for grading will be posted soon.
• [2/16/02 added by TA:] The public HashTableDriver1.java is now available with correct output.
• [2/17/02 added by TA:] The public HashTableDriver2.java is now available. Running "java HashTableDriver2 input 50 100 150 200 500" with input file, my implemetation generates the sample output output. You can get 10 points if the output shows your double hashing is better than linear probing. Note: your output does not need to be the same as mine. We may have different implementation of probeHashValue().
• [3/4/02 added by TA:] All the grading drivers can be found here.

Submission:

• Submission will be handled using the submit program: "~sc42002/bin/submit 1 HashTable.java".
• [2/19/02 added by TA:] If your program consists of more than one class, tar and gzip them and submit. EX: "~sc42002/bin/submit 1 foo.tar.gz"

Web Accessibility