The assignment is to modify HashedDictionary.java to implement the ADT dictionar
ID: 3837763 • Letter: T
Question
The assignment is to modify HashedDictionary.java to
implement the ADT dictionary by using hashing and separate chaining. Use a chain of linked nodes as
each bucket. The dictionary’s entries should have distinct search keys.
Included are files DictionaryInterface.java and Driver.java. These files are not to be changed, use them
as is. Also included is HashedDictionary.java, this file for your reference.
I have made a copy of HashedDictionary.java and named the copy HashedDictionarySC.java, this is
the file you will modify to implement the separate chaining. I have modified it to remove the inner
class TableEntry<S, T> and replaced it with Node<S, T>. I also fixed the formatting.
You will need to create an array of Nodes which will be the hash table. As you are making the changes
to the methods in this class remember that the array is an array of nodes, the elements of which initially
are all set to null. Items added to the array are also nodes. As nodes with the same index are added to
the table then the nodes form a linked list with the first node in the array element. So when accessing a
particular value, the index into the array has to be determined, and then the chain at that index must be
searched.
One more tip: you will not need the probe method, it can be deleted.
Executing the driver should produce the same output as is shown at the end of the Driver file.
===============CODE=================
@@@@@@Driver.java
import java.util.Iterator;
/**
A driver that demonstrates the class HashedDictionarySC.
@author Frank M. Carrano
@version 4.0
*/
public class Driver
{
public static void main(String[] args)
{
testDictionary();
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<String, String> nameList = new HashedDictionarySC<>();
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 Abel - Abel's number is " +
nameList.remove(abel) + " should be 555-5678");
// 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: ");
nameList.remove(reiss);
System.out.println(" " + nameList.getSize() +
" (should be 9) items in dictionary, as follows: ");
display(nameList);
System.out.println(" Removing last item Nancy: ");
nameList.remove(nancy);
System.out.println(" " + nameList.getSize() +
" (should be 8) items in dictionary, as follows: ");
display(nameList);
// 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
public static void display(DictionaryInterface<String, String> dictionary)
{
Iterator<String> keyIterator = dictionary.getKeyIterator();
Iterator<String> valueIterator = dictionary.getValueIterator();
while (keyIterator.hasNext() && valueIterator.hasNext())
System.out.println(keyIterator.next() + " : " + valueIterator.next());
System.out.println();
} // end display
} // end Driver
/*
Create a dictionary:
Initial dictionary should be empty; isEmpty() returns true
Testing add():
11 (should be 11) items in dictionary, as follows:
Tom : 555-5555
Dirk : 555-1234
Derek : 555-7893
Miguel : 555-9012
Sam : 555-7890
Abel : 555-5678
Tabatha : 555-3456
Carole : 555-7892
Bette : 555-7891
Reiss : 555-2345
Nancy : 555-7894
Testing getValue():
Abel: 555-5678 should be 555-5678
Sam: 555-7890 should be 555-7890
Tom: 555-5555 should be 555-5555
Reiss: 555-2345 should be 555-2345
Miguel: 555-9012 should be 555-9012
Testing contains():
Sam is in dictionary - OK
Abel is in dictionary - OK
Miguel is in dictionary - OK
Tom is in dictionary - OK
Bo is not in dictionary - OK
Removing first item Abel - Abel's number is 555-5678 should be 555-5678
Replacing phone number of Reiss and Miguel:
Reiss's old number 555-2345 is replaced by 555-5432
Miguel's old number 555-9012 is replaced by 555-2109
10 (should be 10) items in dictionary, as follows:
Tom : 555-5555
Dirk : 555-1234
Derek : 555-7893
Miguel : 555-2109
Sam : 555-7890
Tabatha : 555-3456
Carole : 555-7892
Bette : 555-7891
Reiss : 555-5432
Nancy : 555-7894
Removing interior item Reiss:
9 (should be 9) items in dictionary, as follows:
Tom : 555-5555
Dirk : 555-1234
Derek : 555-7893
Miguel : 555-2109
Sam : 555-7890
Tabatha : 555-3456
Carole : 555-7892
Bette : 555-7891
Nancy : 555-7894
Removing last item Nancy:
8 (should be 8) items in dictionary, as follows:
Tom : 555-5555
Dirk : 555-1234
Derek : 555-7893
Miguel : 555-2109
Sam : 555-7890
Tabatha : 555-3456
Carole : 555-7892
Bette : 555-7891
Removing Bo (not in dictionary):
Bo was not found in the dictionary.
8 (should be 8) items in dictionary, as follows:
Tom : 555-5555
Dirk : 555-1234
Derek : 555-7893
Miguel : 555-2109
Sam : 555-7890
Tabatha : 555-3456
Carole : 555-7892
Bette : 555-7891
Testing clear():
Dictionary should be empty; isEmpty() returns true
Done.
*/
@@@@@@DictionaryInterface.java
import java.util.Iterator;
/**
An interface for a dictionary with distinct search keys.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
public interface DictionaryInterface<K, V>
{
/** Adds a new entry to this dictionary. If the given search key already
exists in the dictionary, replaces the corresponding value.
@param key An object search key of the new entry.
@param value An object associated with the search key.
@return Either null if the new entry was added to the dictionary
or the value that was associated with key if that value
was replaced. */
public V add(K key, V value);
/** Removes a specific entry from this dictionary.
@param key An object search key of the entry to be removed.
@return Either the value that was associated with the search key
or null if no such object exists. */
public V remove(K key);
/** Retrieves from this dictionary the value associated with a given
search key.
@param key An object search key of the entry to be retrieved.
@return Either the value that is associated with the search key
or null if no such object exists. */
public V getValue(K key);
/** Sees whether a specific entry is in this dictionary.
@param key An object search key of the desired entry.
@return True if key is associated with an entry in the dictionary. */
public boolean contains(K key);
/** Creates an iterator that traverses all search keys in this dictionary.
@return An iterator that provides sequential access to the search
keys in the dictionary. */
public Iterator<K> getKeyIterator();
/** Creates an iterator that traverses all values in this dictionary.
@return An iterator that provides sequential access to the values
in this dictionary. */
public Iterator<V> getValueIterator();
/** Sees whether this dictionary is empty.
@return True if the dictionary is empty. */
public boolean isEmpty();
/** Gets the size of this dictionary.
@return The number of entries (key-value pairs) currently
in the dictionary. */
public int getSize();
/** Removes all entries from this dictionary. */
public void clear();
} // end DictionaryInterface
@@@@@@HashedDictionarySC.java
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
A class that implements the ADT dictionary by using hashing and
linear probing to resolve collisions.
The dictionary is unsorted and has distinct search keys.
Notes: Uses probe for add, remove, and getValue, as described in the
answer to Self-Test Question 4 in Chapter 19.
Uses linear probing, but includes code for quadratic probing.
Has a display method for illustration and testing.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
public class HashedDictionarySC<K, V> implements DictionaryInterface<K, V>
{
// 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<K, V>[] hashTable;
private int tableSize; // Must be prime
private static final int MAX_SIZE = 2 * MAX_CAPACITY;
private boolean initialized = false;
// Fraction of hash table that can be filled:
private static final double MAX_LOAD_FACTOR = 0.5;
public HashedDictionarySC()
{
this(DEFAULT_CAPACITY); // Call next constructor
} // end default constructor
public HashedDictionarySC(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);
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
TableEntry<K, V>[] temp = (TableEntry<K, V>[])new TableEntry[tableSize];
hashTable = temp;
initialized = true;
} // end constructor
public void displayHashTable()
{
checkInitialization();
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 state");
else
System.out.println(hashTable[index].getKey() + " " + hashTable[index].getValue());
} // end for
System.out.println();
} // end displayHashTable
public V add(K key, V value)
{
checkInitialization();
if ((key == null) || (value == null))
throw new IllegalArgumentException(
"Cannot add null to a dictionary.");
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
public V remove(K key)
{
checkInitialization();
V removedValue = null;
int index = getHashIndex(key);
index = probe(index, key);
if ((hashTable[index] != null) && hashTable[index].isIn())
{
// Key found; flag entry as removed and return its value
removedValue = hashTable[index].getValue();
hashTable[index].setToRemoved();
numberOfEntries--;
} // end if
// Else not found; result is null
return removedValue;
} // end remove
public V getValue(K key)
{
checkInitialization();
V result = null;
int index = getHashIndex(key);
index = probe(index, key);
if ((hashTable[index] != null) && hashTable[index].isIn())
result = hashTable[index].getValue(); // Key found; get value
// Else not found; result is null
return result;
} // end getValue
public boolean contains(K key)
{
return getValue(key) != null;
} // end contains
public boolean isEmpty()
{
return numberOfEntries == 0;
} // end isEmpty
public int getSize()
{
return numberOfEntries;
} // end getSize
public final void clear()
{
checkInitialization();
for (int index = 0; index < hashTable.length; index++)
hashTable[index] = null;
numberOfEntries = 0;
//locationsUsed = 0;
} // end clear
public Iterator<K> getKeyIterator()
{
return new KeyIterator();
} // end getKeyIterator
public Iterator<V> 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
// Precondition: checkInitialization has been called.
private int probe(int index, K key)
{
boolean found = false;
int removedStateIndex = -1; // Index of first location in removed state
//int increment = 1; // For quadratic probing **********
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
// Quadratic probing **********
//index = (index + increment) % hashTable.length;
// Odd values for quadratic probing **********
//increment = increment + 2;
}
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
// Quadratic probing **********
//index = (index + increment) % hashTable.length;
// Odd values for quadratic probing **********
//increment = increment + 2;
} // 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
// Increases the size of the hash table to a prime >= twice its old size.
// In doing so, this method must rehash the table entries.
// Precondition: checkInitialization has been called.
private void enlargeHashTable()
{
TableEntry<K, V>[] oldTable = hashTable;
int oldSize = hashTable.length;
int newSize = getNextPrime(oldSize + oldSize);
checkSize(newSize);
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
// Increase size of array
TableEntry<K, V>[] tempTable =
(TableEntry<K, V>[])new TableEntry[newSize];
hashTable = tempTable;
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
// Returns true if lambda > MAX_LOAD_FACTOR for hash table;
// otherwise returns false.
private boolean isHashTableTooFull()
{
return numberOfEntries > MAX_LOAD_FACTOR * hashTable.length;
} // end isHashTableTooFull
// Returns a prime integer that is >= the given integer.
private int getNextPrime(int integer)
{
// if even, add 1 to make odd
if (integer % 2 == 0)
{
integer++;
} // end if
// test odd integers
while (!isPrime(integer))
{
integer = integer + 2;
} // end while
return integer;
} // end getNextPrime
// Returns true if the given intege is prime.
private boolean isPrime(int integer)
{
boolean result;
boolean done = false;
// 1 and even numbers are not prime
if ( (integer == 1) || (integer % 2 == 0) )
{
result = false;
}
// 2 and 3 are prime
else if ( (integer == 2) || (integer == 3) )
{
result = true;
}
else // integer is odd and >= 5
{
assert (integer % 2 != 0) && (integer >= 5);
// a prime is odd and not divisible by every odd
// integer up to its square root
result = true; // assume prime
for (int divisor = 3;
!done && (divisor * divisor <= integer);
divisor = divisor + 2)
{
if (integer % divisor == 0)
{
result = false; // divisible; not prime
done = true;
} // end if
} // end for
} // end if
return result;
} // end isPrime
// Throws an exception if this object is not initialized.
private void checkInitialization()
{
if (!initialized)
throw new SecurityException ("HashedDictionary object is not " +
"initialized properly.");
} // end checkInitialization
// Ensures that the client requests a capacity
// that is not too small or too large.
private void checkCapacity(int capacity)
{
if (capacity < DEFAULT_CAPACITY)
capacity = DEFAULT_CAPACITY;
else if (capacity > MAX_CAPACITY)
throw new IllegalStateException("Attempt to create a dictionary " +
"whose capacity is larger than " +
MAX_CAPACITY);
} // end checkCapacity
// Throws an exception if the hash table becomes too large.
private void checkSize(int size)
{
if (tableSize > MAX_SIZE)
throw new IllegalStateException("Dictionary has become too large.");
} // end checkSize
private class KeyIterator implements Iterator<K>
{
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++;
} // end while
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<V>
{
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())
{
// Skip table locations that do not contain a current entry
while ( (hashTable[currentIndex] == null) ||
hashTable[currentIndex].isRemoved() )
{
currentIndex++;
} // end while
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 class Node<S, T>
{
private S key;
private T value;
private Node<S, T> next;
private Node(S searchKey, T dataValue)
{
key = searchKey;
value = dataValue;
next = null;
} // end constructor
private Node(S searchKey, T dataValue, Node<S, T> nextNode)
{
key = searchKey;
value = dataValue;
next = nextNode;
} // end constructor
private S getKey()
{
return key;
} // end getKey
private T getValue()
{
return value;
} // end getValue
// No setKey method!!*****
private void setValue(T newValue)
{
value = newValue;
} // end setValue
private Node<S, T> getNextNode()
{
return next;
} // end getNextNode
private void setNextNode(Node<S, T> nextNode)
{
next = nextNode;
} // end setNextNode
} // end Node
} // end HashedDictionary2
Explanation / Answer
import java.util.Scanner; /* Node for singly linked list */ class SLLNode { SLLNode next; int data; /* Constructor */ public SLLNode(int x) { data = x; next = null; } } /* Class HashTableChainingSinglyLinkedList */ class HashTableChainingSinglyLinkedList { private SLLNode[] table; private int size ; /* Constructor */ public HashTableChainingSinglyLinkedList(int tableSize) { table = new SLLNode[ nextPrime(tableSize) ]; size = 0; } /* Function to check if hash table is empty */ public boolean isEmpty() { return size == 0; } /* Function to clear hash table */ public void makeEmpty() { int l = table.length; table = new SLLNode[l]; size = 0; } /* Function to get size */ public int getSize() { return size; } /* Function to insert an element */ public void insert(int val) { size++; int pos = myhash(val); SLLNode nptr = new SLLNode(val); if (table[pos] == null) table[pos] = nptr; else { nptr.next = table[pos]; table[pos] = nptr; } } /* Function to remove an element */ public void remove(int val) { int pos = myhash(val); SLLNode start = table[pos]; SLLNode end = start; if (start.data == val) { size--; table[pos] = start.next; return; } while (end.next != null && end.next.data != val) end = end.next; if (end.next == null) { System.out.println(" Element not found "); return; } size--; if (end.next.next == null) { end.next = null; return; } end.next = end.next.next; table[pos] = start; } /* Function myhash */ private int myhash(Integer x ) { int hashVal = x.hashCode( ); hashVal %= table.length; if (hashVal < 0) hashVal += table.length; return hashVal; } /* Function to generate next prime number >= n */ private static int nextPrime( int n ) { if (n % 2 == 0) n++; for ( ; !isPrime( n ); n += 2); return n; } /* Function to check if given number is prime */ private static boolean isPrime( int n ) { if (n == 2 || n == 3) return true; if (n == 1 || n % 2 == 0) return false; for (int i = 3; i * iRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.