n this assignment you will implement three types of hash tables. Download the attached Main.java and SymbolTable.java les. The first file defines some tests for the symbol tables, the second is the symbol table interface.

• Write a class called TwoProbeChainHT that implements a two-probe separate chaining hashtable. Two-probe hashing means that you will hash to two positions, and insert the key in the shorter of the two chains.

Proper hash calculations.

∗ For the rst hash function, use the one given in the slides: hash(k)=(k.hashCode() & 0x7 f) %M

∗ For the second hash function, use: hash2(k)= (((k.hashCode() & 0x7 f) % M) * 31) % M

∗ Use Java’s LinkedList class to store each chain.

1

Figure 1: Sample Hashtable Implementation UML

∗ Do not use parallel arrays.

void put(Key key, Value val) – see interface. [8 points]Value get(Key key) – see interface.

void delete(Key key) – see interface.

• Write a class called LinearProbingHT that implements a linear probe hashtable.

Proper hash calculations. [4 points]

∗ Use the basic hash function given in the slides: hash(k)=(k.hashCode() & 0x7 f) % M, each time there is a collision, increase the hash by 1.

· An alternative way to structure this hash function is: hash(k, i) = ((k.hashCode() & 0x7 f) + i) % M, where k is the key and i is the number of collisions.

∗ An example hash sequence might look like: 43587, 43588, 43589, 43590, 43581…∗ Do not use parallel arrays.

LinearProbingHT() – a constructor that defaults to an array of size 997.

void put(Key key, Value val) – see interface.

Value get(Key key) – see interface.

void delete(Key key) – see interface. Do not degrade performance by using tags or extra nulls; you must update the probe sequence containing the element being deleted.

boolean contains(Key key) –

boolean isEmpty() –

int size() –

Iterable<Key> keys() –

There is no requirement to support array resizing.

2

• Write a class called QuadProbingHT that implements a linear probe hashtable. [8 points]Inherit all the functionality but the hash function from LinearProbingHT.

Use the following hash function: hash(k, i) = ((k.hashCode() & 0x7 f) + i*i) % M, where k is the key and i is the number of collisions.

An example hash sequence might look like: 43587, 43588, 43591, 43596, 43603…

• All three classes must implement the SymbolTable interface.

• Do not import any packages other than Queue or LinkedList in your hashtable implementations.

Please find main.java below

java.util.Arrays; java.util.HashSet; java.util.Set;/** * Symbol table testing ground. * * (your name), Acuna * (version) */ { args the command line arguments*/ {System.out.println();testIntegers( TwoProbeChainHT<Integer, Integer>());testStrings( TwoProbeChainHT<String, Integer>());System.out.println();testIntegers( LinearProbingHT<Integer, Integer>());testStrings( LinearProbingHT<String, Integer>());System.out.println();testIntegers( QuadProbingHT<Integer, Integer>());testStrings( QuadProbingHT<String, Integer>());} st An object implementing a symbol table.*/ {System.out.println();System.out.println();Set<Integer> keys = HashSet<>(Arrays.asList(-, -, -, -, -, , , , , , ));st.put(-, );st.put(-, );st.put(-, );st.put(-, );st.put(-, );st.put(, );st.put(, );st.put(, );st.put(, );st.put(, );: ;: ;(st.contains(-)) : ;: ;: ;(!st.contains(-)) : ;: ;(!st.contains()) : ;Set<Integer> stKeys = HashSet<>();(Integer i : st.keys())stKeys.add(i);: ;System.out.println(); size = st.size();st.put(, );: ;: ;: ;size = st.size();st.put(-, );: ;: ;: ;System.out.println();size = st.size();Integer ret = st.get();: ;: ;size = st.size();ret = st.get();: ;: ;System.out.println();size = st.size();st.delete();: ;: ;size = st.size();st.delete();: ;: ;System.out.println();} st An object implementing a symbol table.*/ {System.out.println();System.out.println();Set<String> keys = HashSet<>(Arrays.asList(, , , , , , , , , ));st.put(, );st.put(, );st.put(, );st.put(, );st.put(, );st.put(, );st.put(, );st.put(, );st.put(, );st.put(, );: ;: ;(st.contains()) : ;: ;: ;(!st.contains()) : ;: ;(!st.contains()) : ;Set<String> stKeys = HashSet<>();(String i : st.keys())stKeys.add(i);: ;System.out.println(); size = st.size();st.put(, );: ;: ;: ;size = st.size();st.put(, );: ;: ;: ;System.out.println();size = st.size();Integer ret = st.get();: ;: ;size = st.size();ret = st.get();: ;: ;System.out.println();size = st.size();st.delete();: ;: ;size = st.size();st.delete();: ;: ;System.out.println();}

}below is the symbolTable.java

/** * Symbol table interface. * * Sedgewick and Wayne, Acuna * <Key> search key * <Value> return type */ <, > { ;; ; ; ; ;;}