Use the KeyedListWithIterators.java generic to develop a SortedListWithIterators.java generic, and modify the hash table defined in HashTable.java so that is uses sorted buckets of keys (and thus should be more efficient than the current design).

You should be able to use the same test (client) program (OpenHashingTester.java) to test your modifications.

KeyedListWithIterators.java below

import java.util.Iterator; // KeyedListWithIterators: linked list with keyed nodes public class KeyedListWithIterators implements KeyedListWithIteratorsInterface { private Node firstNode, lastNode; private int numEntries; public KeyedListWithIterators() { firstNode = lastNode = null; numEntries = 0; } /* * returns the Node with the given key, * or null if key is not present * * @param key the given key * @return the Node with key or null */ private Node findKeyed(K key) { Node curr = firstNode; while (curr != null) { if (key.equals(curr.key)) { break; } curr = curr.next; } // end while return curr; } // end findKeyed /** * Adds the key/value pair to the list if the key * is not yet present and returns null * Otherwise, replaces the key's current value, * and returns the current value * * @param key the given key * @param value the new value for the key * @return the key's current value or null */ @Override public V add(K key, V newValue) { V oldValue = null; if (isEmpty()) { firstNode = lastNode = new Node(key, newValue); numEntries++; } else { // if key in list, replace value // otherwise, add key/value pair to end Node keyNode = findKeyed(key); if (keyNode != null) { // replace value in currNode oldValue = keyNode.value; keyNode.value = newValue; } else { // add to end of list Node newNode = new Node(key, newValue); lastNode.next = newNode; lastNode = newNode; numEntries++; } // end inner if/else } // end outer if/else return oldValue; } // end add /** * returns the value with the given key * returns null if the key is not present * * @param key the given key * @return the key's current value or null */ @Override public V get(K key) { V value = null; Node keyNode = findKeyed(key); if (keyNode != null) { value = keyNode.value; } return value; } // end get /* * returns the Node prior to the Node * with the given key, * or null if key is not present * * @param key the given key * @return the Node prior to the key or null */ private Node findB4Keyed(K key) { Node curr = firstNode; Node prev = null; while (curr != null) { if (key.equals(curr.key)) { break; } prev = curr; curr = curr.next; } // end while return prev; } // end findB4Keyed /** * removes and returns the value with the given key * returns null if the key is not present * * @param key the given key * @return the key's current value or null */ @Override public V remove(K key) { V value = null; if (isEmpty()) { return null; } Node prevNode = findB4Keyed(key); if (prevNode != null) { Node currNode = prevNode.next; if (currNode != null && key.equals(currNode.key)) { // currNode contains key value = currNode.value; prevNode.next = currNode.next; numEntries--; } } else { if (key.equals(firstNode.key)) { // key is in first node value = firstNode.value; firstNode = firstNode.next; if (firstNode == null) { lastNode = null; } numEntries--; } } // end outer if/else return value; } // end remove /** * indicates whether the list is empty * * @return true is list is empty, false otherwise */ @Override public boolean isEmpty() { return numEntries == 0; } /** * removes all nodes from the list */ @Override public void clear() { firstNode = lastNode = null; System.gc(); numEntries = 0; } // end clear /** * Returns an iterator for the keys * * @return Iterator for the keys in the list */ @Override public Iterator keyIterator() { return new KeyIterator(); } /** * Returns an iterator for the values * * @return Iterator for the values in the list */ @Override public Iterator valueIterator() { return new ValueIterator(); } /** * returns the list as a string of format: * [ (k1,v1) (k2,v2) ... (kn,vn) ] */ @Override public String toString() { StringBuilder sb = new StringBuilder("[ "); Node curr = firstNode; while (curr != null) { sb.append(curr); sb.append(" "); curr = curr.next; } sb.append("]"); return sb.toString(); } // end toString //================================================================================================== private class Node { K key; V value; Node next; Node(K key, V value, Node next) { this.key = key; this.value = value; this.next = next; } Node(K key, V value) { this(key, value, null); } /** * returns the key/value pair as a string */ @Override public String toString() { return "("+key+","+value+")"; } } // end Node class //================================================================================================ class KeyIterator implements Iterator { private Node curr; public KeyIterator() { curr = firstNode; } /** * indicates whether there's another node * * @return false if past end of list, true otherwise */ @Override public boolean hasNext() { return curr != null; } // end hasNext /** * returns key in curr and moves curr to next node * returns null if past end of list */ @Override @SuppressWarnings("unchecked") public K1 next() { K1 nextKey = null; if (hasNext()) { nextKey = (K1)curr.key; curr = curr.next; } return nextKey; } // end next @Override public void remove() { throw new UnsupportedOperationException("remove method not implemented for this class"); } // end remove } // end KeyIterator //================================================================================================ class ValueIterator implements Iterator { private Node curr; public ValueIterator() { curr = firstNode; } /** * indicates whether there's another node * * @return false if past end of list, true otherwise */ @Override public boolean hasNext() { return curr != null; } // end hasNext /** * returns value in curr and moves curr to next node * returns null if past end of list */ @Override @SuppressWarnings("unchecked") public V1 next() { V1 nextValue = null; if (hasNext()) { nextValue = (V1)curr.value; curr = curr.next; } return nextValue; } // end next @Override public void remove() { throw new UnsupportedOperationException("remove method not implemented for this class"); } // end remove } // end ValueIterator } // end KeyedListWithIterators generic 

