Task: Implementation of the ProbeHashTable class with linear probing.

(40%) ProbeHashTable.java: Implement the ProbeHashTable 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.

(20%) All other supporting classes given in the lecture, including AbstractHashMap.java, AbstractMap.java, MapEntry.java, ArrayList.java, List.java, OutOfRangeException.java, and SArrayIterator.java.

(30%) Test.java: write a test program to create a hash table with the default size (61). Inport 28 data items (given by a text file). The data file "roster.txt" is provided, which contains the offense 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 table in the format of tuples;

Obtain an iterable instance of key set and then print it out;

Print out the number of collisions occurred during the data insertion.

roster.txt below

Mayfield QB 23 6' 1" 215 lbs R Oklahoma Stanton QB 34 6' 3" 226 lbs 12 Michigan State Taylor QB 29 6' 1" 217 lbs 8 Virginia Tech Chubb RB 22 5' 11" 227 lbs R Georgia Hilliard RB 23 5' 11" 202 lbs R Tulane Johnson Jr. RB 25 5' 9" 210 lbs 4 Miami (FL) Callaway WR 21 5' 11" 200 lbs R Florida Higgins WR 24 6' 1" 198 lbs 3 Colorado State Landry WR 25 5' 11" 196 lbs 5 LSU Louis WR 24 6' 2" 215 lbs 3 Auburn Perriman WR 25 6' 2" 215 lbs 4 UCF Ratley WR 23 6' 2" 200 lbs R Texas A&M 'Mari Scott WR 23 6' 0" 205 lbs R Fresno State Streater WR 30 6' 2" 195 lbs 6 Temple Willies WR 24 6' 4" 207 lbs R Texas Tech Brown TE 24 6' 5" 246 lbs 1 Oregon Charles TE 27 6' 3" 257 lbs 3 Georgia DeValve TE 25 6' 3" 245 lbs 3 Princeton Fells TE 32 6' 7" 270 lbs 5 UC Irvine Njoku TE 22 6' 4" 246 lbs 2 Miami (FL) Hubbard C 27 6' 4" 295 lbs 5 UAB Tretter C 27 6' 4" 307 lbs 6 Cornell Bitonio G 27 6' 4" 305 lbs 5 Nevada Corbett G 23 6' 4" 306 lbs R Nevada Watford G 28 6' 3" 300 lbs 6 James Madison Zeitler G 28 6' 4" 315 lbs 7 Wisconsin Harrison OT 25 6' 6" 295 lbs R West Georgia Robinson OT 26 6' 5" 330 lbs 5 Auburn

AbstractHashMap.java below:

public abstract class AbstractHashMap extends AbstractMap{ protected int n=0; protected int capacity; private int prime; private long scale,offset; public AbstractHashMap(){this(61,999331);} public AbstractHashMap(int cap,int p){ this.capacity=cap; this.prime=p; Random rand=new Random(); this.scale=rand.nextInt(prime-1)+1; this.offset=rand.nextInt(prime); createTable(); } private 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(); 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); }

AbstractMap.java is below:

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(); }

MapEntry.java is below:

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 key){this.key=key;} public Object setValue(String value){ String old=this.value; this.value=value; return old; } public int hashCode(){ if(key==null)return 0; int h=0; for(int i=0;i>>27); h+=(int)key.charAt(i); } return h; }}

ArrayList.java is below:

public class ArrayList implements List{ private int CAP; private int size; private Object[] elements; public ArrayList(){ this(100); } public ArrayList(int capacity){ CAP=capacity; size=0; elements=new Object[capacity]; } public int size(){ return size; } public boolean isEmpty(){ return size==0; } public Object get(int i) throws OutOfRangeException{ if(isize) throw new OutOfRangeException(); for(int j=size-1; j>=i; j--){ } elements[i]=e; size++; } public Object remove(int i) throws OutOfRangeException{ if (i>=size) throw new OutOfRangeException("Out of Range Exception"); Object O=elements[i]; for (int j=i; j

List.java is below:

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

OutOfRangeException.java is below:

public class OutOfRangeException extends Exception { public OutOfRangeException(String str){ System.out.println("OutOfRangeException:" + str);} public OutOfRangeException (){ this("Out Of Range");} }

SArrayIterator.java is below:

import java.util.Iterator; public class SArrayIterator implements Iterator{ private ArrayList data; private int i=0; private boolean removable=false; public SArrayIterator(ArrayList list){ data=list; } public boolean hasNext(){return i

The template of ProbeHashTable class and relevant classes are given below:

public class ProbeHashTable extends AbstractHashMap { private MapEntry[] table; private MapEntry DEFUNCT = new MapEntry(null,null); private int count = 0; //constructors private boolean compareStr(String s, String t) { count++; return s.equals(t); } protected void createTable() { // your implementation here } private boolean isAvailable(int i) { // your implementation here } private int findSlot(int h, String k) { // your implementation here } protected Object bucketPut(int h, Object key, Object value) { // your implementation here } protected Object bucketGet(int h, Object key) { // your implementation here } protected Object bucketRemove(int h, Object key) { // your implementation here } private class KeyIterable implements Iterable { public Iterator iterator() { ArrayList buffer = new ArrayList(n); for (int i=0; i