HashTableNew.java

import java.io.*;

public class HashTableNew, E> { private int M; private KVpair[] HT; private int col =0; private int h(Key key) { return M - 1; }

private int p(Key key, int slot) { return slot; } void setCol(int i) //Collision count { col = i; } int getCol() {return col;}

@SuppressWarnings("unchecked") // Generic array allocation HashTableNew(int m) { M = m; HT = (KVpair[])new KVpair[M]; } /** Insert record r with key k into HT */ boolean hashInsert(int p, Key k, E r) { int home; // Home position for r int pos = home = p; // 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"; if (HT[pos] != null ) { if (HT[pos].key().compareTo(k) ==0) return false; else { //System.out.println(HT[pos].key()+" collide with new key "+k+" with hashcode "+pos); col++; //increase collision count } } else break; } HT[pos] = new KVpair(k, r); // Insert R return true; } /** Search in hash table HT for the record with key k */ E hashSearch(int p, Key k) { int home; // Home position for k int pos = home = p; // 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

char c[] = s.substring(intLength * 4).toCharArray(); int mult = 1; for (int k = 0; k

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

KVPair.java

/** Container class for a key-value pair */ class KVpair { private Key k; private E e;

/** Constructors */ KVpair() { k = null; e = null; } KVpair(Key kval, E eval) { k = kval; e = eval; }

/** Data member access functions */ public Key key() { return k; } public E value() { return e; } }

Objective: Create Hash table and evaluate the efficiency of hashing function. Use HashTableNew.java and HashFunction.java Write a driver program and modify the HashTableNew.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 (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 Objective: Create Hash table and evaluate the efficiency of hashing function. Use HashTableNew.java and HashFunction.java Write a driver program and modify the HashTableNew.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 (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