Reference no: EM132095880

Please help! Any help is appreciated. Answer only in Java, nothing else.

Use HashTable.java and HashFunction.java from below

Write a driver program and modify the HashTable.java to build a Hash table with the specifications as follows:

(a) A table size is 128 slots.

(b) The input data are randomly generated UNIQUE upper case data names with eight characters in length (Each name has to be unique).

(c) Use the generated name for both key and Element value (KVpair.)

(d) Use the same name as the key for sfold function in HashFunction class to create the hash code for the table entry.

(e) Add those data names to the table start with empty table until the table is 40% full.

(f) Display the percentage of table had been occupied during the insertion.

(g) Use the linear prob method for handling collisions and calculate total accumulated collision sum (need to modify the hashInsert method provided in following code).

(h) If the name had collision on the Hash Table, display all names of those collide keys.

(i) Display the total number of collision.

(j) Continue to run the program until the table is 60% and display the total number of collision.

HashTable.java

import java.io.*;

public class HashTable, E> {
private int M;
private KVpair[] HT;

private int h(Key key) {
return M - 1;
}

private int p(Key key, int slot) {
return slot;
}

@SuppressWarnings("unchecked") // Generic array allocation
HashTable(int m) {
M = m;
HT = (KVpair[])new KVpair[M];
}
/** Insert record r with key k into HT */
void hashInsert(Key k, E r) {
int home; // Home position for r
int pos = home = h(k); // Initial position
for (int i=1; HT[pos] != null; i++) {
pos = (home + p(k, i)) % M; // Next pobe slot
assert HT[pos].key().compareTo(k) != 0 :
"Duplicates not allowed";
}
HT[pos] = new KVpair(k, r); // Insert R
}
/** Search in hash table HT for the record with key k */
E hashSearch(Key k) {
int home; // Home position for k
int pos = home = h(k); // Initial position
for (int i = 1; (HT[pos] != null) &&
(HT[pos].key().compareTo(k) != 0); i++)
pos = (home + p(k, i)) % M; // Next probe position
if (HT[pos] == null) return null; // Key not in hash table
else return HT[pos].value(); // Found it
}

}

HashFunction.java

import java.io.*;
import java.math.*;

public class HashFunction
{

int sfold(String s, int M) {

int intLength = s.length() / 4;
int sum = 0;
for (int j = 0; j < intLength; j++) {
char c[] = s.substring(j*4,(j*4)+4).toCharArray();
int mult = 1;
for (int k = 0; k < c.length; k++) {
sum += c[k] * mult;
mult *= 256;
}
}

char c[] = s.substring(intLength * 4).toCharArray();
int mult = 1;
for (int k = 0; k < c.length; k++) {
sum += c[k] * mult;
mult *= 256;
}

return(Math.abs(sum) % M);
}
int h(String x, int M) {
char ch[];
ch = x.toCharArray();
int xlength = x.length();

int i, sum;
for (sum=0, i=0; i sum += ch[i];
return sum % M;
}
int h(int x) {
return(x % 16);
}

}