Question
Please solve the next program while using the main method provide and make sure to get the EXACT output provided as well Write a rehash()
Please solve the next program while using the main method provide and make sure to get the EXACT output provided as well
Write a rehash() method for the hash.java program. It should be called by insert() to move the entire hash table to an array about twice as large whenever the load factor exceeds 0.5. The new array size should be a prime number. Refer to the section Expanding the Array in this chapter. Dont forget youll need to handle items that have been deleted, that is, written over with 1.
hash.java program:
// hash.java // demonstrates hash table with linear probing // to run this program: C:>java HashTableApp import java.io.*; //////////////////////////////////////////////////////////////// class DataItem { // (could have more data) private int iData; // data item (key) //-------------------------------------------------------------- public DataItem(int ii) // constructor { iData = ii; } //-------------------------------------------------------------- public int getKey() { return iData; } //-------------------------------------------------------------- } // end class DataItem //////////////////////////////////////////////////////////////// class HashTable { private DataItem[] hashArray; // array holds hash table private int arraySize;
private DataItem nonItem; // for deleted items // ------------------------------------------------------------- public HashTable(int size) // constructor { arraySize = size; hashArray = new DataItem[arraySize]; nonItem = new DataItem(-1); // deleted item key is -1 } // ------------------------------------------------------------- public void displayTable() { System.out.print(Table: ); for(int j=0; j // ------------------------------------------------------------- public DataItem delete(int key) // delete a DataItem { int hashVal = hashFunc(key); // hash the key while(hashArray[hashVal] != null) // until empty cell, { // found the key? if(hashArray[hashVal].getKey() == key) { DataItem temp = hashArray[hashVal]; // save item hashArray[hashVal] = nonItem; // delete item return temp; // return item } ++hashVal; // go to next cell hashVal %= arraySize; // wraparound if necessary } return null; // cant find item } // end delete() // ------------------------------------------------------------- public DataItem find(int key) // find item with key { int hashVal = hashFunc(key); // hash the key while(hashArray[hashVal] != null) // until empty cell, { // found the key? if(hashArray[hashVal].getKey() == key) return hashArray[hashVal]; // yes, return item ++hashVal; // go to next cell hashVal %= arraySize; // wraparound if necessary } return null; // cant find item } // ------------------------------------------------------------- } // end class HashTable //////////////////////////////////////////////////////////////// class HashTableApp { public static void main(String[] args) throws IOException { DataItem aDataItem; int aKey, size, n, keysPerCell; // get sizes System.out.print(Enter size of hash table: ); size = getInt(); System.out.print(Enter initial number of items: ); n = getInt(); keysPerCell = 10; // make table HashTable theHashTable = new HashTable(size); for(int j=0; j aDataItem = theHashTable.find(aKey); if(aDataItem != null) { System.out.println(Found + aKey); } else System.out.println(Could not find + aKey); break; default: System.out.print(Invalid entry ); } // end switch } // end while } // end main() //-------------------------------------------------------------- public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } //-------------------------------------------------------------- public static char getChar() throws IOException { String s = getString(); return s.charAt(0); } //------------------------------------------------------------- public static int getInt() throws IOException { String s = getString(); return Integer.parseInt(s); } //-------------------------------------------------------------- } // end class HashTableApp You MUST use this main method to solve this question: public static void main(String[] args) throws IOException { DataItem aDataItem; int aKey, size, n, keysPerCell; // get sizes System.out.print("Enter size of hash table: "); size = getInt(); System.out.print("Enter initial number of items: "); n = getInt(); keysPerCell = 10; // make table HashTable theHashTable = new HashTable(size); for(int j=0; j { aKey = (int)(java.lang.Math.random() * keysPerCell * size); aDataItem = new DataItem(aKey); theHashTable.insert(aDataItem); } while(true) // interact with user { System.out.print("Enter first letter of "); System.out.print("show, insert, delete, or find: "); char choice = getChar(); switch(choice) { case 's': theHashTable.displayTable(); break; case 'i': System.out.print("Enter key value to insert: "); aKey = getInt(); aDataItem = new DataItem(aKey); theHashTable.insert(aDataItem); break; case 'd': System.out.print("Enter key value to delete: "); aKey = getInt(); theHashTable.delete(aKey); break; case 'f': System.out.print("Enter key value to find: "); aKey = getInt(); aDataItem = theHashTable.find(aKey); if(aDataItem != null) { System.out.println("Found " + aKey); } else System.out.println("Could not find " + aKey); break; default: System.out.print("Invalid entry "); } // end switch } // end while } // end main() You MUST get this output and please when you post the answer make sure to post the output that you get: Enter size of hash table: 11 Enter initial number of items: 5 Enter first letter of show, insert, delete, or find: s Table: 22 ** ** 47 70 ** ** ** 74 ** 109 Enter first letter of show, insert, delete, or find: d Enter key value to delete: 47 Enter first letter of show, insert, delete, or find: s Table: 22 ** ** -1 70 ** ** ** 74 ** 109 Enter first letter of show, insert, delete, or find: i Enter key value to insert: 47 Rehashing 6 items, new size is 23 Enter first letter of show, insert, delete, or find: s Table: ** 47 70 ** ** 74 ** ** ** ** ** ** ** ** ** ** ** 109 ** ** ** ** 22 Enter first letter of show, insert, delete, or find: i Enter key value to insert: 13 Enter first letter of show, insert, delete, or find: s Table: ** 47 70 ** ** 74 ** ** ** ** ** ** ** 13 ** ** ** 109 ** ** ** ** 22 Enter first letter of show, insert, delete, or find:
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started