Question

Task: Comparing the performance between Linear Probing and Double Hashing. Requirements: Please make sure your program compiles, otherwise your submission will not be graded and you will receive zero. Point deduction rule: Compile warning: 3 points each. Minor error: such as not meeting the assignment input/output requirement, 5 points each. Major error: examples include, infinite loop, runtime errors, any runtime exception, 15 points each. Any code not compliant to the assignment requirement (e.g., not using List interface and AbstractMap and AbstractHashMap classes) will not be graded and you will receive zero. (40%) DblHashMap.java: Implement the DblHashMap class. Your implementation should be very similar to ProbeHashMap except for the findSlot method. (50%) Test.java: write a test program to create a hash table with the size of 109. Import 66 data items (given by a text file). The data file "roster.txt" is provided, which contains the all players of Cleveland Browns. Please use the first column, the last name, as the key, and treat the rest of information as value. Please perform the following tasks after the data are imported to the hash table: Print out the number of collisions occurred during the data insertion, and discuss which approach causes more collisions. Comparing the resulting tables between Linear Probing and Double Hashing, and have a discussion which approach has a more obvious trend of clustering. (10%) README: a text formated README file that contains the information required in the submission section.

Answer 1

public interface List {
   public int size();
   public boolean isEmpty();
   public Object get(int i) throws OutOfRangeException;
   public void set(int i, Object e) throws OutOfRangeException;
   public void add(int i, Object e) throws OutOfRangeException;
   public Object remove(int i) throws OutOfRangeException;
   }

public class ArrayList implements List{
private int CAP;
private int size;
private Object[] itme;
public ArrayList(){
this(5005);}
public ArrayList(int capacity){
CAP = capacity;
size = 0;
itme = new Object[capacity]; }
public int size(){
return size; }
public Object get(int i) throws OutOfRangeException{
if(i return itme[i];
}else{
throw new OutOfRangeException();
} }
public void set(int i, Object e) throws OutOfRangeException{
if(i itme[i] = e;
}else{
throw new OutOfRangeException();
} }
public void add(int i, Object e) throws OutOfRangeException{
if(i>size){
throw new OutOfRangeException(); }
for(int j = size-1; j>= i; j--){
itme[j+i] = itme[j];}
itme[i] = e;
size++; }
public Object remove(int i) throws OutOfRangeException{
if(i >= size){
throw new OutOfRangeException();
}
Object o = itme[i];
for(int j=i; j itme[j] = itme[j+i]; }
size--;
return o;
}
public boolean isEmpty(){
return size == 0;
}}
public class OutOfRangeException extends Exception {
   public OutOfRangeException(){}
   public OutOfRangeException(String msg) { System.out.println(msg);
}}
public abstract class AbstractMap {
   public abstract Object get(Object key);
   public abstract Object put(Object key, Object value);
   public abstract Object remove(Object key);
   public abstract boolean isEmpty();
   public abstract int size();
   public abstract Iterable keySet();}

import java.util.Iterator;
public class SArrayIterator implements Iterator {
   private ArrayList data;
   private int i = 0;
   private boolean removable = false;

   public SArrayIterator(ArrayList a) {
   data = a;
   }
   public boolean hasNext() {return i < data.size();}

   public Object next() {
   Object answer = null;
   if (i == data.size())
   return null;
   try {
   answer = data.get(i++);
   } catch (OutOfRangeException e) {
   System.out.println("Out Of Range");
   }
   removable = true;
   return answer;
   }

   public void remove() {
   if (!removable)
   throw new IllegalStateException("nothing to remove");
   try {
   data.remove(i-1);
   } catch (OutOfRangeException e) {
   System.out.println("Out of Range");
   }
   i--;
   removable = false;
   }}

public class MapEntry {
private String key;
private String value;
public MapEntry() {this(null, null);}
public MapEntry(String k, String v) {
this.key = k;
this.value = v;
}
public String getKey() {return key;}
public String getValue() {return value;}
public void setKey(String k) {key = k;}
public Object setValue(String value) {
String old = this.getValue();
this.value = value;
return old;
}
public int hashCode () {
if (key == null) return 0;
int h = 0;
for (int i = 0; i< key.length(); i++){
h += (int)key.charAt(i);
h = (h<<5) | (h>>>27);
}
return h;
}}
import java.util.Random;
public abstract class AbstractHashMap extends AbstractMap {
protected int n = 0;
protected int capacity;
private int prime;
private long scale, offset; // a= scale, b = offset
public AbstractHashMap(int c, int p) {
this.capacity = c;
this.prime = p;
Random rand = new Random();
this.scale = rand.nextInt(prime - 1) + 1;
this.offset = rand.nextInt(prime);
createTable();
}
public AbstractHashMap() { this(61,999331);}
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 put (Object key, Object value) {
int h = hashValue(key);
return bucketPut(h, key, value);
}
public Object remove (Object key) {
int h = hashValue(key);
return bucketRemove(h,key);
}
protected abstract void createTable();
protected abstract Object bucketGet(int h, Object k);
protected abstract Object bucketPut(int h, Object k, Object v);
protected abstract Object bucketRemove(int h, Object k);
}
import java.util.Iterator;
public class ProbeHashTable extends AbstractHashMap {
private MapEntry[] table;
private MapEntry DEFUNCT = new MapEntry(null, null);

private int ncollisions = 0;
public ProbeHashTable() {super();}
public ProbeHashTable(int cap,int p) {super(cap, p); }
private boolean compareStr(String s, String t) {
boolean result = s.equals(t);
if (!result)
ncollisions++;
return result;
}
protected void createTable() {
table = (MapEntry[]) new MapEntry[capacity]; }

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 = i;
}
if(table[i] == null) {
   break;
} }
else if(compareStr(table[i].getKey(), 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((String) value);
table[-(i + 1)] = new MapEntry((String) key, (String) value);
n++;
return null;
}
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) key);
if(i < 0)
return null;
Object answer = table[i].getValue();
table[i] = DEFUNCT;
n--;
return answer;
}
private class KeyIterable implements Iterable{

public Iterator iterator() {
ArrayList buffer = new ArrayList(n);
for(int i = 0; i < capacity; i++)
try {
if(!isAvailable(i))
buffer.add(buffer.size(), table[i].getKey());
}
catch(OutOfRangeException e) {
System.out.println("keySet: Out Of Range");
}
return new SArrayIterator(buffer);
}
public boolean isEmpty() {
       return false;
   }
   public int size() {
       return 0;
   } }
public Iterable keySet() {
return new KeyIterable();
}
public int getCollisions(){
return ncollisions;
}
public String toString() {
   String tableString = "";
   for(int i = 0; i < capacity; i++) {
   if(!isAvailable(i)) {
   String key = table[i].getKey();
   int tabValue = table[i].getValue().indexOf("\t");
   String value = table[i].getValue().substring(tabValue, tabValue + 3);
   tableString += hashValue(key) + " " + key + " " + value + "\n";
   }}
   return tableString;
}}