This assignment is due on 08/02/18 at 11:59:59am. Task: Implementation of the Pr
ID: 3920212 • Letter: T
Question
This assignment is due on 08/02/18 at 11:59:59am.
Task: Implementation of the ProbeHashTable class with linear probing.
The template of ProbeHashTable class and relevant classes are given below:
Requirements:
Implement the ProbeHashMap class as we discussed in the lectures.
Your implementation has to follow the specification given. Any other implementation (there are tons of HashTable code on the Internet) will not receive any credit.
Test: write a test program to create a hash table with the default size. Insert 100 data items (random strings) and then remove 10 of them. Finally, please print out the remaining items in the hash table. Note that your implementation will be evaluated by a specific test program while being graded.
Bonus: 10 point bonus will be given for those implementation that prints out the number collisions while the 100 data items are inserted into the hash table. Hint: to do that, you may want to change the return type of the put() method to int type, which is the number of collisions. Your README file must state the bonus option you are taking to earn the bonus.
Submission:
Each student submits one copy of the source code: ProbeHashTable.java, AbstractHashMap.java, AbstractMap.java, MapEntry.java and Test.java.
Here is my current code:
import java.util.*;
public abstract class AbstractHashMap extends AbstractMap {
protected int n = 0;
protected int capacity;
private int prime;
private long scale, offset;
public AbstractHashMap() {
capacity = 199;
prime = 999331;
Random rand = new Random();
scale = rand.nextInt(prime-1) + 1;
offset = rand.nextInt(prime);
createTable();
}
public AbstractHashMap(int c, int p, long scale, long off) {
this.capacity = c;
this.prime = p;
this.scale = scale;
this.offset = off;
createTable();
}
public int size() {return n;}
public boolean isEmpty() {return n == 0;}
public int hashValue(Object key) {
return (int) ((Math.abs(key.hashCode()*scale+offset)%prime)%capacity);
}
public Object get(Object key) {
int h = hashValue(key);
return bucketGet(h, key);
}
public Object remove(Object key) {
int h = hashValue(key);
return bucketRemove(h, key);
}
public Object put(Object key, Object value) {
int h = hashValue(key);
return bucketPut(h, key, value);
}
protected abstract void createTable();
protected abstract Object bucketGet(int h, Object k);
protected abstract Object bucketRemove(int h, Object k);
protected abstract Object bucketPut(int h, Object k, Object v);
}
public abstract class AbstractMap {
public abstract Object get(Object key);
public abstract Object remove(Object key);
public abstract Object put(Object key, Object value);
public abstract int size();
public abstract boolean isEmpty();
}
import java.util.*;
public class ProbeHashTable extends AbstractHashMap {
private MapEntry[] table;
private MapEntry DEFUNCT = new MapEntry(null,null);
int currentSize = 0;
int maxSize = 100;
public ProbeHashTable() {
int currentSize = 0;
int maxSize = 100;
String keys = new String[maxSize];
String vals = new String[maxSize];
}
protected void createTable() {
table = (MapEntry[]) new MapEntry[capacity]; // safe cast
}
private boolean isAvailable(int i) {
return(table[i] == null) || (table[i] == DEFUNCT);
}
private int findSlot(int h, String k) {
int avail = -1;
int i = h;
do {
if(isAvailable(i))
{
if (avail == -1)
avail = 1;
if (table[i] == null)
break;
} else if (table[i].getKey().equals(k))
return i;
i = (i+1)%capacity;
} while(i !=h);
return -(avail+1);
}
protected Object bucketPut(int h, Object key, Object value) {
int i = findSlot(h, (String)key);
if(i >= 0) {
return table[i].setValue(value);
}
table[-(i+1)] = new MapEntry(key, value);
maxSize++;
return table[i].getValue();
}
protected Object bucketGet(int h, Object key) {
int i = findSlot(h, (String)key);
if(i < 0) return null;
return table[i].getValue();
}
protected Object bucketRemove(int h, Object key) {
int i = findSlot(h, (String) value);
if (i < 0) return null;
String answer = (String) table[i].getValue();
table[i] = DEFUNCT;
maxSize--;
return answer;
}
public String toString() {
System.out.println(" Hash Table: ");
for( int i = 0; i < maxSize; i++)
if (keys[i] != null)
System.out.println(i + " " + keys[i] +" " + vals[i]);
System.out.println();
}
}
public class MapEntry {
private String key;
private String value;
public String getKey() {return key;}
public String getValue() {return value;}
public int hashCode() {
int h = 0;
for (int i=0; i>27;) {
h += (int)key.charAt(i);
}
return h;
}
}
import java.util.*;
public class Test
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Hash Table Test ");
ProbeHashTable pht = new ProbeHashTable();
char ch;
do {
System.out.println(" Hash Table Operations ");
System.out.println("1. insert ");
System.out.println("2. remove ");
System.out.println("3. print hash table ");
int choice = scan.nextInt();
switch(choice)
{
case 1 :
System.out.println("Enter index , key and value");
pht.bucketPut(scan.next(), scan.next(), scan.next());
break;
case 2 :
System.out.println("Enter index , key");
pht.bucketRemove(scan.next(), scan.next() );
break;
case 3 :
pht.toString();
break;
default :
System.out.println("Wrong Entry ");
break;
System.out.println(" Do you want to continue (Type Y or N) ");
ch = scan.next().charAt(0);
}} while (ch == "Y" || ch == "N");
}
}
Explanation / Answer
import java.io.*;
class StringDataItem
{
private String sData;
public StringDataItem(String ss)
{
sData = ss;
}
public String getKey()
{ return sData; }
}
class StringHashTable
{
private StringDataItem[] hashArray;
private int arraySize;
private StringDataItem nonItem;
public StringHashTable(int size)
{
arraySize = size;
hashArray = new StringDataItem[arraySize];
nonItem = new StringDataItem("-"); //dash IS deleted
for(int i = 0; i < size; i++)
hashArray[i] = new StringDataItem(nonItem.getKey());
}
public void displayTable()
{
System.out.print("Table: ");
for(int j = 0; j < arraySize; j++)
{
if(hashArray[j] != null)
System.out.print(hashArray[j].getKey() + " ");
else
System.out.print("** ");
}
System.out.println("");
}
public int hashFunc(String key)
{
int hashVal = 0;
for(int j = 0; j<key.length(); j++)
{
int letter = key.charAt(j);
hashVal = (hashVal * 27 + letter) % arraySize;
}
return hashVal;
}
public void insert(StringDataItem item)
{
String key = item.getKey();
int hashVal = hashFunc(key);
while(hashArray[hashVal].getKey() != "-")
{
++hashVal;
hashVal %= arraySize;
}
hashArray[hashVal] = item;
}
public StringDataItem delete(String key)
{
int hashVal = hashFunc(key);
while(hashArray[hashVal].getKey() != "-" && hashArray[hashVal].getKey() != null)
{
if(hashArray[hashVal].getKey().equals(key))
{
StringDataItem temp = hashArray[hashVal];
hashArray[hashVal] = nonItem;
return temp;
}
++hashVal;
hashVal %= arraySize;
}
return null;
}
public StringDataItem find(String key)
{
int hashVal = hashFunc(key);
while(hashArray[hashVal].getKey() != "-" && hashArray[hashVal].getKey() != null)
{
if(hashArray[hashVal].getKey().equals(key))
return hashArray[hashVal];
++hashVal;
hashVal %= arraySize;
}
return null;
}
}
class StringHashTableApp
{
public static void main(String[] args) throws IOException
{
StringDataItem aDataItem;
int size, n, keysPerCell;
String aKey;
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter initial number of items: ");
n = getInt();
keysPerCell = 10;
StringHashTable theHashTable = new StringHashTable(size);
for(int j=0; j<n; j++)
{
aKey = Double.toString((java.lang.Math.random() * keysPerCell * size));
aDataItem = new StringDataItem(aKey);
theHashTable.insert(aDataItem);
}
while(true)
{
System.out.print("Enter first letter of show, insert, delete, or find: ");
char choice = getChar();
switch(choice)
{
case 's':
theHashTable.displayTable();
break;
case 'i':
System.out.print("Enter string to insert: ");
aKey = getString();
aDataItem = new StringDataItem(aKey);
theHashTable.insert(aDataItem);
break;
case 'd':
System.out.print("Enter string to delete: ");
aKey = getString();
theHashTable.delete(aKey);
break;
case 'f':
System.out.print("Enter string to find: ");
aKey = getString();
aDataItem = theHashTable.find(aKey);
if(aDataItem != null)
System.out.println("Found " + aKey);
else
System.out.println("Could not find " + aKey);
break;
default:
System.out.println("Invalid entry!");
}
}
}
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.