Implement using the sample \"HashedDictionary\" with array implementation using
ID: 3571547 • Letter: I
Question
Implement using the sample "HashedDictionary" with array implementation using separate chaining probing.Basically turn from linear probing to seperate chaining. Please submit your version of HashedDictionary.java and keep original DictionaryInterface.java and TestHashing.java files from sample programs.I have provided downloads or you can copy and paste..
TestHashing.java download:
https://ufile.io/6b285
DictionaryInterface.java download:
https://ufile.io/753b6
HashedDictionary.java download:
https://ufile.io/22ae4
Here is the 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();
}
Here is the 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("notIn ");
else
System.out.println(hashTable[index].getKey() + " " + hashTable[index].getValue());
} // end for
System.out.println();
} // end display
public V add(K key, V value)
{
checkInitialization();
if ((key == null) || (value == null))
throw new IllegalArgumentException();
else
{
V oldValue; // value to return
int index = getHashIndex(key);
index = probe(index, key); // Check for and resolve collision
// Assertion: index is within legal range for hashTable
assert (index >= 0) && (index < hashTable.length);
if ((hashTable[index] == null) || hashTable[index].isRemoved())
{ // key not found, so insert new entry
hashTable[index] = new TableEntry<>(key, value);
numberOfEntries++;
oldValue = null;
}
else
{ // key found; get old value for return and then replace it
oldValue = hashTable[index].getValue();
hashTable[index].setValue(value);
} // end if
// Ensure that hash table is large enough for another add
if (isHashTableTooFull()) enlargeHashTable();
return oldValue;
} // end if
} // end add
private boolean isHashTableTooFull()
{
boolean notFull = false;
int index = 0;
while (!notFull && index < hashTable.length)
{
notFull = hashTable[index] == null;
index++;
}
System.out.println("index: " + index + " full? " + !notFull);
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);
System.out.println("old hashTable size: " + oldSize + " new hashTable size: " + newSize);
// 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)
{
checkInitialization();
V removedValue = null;
int index = getHashIndex(key);
index = locate(index, key);
if (index != -1)
{// Key found; flag entry as removed and return its value
removedValue = hashTable[index].getValue();
hashTable[index].setToRemoved();
numberOfEntries--;
} // end if
// Else key not found; return null
return removedValue;
} // 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
{
private S key;
private T value;
private States state; // Flags whether this entry is in the hash table
private enum States {CURRENT, REMOVED} // Posssible values of state
//private boolean inTable; // true if entry is in table
private TableEntry(S searchKey, T dataValue)
{
key = searchKey;
value = dataValue;
state = States.CURRENT;
} // end constructor
private S getKey()
{
return key;
} // end getKey
private T getValue()
{
return value;
} // end getValue
private void setValue(T newValue)
{
value = newValue;
} // end setValue
private boolean isIn()
{
//return inTable;
return state == States.CURRENT;
} // end isIn
private boolean isRemoved() // opposite of isIn
{
//return !inTable;
return state == States.REMOVED;
} // end isRemoved
// state = true means entry in use; false means entry not in use, ie deleted
private void setToRemoved()
{
key = null;
value = null;
//inTable = false;
state = States.REMOVED;
} // end setToRemoved
private void setToIn() // not used
{
//inTable = true;
state = States.CURRENT;
} // end setToIn
} // end TableEntry
} // end HashedDictionary2
Here is the 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
Explanation / Answer
public class Entry<K, V> {
K key;
V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K key() {
return key;
}
public V value() {
return value;
}
@Override
public String toString() {
return "(" + key + ", " + value + ")";
}
@Override
public boolean equals(Object obj) {
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Entry<K, V> other = (Entry<K, V>) obj;
if (this.key != other.key && (this.key == null || !this.key.equals(other.key)))
return false;
if (this.value != other.value && (this.value == null || !this.value.equals(other.value)))
return false;
return true;
}
@Override
public int hashCode() {
int hash = 7;
hash = 23 * hash + (this.key != null ? this.key.hashCode() : 0);
hash = 23 * hash + (this.value != null ? this.value.hashCode() : 0);
return hash;
}
}