You will implement a version of the cuckoo hash table. Your cuckoo hash will operate as follows You will use a single backing array(instead of two) and two hash functions (both MultiplicativeHashFunction objects), h1 and h2. The z values for your hash functions (and all subsequent hash functions needed when resizing or rehashing) will be taken from an array of integers passed to the CuckooHashTable constructor. The first value in the array will be used for the first incarnation of h1, the second value for the first incarnation of h2, the next two values will be used for the next incarnations of h1 and h2, etc. Note: be careful to follow this. We will be checking your array (via toString()) and correctness will depend on using the same values of z as we do when generating the test code. The MultiplicativeHashFunction objects you will use also have a getParams() method to show the value of z,w,d when that hash function is used. When adding an item, x, that is not in the hash table already, always add it to t[h1(x)] (even if t[h1(x)] is already taken and t[h2(x)] is available). The load factor must always satisfy =n/t.length1/2. If adding an item will violate this then resize the table (doubling its size) and rehash everything (before doing the add). After removing an item, if the load factor satisfies =n/t.length<1>

CuckooHashTable.java/**

* This class implements the cuckoo hash * * See: Rasmus Pagh, Flemming Friche Rodler, Cuckoo Hashing, Algorithms - ESA 2001, * Lecture Notes in Computer Science 2161, Springer 2001, ISBN 3-540-42493-8 * * @param */ public abstract class CuckooHashTable extends OpenAddressHashTable { /* add any attributes you may need here */ C MultiplicativeHashFunction h2 = null; /** * Create a new empty hash table * @param clazz is the class of the data to be stored in the hash table * @param zz is an array of integer values to be used for the has functions */ public CuckooHashTable(Class clazz, int[] zz) { // // add your code for the constructor here // } /* define all abstract methods inherited from parent class here */ }

OpenAddressHashTable.java import java.util.Iterator; import java.util.List; import java.util.Random; public abstract class OpenAddressHashTable implements USet { protected Factory f; /** the backing array */ protected T[] t; /** The "dimension" of the virtual table (t.length = 2^d) */ protected int d; /** The number of elements in the hash table */ protected int n; /** The number of bits in an int */ protected static final int w = 32; /** create a new hash table */ @SuppressWarnings("unchecked") public OpenAddressHashTable(Class clazz) { f = new Factory((Class)clazz.getClass()); d = 1; t = f.newArray(1< } /** * Resize the table */ protected abstract void resize(); /** * Clear the table (i.e., empty the table of all items) */ public void clear() { n = 0; d = 1; t = f.newArray(1< } /** * Return the number of elements stored in this hash table */ public int size() { return n; } /** * Adds element x to the table if there does not already exist an item y * in the table such that x.equals(y) is true. * * @param x is the item to add to the table * @return true if x is successfully added to the table, returns false if there already * an item y in the table such that x.equals(y) is true. */ public abstract boolean add(T x); /** * Remove the copy of x stored in this table if it exists. * @param x the item to remove * @return the element y stored in the table such that x.equals(y) is true, * or null if no such element y exists */ public abstract T remove(T x); /** * Get the copy of x stored in this table. * @param x - the item to get * @return - the element y stored in this table such that x.equals(y) * is true, or null if no such element y exists */ public abstract T find(Object x); @Override public final String toString(){ return java.util.Arrays.toString(t); } /** * Iterator for the hash table. You can implement your own if you wish but * this is not necessary and will not be tested. */ public Iterator iterator() { return null; } }

USet.Java public interface USet extends Iterable { public int size(); public boolean add(T x); public T remove(T x); public T find(T x); public void clear(); }

MultiplicativeHashFunctions.java /** * Multiplicative hash function from ODS 5.1.1 * hash(x) returns ((x.hashCode() * z) mod 2^w) div 2^(w-d) */ public class MultiplicativeHashFunction{ private int z; private int w; private int d; public MultiplicativeHashFunction(int zz, int ww, int dd){ this.z = zz; this.w = ww; this.d = dd; } public int[] getParams(){ return new int[]{z,w,d}; } public int hash(Object x){ return (z * x.hashCode()) >>> (w-d); } /* not used public int hash(int y){ return (z * y) >>> (w-d); } */ @Override public String toString(){ return "(z,w,d)=(" + z + "," + w + "," + d + ")"; } }