hash table with separate chaining java The following is my main method...im gett

Question

hash table with separate chaining java

The following is my main method...im getting error implementing the HashTable class....does anyone know how to correctly implement the following methods in the Hashtable class in order to be used in main method? like the put(), divideOccur(), setMinMax(), getCollis(), getNumEntries(), getMinKey(), getMinVal(), getMaxKey(), getMaxVal(), and displayInfo()

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

It must follow the sample output:

import java.io.*;
import java.util.*;

public class Project2 {
public static void main(String[] args) throws IOException {
  
if (args.length < 1) {
System.out.println("Error: Directory name is missing");
System.out.println("Usage: java scoreProcess directory_name");
return;
}
File directory = new File(args[0]); // args[0] contains the directory name
File[] files = directory.listFiles(); // get the list of files from that directory

Scanner input;
  
HashTable table = new HashTable();

// process the arguments stores in args
for (int i = 0; i < files.length; i++) {
input = new Scanner(files[i]);

//System.out.println(" Current file name: " + files[i].getName());
  
// no error checking done here, add your own
String key;
Double value;
while (input.hasNext())
{
   key = "";
   while (!input.hasNextDouble()){
       key += input.next() + " ";
   }
  
   value = new Double(input.next());    
   table.put(key.trim(), value.intValue());
}
}
table.divideOccur();
table.setMinMax();
String name = "";
Scanner kb = new Scanner(System.in);
System.out.println("The number of collisions: " + table.getCollis());
System.out.println("The number of entries in the table is : " + table.getNumEntries() + ". The size of bucket array is 100." );
System.out.println("The team with the lowest average is " + table.getMinKey() + " with a score of: " + table.getMinVal());
System.out.println("The team with the highest average is " + table.getMaxKey() + " with a score of: " + table.getMaxVal());
while(true) {
   System.out.println("Please enter the name of a team you would like to search for, remember" +
           " all team names start with a capital letter. If you would like to exit please enter a lowercase x");
   name = kb.nextLine();
   if(name.equals("x"))
       return;
   else
       table.displayInfo(name);
}
}
  
}

Explanation / Answer

Try this code. This is a sample application that I implemented.

public class SeparateChainingHashST<Key, Value> {
private static final int INIT_CAPACITY = 4;

// largest prime <= 2^i for i = 3 to 31
// not currently used for doubling and shrinking
// private static final int[] PRIMES = {
// 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381,
// 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301,
// 8388593, 16777213, 33554393, 67108859, 134217689, 268435399,
// 536870909, 1073741789, 2147483647
// };

private int N; // number of key-value pairs
private int M; // hash table size
private SequentialSearchST<Key, Value>[] st; // array of linked-list symbol tables

// create separate chaining hash table
public SeparateChainingHashST() {
this(INIT_CAPACITY);
}

// create separate chaining hash table with M lists
public SeparateChainingHashST(int M) {
this.M = M;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
for (int i = 0; i < M; i++)
st[i] = new SequentialSearchST<Key, Value>();
}

// resize the hash table to have the given number of chains b rehashing all of the keys
private void resize(int chains) {
SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST<Key, Value>(chains);
for (int i = 0; i < M; i++) {
for (Key key : st[i].keys()) {
temp.put(key, st[i].get(key));
}
}
this.M = temp.M;
this.N = temp.N;
this.st = temp.st;
}

// hash value between 0 and M-1
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}

// return number of key-value pairs in symbol table
public int size() {
return N;
}

// is the symbol table empty?
public boolean isEmpty() {
return size() == 0;
}

// is the key in the symbol table?
public boolean contains(Key key) {
return get(key) != null;
}

// return value associated with key, null if no such key
public Value get(Key key) {
int i = hash(key);
return st[i].get(key);
}

// insert key-value pair into the table
public void put(Key key, Value val) {
if (val == null) {
delete(key);
return;
}

// double table size if average length of list >= 10
if (N >= 10*M) resize(2*M);

int i = hash(key);
if (!st[i].contains(key)) N++;
st[i].put(key, val);
}

// delete key (and associated value) if key is in the table
public void delete(Key key) {
int i = hash(key);
if (st[i].contains(key)) N--;
st[i].delete(key);

// halve table size if average length of list <= 2
if (M > INIT_CAPACITY && N <= 2*M) resize(M/2);
}

// return keys in symbol table as an Iterable
public Iterable<Key> keys() {
Queue<Key> queue = new Queue<Key>();
for (int i = 0; i < M; i++) {
for (Key key : st[i].keys())
queue.enqueue(key);
}
return queue;
}

/***********************************************************************
* Unit test client.
***********************************************************************/
public static void main(String[] args) {
SeparateChainingHashST<String, Integer> st = new SeparateChainingHashST<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}

// print keys
for (String s : st.keys())
StdOut.println(s + " " + st.get(s));

}

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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