QUESTION:

Java: Code the following algorithm for finding the location of an object as a static method. Assume a hash table array and an object to be located in the table are passed as arguments. Return the objects position if it is found; return -1 if the object is not found.

Computer the index by taking the hashCode() % table.length

If table[index] is null

The object is not in the table

Else if table[index is equal to the object

The object is in the table

Continue to search the table(by incrementing index) until either the object is found or a null entry is found

HASHTABLECHAIN CODE

/**/ package KW.CH07; import java.util.AbstractMap; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.StringJoiner; /** * Hash table implementation using chaining. * @param  The key type * @param  The value type * @author Koffman and Wolfgang **/ public class HashtableChain /**/ extends AbstractMap /**/ implements KWHashMap { /** The table */ private LinkedList>[] table; /** The number of keys */ private int numKeys; /** The capacity */ private static final int CAPACITY = 101; /** The maximum load factor */ private static final double LOAD_THRESHOLD = 3.0; /**/ // Note this is equivalent to java.util.AbstractMap.SimpleEntry /** Contains key-value pairs for a hash table. @param  the key type @param  the value type */ public static class Entry /**/ implements Map.Entry /**/ { /** The key */ private final K key; /** The value */ private V value; /** * Creates a new key-value pair. * @param key The key * @param value The value */ public Entry(K key, V value) { this.key = key; this.value = value; } /** * Retrieves the key. * @return The key */ @Override public K getKey() { return key; } /** * Retrieves the value. * @return The value */ @Override public V getValue() { return value; } /** * Sets the value. * @param val The new value * @return The old value */ @Override public V setValue(V val) { V oldVal = value; value = val; return oldVal; } /**/ /** * Return a String representation of the Entry * @return a String representation of the Entry * in the form key = value */ @Override public String toString() { return key.toString() + "=" + value.toString(); } /**/ } /**/ // Constructor public HashtableChain() { table = new LinkedList[CAPACITY]; } // Constructor for test purposes HashtableChain(int capacity) { table = new LinkedList[capacity]; } /**/ /** * Method get for class HashtableChain. * @param key The key being sought * @return The value associated with this key if found; * otherwise, null */ @Override public V get(Object key) { int index = key.hashCode() % table.length; if (index < 0) { index += table.length; } if (table[index] == null) { return null; // key is not in the table. } // Search the list at table[index] to find the key. for (Entry nextItem : table[index]) { if (nextItem.getKey().equals(key)) { return nextItem.getValue(); } } // assert: key is not in the table. return null; } /**/ /**/ /** * Method put for class HashtableChain. * @post This key-value pair is inserted in the * table and numKeys is incremented. If the key is already * in the table, its value is changed to the argument * value and numKeys is not changed. * @param key The key of item being inserted * @param value The value for this key * @return The old value associated with this key if * found; otherwise, null */ @Override public V put(K key, V value) { int index = key.hashCode() % table.length; if (index < 0) { index += table.length; } if (table[index] == null) { // Create a new linked list at table[index]. table[index] = new LinkedList<>(); } // Search the list at table[index] to find the key. for (Entry nextItem : table[index]) { // If the search is successful, replace the old value. if (nextItem.getKey().equals(key)) { // Replace value for this key. V oldVal = nextItem.getValue(); nextItem.setValue(value); return oldVal; } } // assert: key is not in the table, add new item. table[index].addFirst(new Entry<>(key, value)); numKeys++; if (numKeys > (LOAD_THRESHOLD * table.length)) { rehash(); } return null; } /**/ /**/ /** Returns the number of entries in the map @return the number of entries in the map */ @Override public int size() { return numKeys; } /**/ /** Returns true if empty @return true if empty */ @Override public boolean isEmpty() { return numKeys == 0; } /** * Expands table size when loadFactor exceeds LOAD_THRESHOLD * @post the size of table is doubled and is an * odd integer. Each non-deleted entry from the original * table is reinserted into the expanded table. * The value of numKeys is reset to the number of items * actually inserted; numDeletes is reset to 0. */ public void rehash() { // Save a reference to oldTable List>[] oldTable = table; // Double capacity of this table table = new LinkedList[2 * oldTable.length + 1]; // Reinsert all items in oldTable into expanded table. numKeys = 0; for (List> cell : oldTable) { if (cell != null) { cell.forEach(nextEntry -> put(nextEntry.getKey(), nextEntry.getValue())); } } } /**/ /**/ @Override public java.util.Set> entrySet() { return new EntrySet(); } /** Inner class to implement the set view. */ private class EntrySet extends java.util.AbstractSet> { /** Return the size of the set. */ @Override public int size() { return numKeys; } /** Return an iterator over the set. */ @Override public Iterator> iterator() { return new SetIterator(); } } private class SetIterator implements Iterator> { int index = 0; Iterator> localIterator = null; @Override public boolean hasNext() { if (localIterator != null) { if (localIterator.hasNext()) { return true; } else { localIterator = null; index++; } } while (index < table.length && table[index] == null) { index++; } if (index == table.length) { return false; } localIterator = table[index].iterator(); return localIterator.hasNext(); } @Override public Map.Entry next() { if (!hasNext()) { throw new java.util.NoSuchElementException(); } return localIterator.next(); } @Override public void remove() { localIterator.remove(); if (table[index].size() == 0) { table[index] = null; } numKeys--; } } /**/ } /**/ 

HASHTABLEOPEN CODE

/**/ package KW.CH07; import java.util.AbstractMap; import java.util.AbstractSet; import java.util.Iterator; import java.util.Map; import java.util.Set; import java.util.StringJoiner; /** * Hash table implementation using open addressing. * @param  The key type * @param  The value type * @author Koffman and Wolfgang */ public class HashtableOpen /**/ extends AbstractMap /**/ implements KWHashMap { // Data Fields private Entry[] table; private static final int START_CAPACITY = 101; private static final double LOAD_THRESHOLD = 0.75; private int numKeys; private int numDeletes; // private static final Entry DELETED = new Entry(null, null); private static final Entry DELETED = new Entry(null, null); /**/ private int numFinds = 0; private int numProbes = 0; /**/ // Constructor public HashtableOpen() { table = new Entry[START_CAPACITY]; } // Constructor for testing HashtableOpen(int capacity) { table = new Entry[capacity]; } /**/ // Note this is equivalent to java.util.AbstractMap.SimpleEntry /** Contains key-value pairs for a hash table. @param  the key type @param  the value type */ public static class Entry /**/ implements Map.Entry /**/ { /** The key */ private final K key; /** The value */ private V value; /** * Creates a new key-value pair. * @param key The key * @param value The value */ public Entry(K key, V value) { this.key = key; this.value = value; } /** * Retrieves the key. * @return The key */ @Override public K getKey() { return key; } /** * Retrieves the value. * @return The value */ @Override public V getValue() { return value; } /** * Sets the value. * @param val The new value * @return The old value */ @Override public V setValue(V val) { V oldVal = value; value = val; return oldVal; } /**/ /** * Return a String representation of the Entry * @return a String representation of the Entry * in the form key = value */ @Override public String toString() { return key.toString() + "=" + value.toString(); } /**/ } /**/ /**/ /** Returns the number of entries in the map @return the number of entries in the map */ @Override public int size() { return numKeys; } /**/ /** Returns true if empty @return true if empty */ @Override public boolean isEmpty() { return numKeys == 0; } /**/ /** * Finds either the target key or the first empty slot in the * search chain using linear probing. * @pre The table is not full. * @param key The key of the target object * @return The position of the target or the first empty slot if * the target is not in the table. */ private int find(Object key) { /**/ numFinds++; /**/ // Calculate the starting index. int index = key.hashCode() % table.length; if (index < 0) { index += table.length; // Make it positive. } // Increment index until an empty slot is reached // or the key is found. while ((table[index] != null) && (!key.equals(table[index].getKey()))) { /**/ numProbes++; /**/ index++; // Check for wraparound. if (index >= table.length) { index = 0; // Wrap around. } } return index; } /**/ /**/ /** * Method get for class HashtableOpen. * @param key The key being sought * @return the value associated with this key if found; * otherwise, null */ @Override public V get(Object key) { // Find the first table element that is empty // or the table element that contains the key. int index = find(key); // If the search is successful, return the value. if (table[index] != null) { return table[index].getValue(); } else { return null; // key not found. } } /**/ /**/ /** * Method put for class HashtableOpen. * @post This key-value pair is inserted in the * table and numKeys is incremented. If the key is already * in the table, its value is changed to the argument * value and numKeys is not changed. If the LOAD_THRESHOLD * is exceeded, the table is expanded. * @param key The key of item being inserted * @param value The value for this key * @return Old value associated with this key if found; * otherwise, null */ @Override public V put(K key, V value) { // Find the first table element that is empty // or the table element that contains the key. int index = find(key); // If an empty element was found, insert new entry. if (table[index] == null) { table[index] = new Entry<>(key, value); numKeys++; // Check whether rehash is needed. double loadFactor = (double) (numKeys + numDeletes) / table.length; if (loadFactor > LOAD_THRESHOLD) { rehash(); } return null; } // assert: table element that contains the key was found. // Replace value for this key. V oldVal = table[index].getValue(); table[index].setValue(value); return oldVal; } /**/ /**/ /** * Returns a set view of the entries in the Map * @return a Set view of the entries in the Map */ @Override public Set> entrySet() { return new EntrySet(); } /** Inner class to implement the set view. */ private class EntrySet extends AbstractSet> { /** Return the size of the set. */ @Override public int size() { return numKeys; } /** Return an iterator over the set. */ @Override public Iterator> iterator() { return new SetIterator(); } } /**/ /**/ private class SetIterator implements Iterator> { //Data Field /** Index into array containing the hash table */ int index = -1; int indexOfLastReturned = -1; //Methods public SetIterator() { advanceIndex(); } @Override public boolean hasNext() { return index < table.length; } @Override public Map.Entry next() { if (!hasNext()) { throw new java.util.NoSuchElementException(); } Map.Entry returnValue = table[index]; indexOfLastReturned = index; advanceIndex(); return returnValue; } @Override public void remove() { if (indexOfLastReturned == -1) { throw new IllegalStateException(); } table[indexOfLastReturned] = DELETED; numDeletes++; numKeys--; indexOfLastReturned = -1; } private void advanceIndex() { do { index++; } while (index < table.length && (table[index] == null || table[index] == DELETED)); } } /**/ /**/ /** * Finds either the target key or the first empty slot in the * search chain using linear probing. * @pre The table is not full. * @param array The hash table to be searched * @param key The key of the target object * @return The position of the target or the first empty slot if * the target is not in the table. */ private static int find(Object[] array, Object key) { // Calculate the starting index. int index = key.hashCode() % array.length; if (index < 0) { index += array.length; // Make it positive. } // Increment index until an empty slot is reached // or the key is found. while ((array[index] != null) && (!key.equals(array[index]))) { index++; // Check for wraparound. if (index >= array.length) { index = 0; // Wrap around. } } return index; } /**/ /**/ @Override public String toString() { StringJoiner sj = new StringJoiner(", ", "{", "}"); for (Entry entry : table) { if (entry != null) sj.add(entry.toString()); } return sj.toString(); } /**/ /**/ public double averageProbes() { return (double) numProbes / numFinds; } /**/ } /**/