[Solved] Solvewithhashing Java Problem 1 Given Array N Positive Numbers Give Algorithm Finding Fir Q37222819

• I. SolveWithHashing in java

Problem #1

Given an array of n positive numbers, give an algorithm forfinding the first element in the array which is repeated (may berepeated more than once). For example, in the array {0,3,2,1,2,2,3}the first repeated number is 3 (not 2). Utilize hashing where thekey is the element, and the valueis the position of the element in the array. Initially we store theposition of the element in the array as the value for this key. Ifwe get the same element again however, we just negate the currentvalue in the hash table. The negative value in the hash tableindicates that we have seen the same element more than once. Afterprocessing the complete input array, we scan the hash table withthe values iterator and return the highest negative indexed valuefrom it. The highest negative value indicates that we have seenthat element first among repeated elements.

Step1: You will utilize HashedDictionary classthat implements DictionaryInterface. Make yourself familiar withthe class implementation. Next, implement displayHashTable() methodin this class. SolveWithHashing class has testDisplayHashTablemethod you will use to test it.

Step2: Implement the algorithm ingetFirstRepeatedElement method. Note: the algorithm assumes thatrecorded positions are 1-based, for example the element at index 0has position 1.

Problem #2

Given two arrays a and b, and a numberk, consider the following algorithm for finding whetherthere exists a pair of elements, one of them from a andone from b, that add up to k.

• Select the set which has the smaller number of elements (swapthe reference variables if needed)
• For the selected set create a hash table (you can use theelement for the key and the value)
• Now scan the second array and check whether k-selectedelement exist in the hash table or not
  • HINT look for a key that is computed as a delta between k andthe current element
• If it exists, then return the pair of elements
• Otherwise continue until we reach the end of the set.

IMPLEMENT CODE WHERE IT SAYS “TODO” import java.util.*;import java.util.NoSuchElementException;import java.io.Serializable; public class HashedDictionary<K,V> implements DictionaryInterface<K,V>,Serializable{ // 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 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 private int probes; public HashedDictionary() { this(DEFAULT_CAPACITY); // Call next constructor } // end default constructor public HashedDictionary(int initialCapacity) { initialCapacity = checkCapacity(initialCapacity); this.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]; this.hashTable = temp; this.initialized = true; this.probes = 0; } // end constructor // We’ve added this method to display the hash table for illustration and testing public void displayHashTable() { System.out.println(“The size of hash table is: ” + this.hashTable.length); System.out.println(“In displayHashTable – implement me”); // TODO Project1 #1 // displays “null” if there is no entry in the slot // displays “notIn” if an entry used to be there but was removed // displays the “KEY:” and its “VALUE:” if the entry is there System.out.println(); } // end display // Throws an exception if this object is not initialized. private void checkInitialization() { if (!this.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 int 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); return capacity; } // end checkCapacity // Throws an exception if the hash table becomes too large. private void checkSize(int size) { if (size > MAX_SIZE) throw new IllegalStateException(“Dictionary has become too large.”); } // end checkSize public int getNumberOfProbes() { return this.probes; } 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 < this.hashTable.length); if ( (this.hashTable[index] == null) || this.hashTable[index].isRemoved()) { // Key not found, so insert new entry this.hashTable[index] = new TableEntry<>(key, value); this.numberOfEntries++; oldValue = null; } else { // Key found; get old value for return and then replace it oldValue = this.hashTable[index].getValue(); this.hashTable[index].setValue(value); } // Ensure that hash table is large enough for another add if (isHashTableTooFull()) enlargeHashTable(); return oldValue; } } // end add 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 = this.hashTable[index].getValue(); this.hashTable[index].setToRemoved(); this.numberOfEntries–; } // Else not found; result is 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 = this.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 this.numberOfEntries == 0; } // end isEmpty public int getSize() { return this.numberOfEntries; } // end getSize public final void clear() { checkInitialization(); for (int index = 0; index < this.hashTable.length; index++) hashTable[index] = null; this.numberOfEntries = 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() % this.hashTable.length; if (hashIndex < 0) { hashIndex = hashIndex + this.hashTable.length; } return hashIndex; } // end getHashIndex 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

Expert Answer

---

Answer to I. SolveWithHashing in java Problem #1 Given an array of n positive numbers, give an algorithm for finding the first el… . . .