This is HashTable.java

/* * HashTable.java */ import java.util.Iterator; /** * Open Hash Table generic * * @author NJB * @param  table key type * @param  table element type */ public class HashTable implements DictionaryInterface { private KeyedListWithIteratorsInterface[] table; // array of lists private BagInterface keys; private int numberOfItems; /** * creates new open hash table of given size * * @param size the table size * @throws IllegalArgumentException if size <= 0 */ @SuppressWarnings("unchecked") public HashTable(int size) throws IllegalArgumentException { if (size <= 0) { throw new IllegalArgumentException("Invalid size"); } table = new KeyedListWithIterators[size]; keys = new LinkedBag(); numberOfItems = 0; } // end constructor /** * utility method returns hash key for given table element * uses the pre-defined hashcode method * * @param element the given table element * @return hash key >= 0, < table size */ private int hash(Key key) { return Math.abs(key.hashCode()) % table.length; } // end hash method /* *** DICTIONARY INTERFACE METHODS */ /** 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 element 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. */ @Override public Item add(Key key, Item element) { int hashKey = hash(key); Item oldItem = null; // if nothing with this hash key has been added, // create the list for the hash key if (table[hashKey] == null) { table[hashKey] = new KeyedListWithIterators(); } if (!contains(key)) { table[hashKey].add(key, element); keys.add(key); numberOfItems++; } else { oldItem = table[hashKey].add(key, element); } return oldItem; } // end add method /** 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. */ @Override public Item remove(Key key) { Item result = null; if (!contains(key)) { return result; } int hashKey = hash(key); if (table[hashKey] != null) { result = table[hashKey].remove(key); keys.remove(key); numberOfItems--; } return result; } // end remove method /** 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. */ @Override public Item getValue(Key key) { if (!contains(key)) { return null; } int hashKey = hash(key); Item result = null; if (table[hashKey] != null) { result = table[hashKey].get(key); } return result; } // end getValue method /** 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. */ @Override public boolean contains(Key key) { return keys.contains(key); } // end member method /** 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. */ @Override public Iterator getKeyIterator() { return new KeyIterator(); } /** Creates an iterator that traverses all values in this dictionary. @return An iterator that provides sequential access to the values in this dictionary. */ @Override public Iterator getValueIterator() { return new ValueIterator(); } /** Sees whether this dictionary is empty. @return True if the dictionary is empty. */ @Override public boolean isEmpty() { return numberOfItems == 0; } /** Gets the size of this dictionary. @return The number of entries (key-value pairs) currently in the dictionary. */ @Override public int getSize() { return numberOfItems; } /** Removes all entries from this dictionary. */ @Override public void clear() { for (int hashKey=0; hashKey(); numberOfItems = 0; System.gc(); } //==================================================================== private class KeyIterator implements Iterator { private int nextHashKey; private Iterator currKeyIterator; public KeyIterator() { nextHashKey = findNextList(0); if (nextHashKey > -1) { currKeyIterator = (Iterator) table[nextHashKey].keyIterator(); } else { currKeyIterator = null; } } // end constructor /* returns the (0-based) index of the next non-null list in the table, starting from the given index returns -1 if no such list exists */ private int findNextList(int start) { int result = -1; for (int index=start; index -1 && nextHashKey < table.length; if (result) { // set the iterator of the next table list currKeyIterator = (Iterator)table[nextHashKey].keyIterator(); } } } else { result = false; } return result; } // end hasNext /** * Returns the next element in the iteration. * * @return the next element in the iteration * @throws NoSuchElementException if the iteration has no more elements */ @Override public Key1 next() { if (hasNext()) { return currKeyIterator.next(); } return null; } // end next @Override public void remove() { throw new UnsupportedOperationException("remove() is not " + "supported by this iterator"); } } // end class KeyIterator //==================================================================== private class ValueIterator implements Iterator { private int nextKey; private Iterator currValueIterator; public ValueIterator() { nextKey = findNextList(0); if (nextKey > -1) { currValueIterator = (Iterator) table[nextKey].valueIterator(); } else { currValueIterator = null; } } /* returns the (0-based) index of the next non-null list in the table, starting from the given index returns -1 if no such list exists */ private int findNextList(int start) { int result = -1; for (int index=start; index -1 && nextKey < table.length; if (result) { // set the iterator of the next table list currValueIterator = (Iterator)table[nextKey].valueIterator(); } } } else { result = false; } return result; } // end hasNext /** * Returns the next element in the iteration. * * @return the next element in the iteration * @throws NoSuchElementException if the iteration has no more elements */ @Override public Item1 next() { if (hasNext()) { return currValueIterator.next(); } return null; } // end next /** * Removes from the underlying collection the last element returned by * this iterator (optional operation). This method can be called only * once per call to {@link #next}. The behavior of an iterator is * unspecified if the underlying collection is modified while the * iteration is in progress in any way other than by calling this * method. * * @implSpec The default implementation throws an instance of * {@link UnsupportedOperationException} and performs no other action. * * @throws UnsupportedOperationException if the {@code remove} operation * is not supported by this iterator * * @throws IllegalStateException if the {@code next} method has not yet * been called, or the {@code remove} method has already been called * after the last call to the {@code next} method */ @Override public void remove() { throw new UnsupportedOperationException("remove() is not " + "supported by this iterator"); } // end remove } // end class ValueIterator } // end class HashTable 

This is openHashingTester.java  public class OpenHashingTester { /** * @param args the command line arguments */ public static void main(String[] args) { final int SIZE = 101; final String QUIT = "quit"; HashTable myTable = new HashTable(SIZE); String name="", address, phone, email; Scanner kbd = new Scanner(System.in); System.out.print("Enter any number of records to add; "); System.out.println("enter \"" + QUIT + "\" as name to end:"); while (!name.equalsIgnoreCase(QUIT)) { System.out.print(" \tfull name: "); name = kbd.nextLine(); if (name.equalsIgnoreCase(QUIT)) { continue; } System.out.print("\taddress: "); address = kbd.nextLine(); System.out.print("\tphone number: "); phone = kbd.nextLine(); System.out.print("\te-mail address: "); email = kbd.nextLine(); myTable.add( name, new Record(name, address, phone, email) ); } // end while System.out.print(" . . . Enter any number of names to find; "); System.out.println("enter \"" + QUIT + "\" as name to end:"); name = ""; while (!name.equalsIgnoreCase(QUIT)) { System.out.print("\tfull name: "); name = kbd.nextLine(); if (name.equalsIgnoreCase(QUIT)) { continue; } Record myRec = myTable.getValue(name); if (myRec != null) { System.out.println(myRec); } else { System.out.printf("Record with name \"%s\" not found ", name); } } System.out.println(" . . . =================================================="); System.out.println("Keys & Records: "); Iterator keys = myTable.getKeyIterator(); Iterator values = myTable.getValueIterator(); while (keys.hasNext() && values.hasNext()) { System.out.println("Next key: " + keys.next()); System.out.println("Next record: " + values.next()); }// end while } // end main } // end class OpenHashingTester 

Use the KeyedListWithIterators.java generic to develop a SortedListWithIterators.java generic, and modify the hash table defined in HashTable.java so that is uses sorted buckets of keys (and thus should be more efficient than the current design).

You should be able to use the same test (client) program (OpenHashingTester.java) to test your modifications.