Separate Chaining Implementation Java Description: This is a project for you to

Question

Separate Chaining Implementation Java

Description:

This is a project for you to get some practice with the hashing technique. You must develop your own hash table and hash functions instead of using the provided hash table in Java.

Your program is going to process score files where each line is either blank (in which case it should be ignored) or it has a name and a score on it. The name can be multiple words with any amount of white space between them. You should convert all names to strings with just one space between each word. The last word on each line is a score, which is a floating point number (do error check if the last word is not a number). Two sample score files ex1.txt and ex2.txt (in the folder ex) are shown as follows:

The files can be found here: http://www.csupomona.edu/~ftang/courses/CS240/projects/hashingData/

Your program takes a directory from the command line that contains a list of score files. It then reads each score in every file, and for each name, it computes the average score for that name. In other words, a name can have multiple entries in a score file, and different score files can have different scores with the same name. For example, if I call your program with a directory that contains the above two files as the command line argument, the program will keep track of the names:

For the hashing method, keep a record of the following data and analyze them in your report:

Your program should first print out the above hashing data, and followed by how many names it found, and then it prints out the minimum and maximum average scores along with all names that have those averages. Note, more than one name can have the same average. Also, if there is more than one name for the minimum or maximum, the names may be printed in any order. Here, "ex" is a directory (folder) that contains both files (ex1.txt and ex2.txt). Your program should print out the following to the screen:

Then your program should ask the user to enter a name, and it gives the number of scores plus the average score for that name. If the name wasn't specified in any of the score files, then it says that the name isn't found. It repeats this until the user closes standard input, and your program exits.

You should implement your own hash table with separate chaining to keep track of the (name, score) entries. You should create your own hash functions and compression functions instead of using the hashCode() method provided in Java.

Your program will be tested with the following input files in a directory called: hashingData

Your program should generate the exact output like the above one except for the number of collisions, and the size of the table. If the numbers do not match, then there's a problem.

Explanation / Answer

All keys with the same hashcode "h" is added to the linked list stored at the index "h".
The time complexity of insertion is O(1), no matter how loaded the hash table is. Time complexity for
retrieval is O(1) when the load factor is less than 1.

package lab.hashing;

import lab.linkedlist.*;

public class HashTable
{
   final int INIT_SIZE=100;
   final int INCREMENT=100;
   int CURRENT_SIZE;
   int LOAD_FACTOR=0;
   LinkedList[] hashtable=new LinkedList[INIT_SIZE];

   public HashTable()
   {
CURRENT_SIZE=INIT_SIZE;
   }

   public void put(Object key,Object value)
   {
int index;
Hashable hashkey=(Hashable)key;
index=(Math.abs(hashkey.getHashCode()))%CURRENT_SIZE;
if(hashtable[index]==null)
{
LinkedList seperatechain=new LinkedList();
hashtable[index]=seperatechain;
seperatechain.insertBegining(value);
}
else
{
hashtable[index].insertBegining(value);
}

   }

   public Object get(Object key)
   {
int index;
Hashable hashkey=(Hashable)key;
index=(Math.abs(hashkey.getHashCode()))%CURRENT_SIZE;

if(hashtable[index]==null)
{
return null;
}
else
{
return hashtable[index].search(key);
}
   }

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.