Need help with this program. Question below followed by source code.

In this assignment you will implement two types of hash-based maps. Download the attached Driver.java, Map.java. The first file defines some tests for maps, the second is the map interface. Also included is ChainMap.java, which contains a sample implementation of a chaining hash-based map. Write a class called TwoProbeChainMap that implements a two-probe chaining hash-based map. Twoprobe hashing means that you will hash to two positions, and insert the key in the shorter of the two chains at those two positions. The easiest way to implement this class is to spend some time understanding ChainMap, and then redesign it to use the two probe technique. Proper hash calculations. For the first hash function, use: hash(k)=(k.hashCode() & 0x7f) % M. For the second hash function, use: hash2(k)= (((k.hashCode() & 0x7f) % M) * 31) % M. void put(Key key, Value val) - see interface. Value get(Key key) - see interface. void remove(Key key) - see interface. Write a class called LinearProbingMap that implements a linear probe hash-based map. [45 points total] Proper hash calculations. An decent way to structure the hash function is: hash(k, i) = ((k.hashCode() & 0x7f) + i) % M, where k is the key and i is the number of collisions. Each time there is a collision, i should be incremented so that the hash increases by 1. An example hash sequence might look like: 587, 588, 589, 590, 581... LinearProbingMap() - 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 remove(Key key) - although the interface has this function, you are not required to implement it. boolean contains(Key key) - see interface. boolean isEmpty() - see interface. int size() - see interface. Iterable keys() - see interface. There is no requirement to support array resizing. Both classes must implement the provided Map interface. Do not import any packages other than Queue or LinkedList in your map implementations. No testing report is required this time - test as much or as little as it takes to convince yourself that the implementations work.

***************************ChainMap*********************

import java.util.LinkedList; import java.util.Queue;

/** * A map (like) ADT implemented using a hashtable with chaining. * @author Acuna, Sedgewick and Wayne */ public class ChainMap implements Map { private class Entry { public Key key; public Value value; public Entry (Key k, Value v) { key = k; value = v; } } private int N; // number of key-value pairs private int M; // hash table size private LinkedList[] entries; public ChainMap() { this(997); } public ChainMap(int M) { this.N = 0; this.M = M; entries = new LinkedList[M]; for (int i = 0; i < M; i++) entries[i] = new LinkedList<>(); } private int hash(Key key) { return (key.hashCode() & 0x7fffffff) % M; } @Override public Value get(Key key) { for(Entry entry : entries[hash(key)]) if(key.hashCode() == entry.key.hashCode()) return entry.value; return null; } @Override public void put(Key key, Value val) { boolean added = false; for(Entry entry : entries[hash(key)]) if(key.hashCode() == entry.key.hashCode()) { entry.value = val; added = true; } if(!added) { entries[hash(key)].add(new Entry(key, val)); N++; } } @Override public int size() { return N; } @Override public boolean isEmpty() { return N == 0; } @Override public boolean contains(Key k) { return get(k) != null; } @Override public void remove(Key key) { if(contains(key)) { Entry target = null; for(Entry e : entries[hash(key)]) if(e.key == key) target = e; entries[hash(key)].remove(target); N--; } } @Override public Iterable keys() { Queue queue = new LinkedList<>(); for (int i = 0; i < M; i++) for(Entry e : entries[i]) queue.add(e.key); return queue; } }

****************************Map.java****************

/** * Map interface. * * @author Acuna * @param search key * @param return type */ public interface Map { /** * Puts a key-value pair into the map. * * @param key Key to use. * @param val Value to associate. */ void put(Key key, Value val); /** * Gets the value paired with a key. If the key doesn't exist in map, * returns null. * * @param key Key to use. * @return Value associated with key. */ Value get(Key key); /** * Removes a key (and its associated value) from the map. * * @param key Key to use. */ void remove(Key key); /** * Checks if the map contains a particular key. * * @param key True if map contains key, false otherwise. * @return Result of check. */ boolean contains(Key key); /** * Returns true if there are no key-vale pairs stored in the map, and false * otherwise. * * @return True if map is empty, false otherwise. */ boolean isEmpty(); /** * Returns the number of key-value pairs in the map. * * @return Number of key-value pairs. */ int size(); /** * Returns an Iterable object containing all keys in the table. Keys not * guaranteed to be in any particular order. * * @return Iterable object containing all keys. */ Iterable keys(); }

*****************Driver Class*************

import java.util.Arrays; import java.util.HashSet; import java.util.Set;

/** * Map testing ground. * * @author (your name), Acuna * @version (version) */ public class Driver { /** * Entry point for testing. * * @param args the command line arguments */ public static void main(String[] args) {

System.out.println("ChainMap: "); testStrings(new ChainMap()); System.out.println("TwoProbeChainMap: "); testStrings(new TwoProbeChainMap());

System.out.println("LinearProbingMap: "); testStrings(new LinearProbingMap()); } /** * Test string operations on symbol table implementation. No JUnit; ugly. * Make assertions are enabled before using this method. * * @param m An object implementing a symbol table. */ public static void testStrings(Map m) { System.out.println("*STRING TESTING*"); System.out.println(" Testing creation and basic methods... "); //populate initial symbol table. Set keys = new HashSet<>(Arrays.asList("DFKDJSFS", "DAFDW", "XZC", "adsfas", "a", "B", "112323", "