In JAVA I am using Data Structure and algorithms in Java Second Edition Program
ID: 3701725 • Letter: I
Question
In JAVA
I am using Data Structure and algorithms in Java Second Edition
Program Must Compile and run Please WRITE UNDER ONE FILE!
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. Don’t forget you’ll
need to handle items that have been “deleted,” that is, written over with –1.
MUST COMPILE AND RUN ,PLEASE DISPLAY OUTPUT, PLEASE Write under one File
Please include main method below with program
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<n; j++) // insert data
{
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()
Output may look like:
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:
Explanation / Answer
Below is your code: -
class DataItem {
private int iData;
public DataItem(int ii) {
iData = ii;
}
public int getKey() {
return iData;
}
}
class HashTable {
private DataItem[] hashArray;
private int arraySize;
private DataItem nonItem;
private double numItems; // used to determine loadFactor
public HashTable(int size) {
numItems = 0;
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 < arraySize; j++) {
if (hashArray[j] != null)
System.out.print(hashArray[j].getKey() + " ");
else
System.out.print("** ");
}
System.out.println("");
}
public double getLoadFactor() {
return (numItems / (double) arraySize);
}
public HashTable rehash() {
// create a new table based on the original one
int newSize = getPrime(arraySize * 2);
HashTable newTable = new HashTable(newSize);
System.out.println("Rehashing " + (int)numItems + " items, new size is " + newSize);
newTable.setNumItems(numItems); // transfer numItems from oldtable to
// newtable
// for all the values in the old hash table, re-insert them into the new
// table.
for (int j = 0; j < arraySize; j++) {
if (hashArray[j] != null && hashArray[j].getKey() != -1)
newTable.rehashInsert(hashArray[j], newSize);
}
this.arraySize = newTable.arraySize;
this.hashArray = newTable.hashArray;
this.nonItem = newTable.nonItem;
this.numItems = newTable.numItems;
// then return that table
return newTable;
}
private int getPrime(int min) // returns 1st prime > min
{
for (int j = min + 1; true; j++)
if (isPrime(j))
return j;
}
private boolean isPrime(int n) {
for (int j = 2; (j * j <= n); j++)
if (n % j == 0)
return false;
return true;
}
public int hashFunc(int key) {
return key % arraySize;
}
// used by rehash() to calculate new locations for keys
private void rehashInsert(DataItem item, int size) {
// assumes table not full
int key = item.getKey();
int hashVal = key % size;
while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
++hashVal;
hashVal %= arraySize;
}
hashArray[hashVal] = item;
}
private void setNumItems(double number) {
numItems = number;
}
public void insert(DataItem item) {
// assumes table not full
int key = item.getKey();
int hashVal = hashFunc(key);
while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
++hashVal;
hashVal %= arraySize;
}
hashArray[hashVal] = item;
numItems++;
if (getLoadFactor() > 0.5) {
rehash();
}
}
public DataItem delete(int key) {
int hashVal = hashFunc(key);
while (hashArray[hashVal] != null) {
if (hashArray[hashVal].getKey() == key) {
DataItem temp = hashArray[hashVal];
hashArray[hashVal] = nonItem;
numItems--;
return temp;
}
++hashVal;
hashVal %= arraySize;
}
return null;
}
public DataItem find(int key) {
int hashVal = hashFunc(key);
while (hashArray[hashVal] != null) {
if (hashArray[hashVal].getKey() == key)
return hashArray[hashVal];
++hashVal;
hashVal %= arraySize;
}
return null;
}
} // 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 < n; j++) // insert data
{
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()
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 HashTableApp
Output
Enter size of hash table: 11
Enter initial number of items: 5
Enter first letter of show, insert, delete, or find: s
Table: ** 23 24 ** 48 ** ** ** 41 63 **
Enter first letter of show, insert, delete, or find: d
Enter key value to delete: 48
Enter first letter of show, insert, delete, or find: s
Table: ** 23 24 ** -1 ** ** ** 41 63 **
Enter first letter of show, insert, delete, or find: i
Enter key value to insert: 48
Enter first letter of show, insert, delete, or find: i
Enter key value to insert: 49
Rehashing 6 items, new size is 23
Enter first letter of show, insert, delete, or find: s
Table: 23 24 48 49 ** ** ** ** ** ** ** ** ** ** ** ** ** 63 41 ** ** ** **
Enter first letter of show, insert, delete, or find:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.