For Java

please implement hashed dictionary using the sample "HashedDictionary.java" with array implementation using separate chaining probing. Complete the add and the remove methods, write an inner class named TableEntry, and modify other statements/methods, as necessary. An interface (DictionaryInterface.java) and a test file (TestHashing.java) have also been provided along with the HashedDictionary.java class.

DictionaryInterface.java

import java.util.Iterator;

public interface DictionaryInterface { public V add(K key, V value); public V remove(K key); public V getValue(K key); public boolean contains(K key); public Iterator getKeyIterator(); public Iterator getValueIterator(); public boolean isEmpty(); public int getSize(); public void clear(); }

HashedDictionary.java

import java.util.Iterator; import java.util.NoSuchElementException;

public class HashedDictionary implements DictionaryInterface { // The dictionary private int numberOfEntries; private static final int DEFAULT_CAPACITY = 5; // must be prime private static final int MAX_CAPACITY = 10000; // The hash table private TableEntry[] hashTable; private int tableSize; private static final int MAX_SIZE = 2 * MAX_CAPACITY; private boolean initialized = false; private static final double MAX_LOAD_FACTOR = 0.5; // Fraction of hash table // that can be filled public HashedDictionary() { this(DEFAULT_CAPACITY); // Call next constructor } // end default constructor

public HashedDictionary(int initialCapacity) { checkCapacity(initialCapacity); numberOfEntries = 0; // Dictionary is empty // Set up hash table: // Initial size of hash table is same as initialCapacity if it is prime; // otherwise increase it until it is prime size int tableSize = getNextPrime(initialCapacity); checkSize(tableSize); // Check for max array size // The cast is safe because the new array contains null entries @SuppressWarnings("unchecked") TableEntry[] temp = (TableEntry[])new TableEntry[tableSize]; hashTable = temp; initialized = true; } // end constructor private void checkCapacity(int capacity) { if (capacity > MAX_CAPACITY) throw new IllegalStateException("Attempt to create an array whose capacity exceeds allowed " + "maximum of " + MAX_CAPACITY); } // end checkCapacity private int getNextPrime(int anInteger) { if (anInteger % 2 == 0) anInteger++; while (!isPrime(anInteger)) anInteger += 2; return anInteger; } private boolean isPrime(int anInteger) { boolean found = false; int d = 2; while (!found && (d <= anInteger / 2)) { found = anInteger % d == 0; d++; } return !found; } private void checkSize(int tableSize) { if (tableSize > MAX_CAPACITY) throw new IllegalStateException("Attempt to create an array whose capacity exceeds allowed " + "maximum of " + MAX_CAPACITY); } // end checkSize

public void display() { for (int index = 0; index < hashTable.length; index++) { if (hashTable[index] == null) System.out.println("null "); else if (hashTable[index].isRemoved()) System.out.println("Removed "); else System.out.println(hashTable[index].getKey() + " " + hashTable[index].getValue()); } // end for System.out.println(); } // end display public V add(K key, V value) { /* Enter your code here */ } // end add

private boolean isHashTableTooFull() { boolean notFull = false; int index = 0; while (!notFull && index < hashTable.length) { notFull = hashTable[index] == null; index++; } return !notFull; } private int probe(int index, K key) { boolean found = false; int removedStateIndex = -1; // Index of first location in removed state while (!found && (hashTable[index] != null)) { if (hashTable[index].isIn()) { if (key.equals(hashTable[index].getKey())) found = true; // Key found else // Follow probe sequence index = (index + 1) % hashTable.length; // Linear probing } else // Skip entries that were removed { // Save index of first location in removed state if (removedStateIndex == -1) removedStateIndex = index; index = (index + 1) % hashTable.length; // Linear probing } // end if } // end while // Assertion: Either key or null is found at hashTable[index] if (found || (removedStateIndex == -1)) return index; // Index of either key or null else return removedStateIndex; // Index of an available location } //end probe

//Precondition: checkInitialization has been called private void enlargeHashTable() { TableEntry[] oldTable = hashTable; int oldSize = hashTable.length; int newSize = getNextPrime(oldSize + oldSize); // The cast is safe because the new array contains null entries @SuppressWarnings("unchecked") TableEntry[] temp = (TableEntry[])new TableEntry[newSize]; hashTable = temp; numberOfEntries = 0; // Reset number of dictionary entries, since // it will be incremented by add during rehash // Rehash dictionary entries from old array to the new and bigger // array; skip both null locations and removed entries for (int index = 0; index < oldSize; index++) { if ((oldTable[index] != null) && oldTable[index].isIn()) add(oldTable[index].getKey(), oldTable[index].getValue()); } // end for } // end enlargeHashTable

public V remove(K key) { /* Enter your code here */ } // end remove

public V getValue(K key) { checkInitialization(); V result = null; int index = getHashIndex(key); index = locate(index, key);

if (index != -1) result = hashTable[index].getValue(); // key found; get value // Else key not found; return null return result; } // end getValue

private void checkInitialization() { if (!initialized) throw new SecurityException("Array object is not initialized properly."); } private int locate(int index, K key) { boolean found = false;

while (!found && (hashTable[index] != null)) { if (hashTable[index].isIn() && key.equals(hashTable[index].getKey())) found = true; // Key found else // follow probe sequence index = (index + 1) % hashTable.length; // Linear probing } // end while // Assertion: Either key or null is found at hashTable[index] int result = -1; if (found) result = index; return result; } // end locate public boolean contains(K key) { return getValue(key) != null; } // end contains

public boolean isEmpty() { return numberOfEntries == 0; } // end isEmpty

//public boolean isFull() //{ // return false; //} // end isFull

public int getSize() { return numberOfEntries; } // end getSize

public final void clear() { for (int index = 0; index < hashTable.length; index++) hashTable[index] = null;

numberOfEntries = 0; //locationsUsed = 0; } // end clear

public Iterator getKeyIterator() { return new KeyIterator(); } // end getKeyIterator public Iterator getValueIterator() { return new ValueIterator(); } // end getValueIterator private int getHashIndex(K key) { int hashIndex = key.hashCode() % hashTable.length; if (hashIndex < 0) { hashIndex = hashIndex + hashTable.length; } // end if

return hashIndex; } // end getHashIndex //private boolean isHashTableTooFull() //{ // return locationsUsed > MAX_LOAD_FACTOR * hashTable.length; //} // end isHashTableTooFull

private class KeyIterator implements Iterator { private int currentIndex; // current position in hash table private int numberLeft; // number of entries left in iteration

private KeyIterator() { currentIndex = 0; numberLeft = numberOfEntries; } // end default constructor public boolean hasNext() { return numberLeft > 0; } // end hasNext public K next() { K result = null; if (hasNext()) { // Skip table locations that do not contain a current entry while ((hashTable[currentIndex] == null) || hashTable[currentIndex].isRemoved()) currentIndex++; result = hashTable[currentIndex].getKey(); numberLeft--; currentIndex++; } else throw new NoSuchElementException(); return result; } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end KeyIterator private class ValueIterator implements Iterator { private int currentIndex; private int numberLeft; private ValueIterator() { currentIndex = 0; numberLeft = numberOfEntries; } // end default constructor public boolean hasNext() { return numberLeft > 0; } // end hasNext public V next() { V result = null; if (hasNext()) { while ((hashTable[currentIndex] == null) || hashTable[currentIndex].isRemoved()) currentIndex++; result = hashTable[currentIndex].getValue(); numberLeft--; currentIndex++; } else throw new NoSuchElementException();

return result; } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end ValueIterator

private static class TableEntry { /* Enter your code here */ } // end TableEntry } // end HashedDictionary2

TestHashing.java

import java.util.Iterator;

public class TestHashing { public static void main(String[] args) { testDictionary(); testHashTable(); System.out.println(" Done."); } // end main public static void testDictionary() { String dirk = "Dirk"; String abel = "Abel"; String miguel = "Miguel"; String tabbie = "Tabatha"; String tom = "Tom"; String sam = "Sam"; String reiss = "Reiss"; String bette = "Bette"; String carole = "Carole"; String derek = "Derek"; String nancy = "Nancy"; String bogus = "Bo";

// create a dictionary of initial size 11 DictionaryInterface nameList = new HashedDictionary();

System.out.println("Create a dictionary: "); System.out.println("Initial dictionary should be empty; isEmpty() returns " + nameList.isEmpty());

// test add System.out.println(" Testing add(): "); nameList.add(dirk, "555-1234"); nameList.add(abel, "555-5678"); nameList.add(miguel, "555-9012"); nameList.add(tabbie, "555-3456"); nameList.add(tom, "555-5555"); nameList.add(sam, "555-7890"); nameList.add(reiss, "555-2345"); nameList.add(bette, "555-7891"); nameList.add(carole, "555-7892"); nameList.add(derek, "555-7893"); nameList.add(nancy, "555-7894");

System.out.println(nameList.getSize() + " (should be 11) items in dictionary, as follows: "); display(nameList);

// test getValue System.out.println(" Testing getValue(): "); System.out.println(" Abel: " + nameList.getValue(abel) + " should be 555-5678"); System.out.println(" Sam: " + nameList.getValue(sam) + " should be 555-7890"); System.out.println(" Tom: " + nameList.getValue(tom) + " should be 555-5555"); System.out.println(" Reiss: " + nameList.getValue(reiss) + " should be 555-2345"); System.out.println(" Miguel: " + nameList.getValue(miguel) + " should be 555-9012");

// test contains System.out.println(" Testing contains(): ");

if ( nameList.contains(sam) ) System.out.println(" Sam is in dictionary - OK"); else System.out.println("Error in contains()");

if ( nameList.contains(abel) ) System.out.println(" Abel is in dictionary - OK"); else System.out.println("Error in contains()");

if ( nameList.contains(miguel) ) System.out.println(" Miguel is in dictionary - OK"); else System.out.println("Error in contains()");

if ( nameList.contains(tom) ) System.out.println(" Tom is in dictionary - OK"); else System.out.println("Error in contains()");

if (!nameList.contains(bogus)) System.out.println(" Bo is not in dictionary - OK"); else System.out.println("Error in contains()");

// remove first item System.out.println(" Removing first item Dirk - Dirk's number is " + nameList.remove(dirk) + " should be 555-1234");

// test replacing value System.out.println("Replacing phone number of Reiss and Miguel: "); String oldNumber = nameList.add(reiss, "555-5432"); System.out.println("Reiss's old number " + oldNumber + " is replaced by 555-5432"); oldNumber = nameList.add(miguel, "555-2109"); System.out.println("Miguel's old number " + oldNumber + " is replaced by 555-2109");

System.out.println(" " + nameList.getSize() + " (should be 10) items in dictionary, as follows: "); display(nameList);

// remove interior and last items System.out.println(" Removing interior item Reiss and last item Nancy: "); System.out.println(" Reiss's number is " + nameList.remove(reiss) + " should be 555-5432"); System.out.println(" Nancy's number is " + nameList.remove(nancy) + " should be 555-7894");

// remove Bo (not in dictionary) System.out.println(" Removing Bo (not in dictionary): "); String result = nameList.remove(bogus); if (result == null) System.out.println("Bo was not found in the dictionary."); else System.out.println("Error in remove().");

System.out.println(" " + nameList.getSize() + " (should be 8) items in dictionary, as follows: "); display(nameList);

// test clear System.out.println(" Testing clear(): "); nameList.clear();

System.out.println("Dictionary should be empty; isEmpty() returns " + nameList.isEmpty()); } // testDictionary /** Tests the hash table when no locations contain null */ public static void testHashTable() { // declaring the type of nameList as HashedDictionary2 instead of DictionaryInterface // enables us to use the display method defined in HashedDictionary2 HashedDictionary nameList = new HashedDictionary(11);

System.out.println(" ----------------------------------------------------------------------- "); System.out.println("testHashTable():");

System.out.println("Create a dictionary whose initial hash table has 11 locations: "); System.out.println("Initial dictionary should be empty; isEmpty() returns " + nameList.isEmpty());

// add 5 names - rehashing will not occur, since the load factor will be < 0.5 System.out.println(" Testing add() - add 5 names: "); nameList.add("Tabatha", "555-1234"); nameList.add("Toni", "555-1235"); nameList.add("Tobbie", "555-1236"); nameList.add("Tabbie", "555-1237"); nameList.add("Tim", "555-1238");

System.out.println("Dictionary should not be full; isFull() returns " + nameList.isFull() + " "); System.out.println("Dictionary contains " + nameList.getSize() + " (should be 5) items, as follows: "); display2(nameList);

System.out.println(" The hash table is: "); nameList.display(); // display hash table [METHOD ADDED TO CLASS FOR TESTING PURPOSES]

// We now remove a name and add a name, so the table size remains the same. Our goal is to // remove null from all table locations. Then we will test the method contains() in this situation.

System.out.println(" Remove Tabatha, add Nancy: "); nameList.remove("Tabatha"); nameList.add("Nancy", "555-1239"); System.out.println(" The hash table is: "); nameList.display();

System.out.println(" Remove Toni, add Derek: "); nameList.remove("Toni"); nameList.add("Derek", "555-1240"); System.out.println(" The hash table is: "); nameList.display();

System.out.println(" Remove Tabbie, add Carole: "); nameList.remove("Tabbie"); nameList.add("Carole", "555-1241"); System.out.println(" The hash table is: "); nameList.display();

System.out.println(" Remove Tobbie, add Bette: "); nameList.remove("Tobbie"); nameList.add("Bette", "555-1242"); System.out.println(" The hash table is: "); nameList.display();

System.out.println(" Remove Tim, add Reiss: "); nameList.remove("Tim"); nameList.add("Reiss", "555-1243"); System.out.println(" The hash table is: "); nameList.display();

System.out.println(" Remove Tim, add Miguel: "); nameList.remove("Tim"); nameList.add("Miguel", "555-1244"); System.out.println(" The hash table is: "); nameList.display();

System.out.println(" Remove Bette, add Tom: "); nameList.remove("Bette"); nameList.add("Tom", "555-1245"); System.out.println(" The hash table is: "); nameList.display();

System.out.println(" Locate Reis, Carole, Nancy, and Zeke: "); if (nameList.contains("Reiss")) System.out.println("Reis is in the dictionary "); else System.out.println("Reis is NOT in the dictionary: ERROR ");

if (nameList.contains("Carole")) System.out.println("Carole is in the dictionary "); else System.out.println("Carole is NOT in the dictionary: ERROR ");

if (nameList.contains("Nancy")) System.out.println("Nancy is in the dictionary "); else System.out.println("Nancy is NOT in the dictionary: ERROR ");

if (nameList.contains("Zeke")) System.out.println("Zeke is in the dictionary: ERROR "); else System.out.println("Zeke is NOT in the dictionary "); } // end testHashTable

public static void display(DictionaryInterface dictionary) { Iterator keyIterator = dictionary.getKeyIterator(); Iterator valueIterator = dictionary.getValueIterator();

while (keyIterator.hasNext() && valueIterator.hasNext()) System.out.println(keyIterator.next() + " : " + valueIterator.next()); System.out.println(); } // end display

public static void display2(DictionaryInterface dictionary) { Iterator keyIterator = dictionary.getKeyIterator(); Iterator valueIterator = dictionary.getValueIterator();

while (keyIterator.hasNext() && valueIterator.hasNext()) System.out.println(keyIterator.next() + " : " + valueIterator.next()); System.out.println(); } // end display2 } // end TestHashing