[Solved]Java Application Works Correctly Move Part 2 Analyzing Hashing Mechanism One Faster Dicti Q37203821
In java
Once the applicationworks correctly move to part 2 that has to do with analyzing thehashing mechanism itself.
One of the fasterdictionary implementations is the hash table. As long as the tabledoes not become too full, the time for adding and finding anelement will be O(1). This performance does not come without somecost. The obvious penalty is that there will be space in the tablethat is wasted. Another penalty is that the items in the hash tableare not in any particular order. As more items are added to thehash table, the size of the table may be increased to maintain theperformance. In this case, the items will be rehashed and will nolonger be in the same locations or order. To observe this behavior,make changes in HashedDictionary class necessary to change the openaddressing from Linear Probing mechanism to DoubleHashing.
- First implement getHashIndexIncrement method that calculatesand returns the step increment for the given key to be used whenprobing for element inside the locate and probe methods. Use thefollowing formula to calculate the initial value of the increment:step = (previousPrime – key.hashCode()) % previousPrime; If thecalculated step value is zero set it to the provided DEFAULT_PRIME.If the calculated step is negative, make it positive by adding thehashTable.length to it.
- Change probe and locate to use Double Hashing insteadof the Linear Probing currently in place.
private int getHashIndexIncrement(K key) { // TODO Project 2 Part 2 int previousPrime = getPreviousPrime(this.hashTable.length); final int DEFAULT_PRIME = 7; int step = 0; System.out.println(“getHashIndexIncrement method – IMPLEMENT ME”); //System.out.println(“hash index increment is ” + step); return step; } // end getHashIndexIncrement // Precondition: checkInitialization has been called. private int probe(int index, K key) { // TODO Project 2 Part 2 boolean found = false; int removedStateIndex = -1; // Index of first location in removed state //int step = getHashIndexIncrement(key); // for double hashing ****** while ( !found && (this.hashTable[index] != null) ) { if (this.hashTable[index].isIn()) { if (key.equals(this.hashTable[index].getKey())) found = true; // Key found else { // Follow probe sequence index = (index + 1) % this.hashTable.length; // Linear probing this.probes++; } } else // Skip entries that were removed { // Save index of first location in removed state if (removedStateIndex == -1) removedStateIndex = index; index = (index + 1) % this.hashTable.length; // Linear probing this.probes++; } } // 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 int locate(int index, K key) { // TODO Project 2 Part 2 boolean found = false; // int step = getHashIndexIncrement(key); // for double hashing ****** while ( !found && (this.hashTable[index] != null) ) { if ( this.hashTable[index].isIn() && key.equals(this.hashTable[index].getKey()) ) found = true; // Key found else { // Follow probe sequence index = (index + 1) % this.hashTable.length; // Linear probing ****** this.probes++; } } // Assertion: Either key or null is found at hashTable[index] int result = -1; if (found) result = index; return result; } // end locate // 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 = this.hashTable; int oldSize = this.hashTable.length; int newSize = getNextPrime(oldSize + oldSize); checkSize(newSize); // The cast is safe because the new array contains null entries @SuppressWarnings(“unchecked”) TableEntry<K, V>[] tempTable = (TableEntry<K, V>[])new TableEntry[newSize]; // Increase size of array this.hashTable = tempTable; this.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 enlargeHashTable // Returns true if lambda > MAX_LOAD_FACTOR for hash table; // otherwise returns false. private boolean isHashTableTooFull() { return this.numberOfEntries > MAX_LOAD_FACTOR * this.hashTable.length; } // end isHashTableTooFull private int getPreviousPrime(int integer) { // if even, subtract 1 to make odd if (integer % 2 == 0) { integer–; } // test odd integers while(!isPrime(integer)) { integer = integer – 2; } return integer; } // end getPreviousPrime // 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++; } // test odd integers while (!isPrime(integer)) { integer = integer + 2; } 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; } } } return result; } // end isPrime 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() { this.currentIndex = 0; this.numberLeft = numberOfEntries; } // end default constructor public boolean hasNext() { return this.numberLeft > 0; } // end hasNext public K next() { K result = null; if (hasNext()) { // Skip table locations that do not contain a current entry while ( (hashTable[this.currentIndex] == null) || hashTable[this.currentIndex].isRemoved() ) { this.currentIndex++; } result = hashTable[this.currentIndex].getKey(); this.numberLeft–; this.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() { this.currentIndex = 0; this.numberLeft = numberOfEntries; } // end default constructor public boolean hasNext() { return this.numberLeft > 0; } // end hasNext public V next() { V result = null; if (hasNext()) { // Skip table locations that do not contain a current entry while ( (hashTable[this.currentIndex] == null) || hashTable[this.currentIndex].isRemoved() ) { this.currentIndex++; } result = hashTable[this.currentIndex].getValue(); this.numberLeft–; this.currentIndex++; } else throw new NoSuchElementException(); return result; } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end ValueIterator private static class TableEntry<S, T> implements Serializable { private S key; private T value; private States state; // Flags whether this entry is in the hash table private enum States {CURRENT, REMOVED} // Possible values of state private TableEntry(S searchKey, T dataValue) { this.key = searchKey; this.value = dataValue; this.state = States.CURRENT; } // end constructor private S getKey() { return this.key; } // end getKey private T getValue() { return this.value; } // end getValue private void setValue(T newValue) { this.value = newValue; } // end setValue // Returns true if this entry is currently in the hash table. private boolean isIn() { return this.state == States.CURRENT; } // end isIn // Returns true if this entry has been removed from the hash table. private boolean isRemoved() { return this.state == States.REMOVED; } // end isRemoved // Sets the state of this entry to removed. private void setToRemoved() { this.key = null; this.value = null; this.state = States.REMOVED; // Entry not in use, ie deleted from table } // end setToRemoved // Sets the state of this entry to current. private void setToIn() // Not used { this.state = States.CURRENT; // Entry in use } // end setToIn } // end TableEntry}
Expert Answer
Answer to In java Once the application works correctly move to part 2 that has to do with analyzing the hashing mechanism itself. … . . .
OR
