Modify this following program so that it can display this same Output. It must b
ID: 3702024 • Letter: M
Question
Modify this following program so that it can display this same Output. It must be the SAME.
Your posted output after modifying MUST be this one (exept for thr random #'s that can be any):
(Try size=1000, N=3, max=1000000)
Enter size of hash table: 10
Enter number of items: 4
Enter max key value: 1000000
key=889845, groups are 5+4+8+9+8+8, hashValue is 42, trimmed to 2
key=964039, groups are 9+3+0+4+6+9, hashValue is 31, trimmed to 1
key=806169, groups are 9+6+1+6+0+8, hashValue is 30, trimmed to 0
key=265774, groups are 4+7+7+5+6+2, hashValue is 31, trimmed to 1
Enter first letter of show, insert, delete, or find: s
Table: 806169 964039 889845 265774 ** ** ** ** ** **
Enter first letter of show, insert, delete, or find: i
Enter key value to insert: 65789
key=65789, groups are 9+8+7+5+6, hashValue is 35, trimmed to 5
Enter first letter of show, insert, delete, or find: s
Table: 806169 964039 889845 265774 ** 65789 ** ** ** **
Enter first letter of show, insert, delete, or find: i
Enter key value to insert: 98765
key=98765, groups are 5+6+7+8+9, hashValue is 35, trimmed to 5
Enter first letter of show, insert, delete, or find: s
Table: 806169 964039 889845 265774 ** 65789 98765 ** ** **
Enter first letter of show, insert, delete, or find: d
Enter key value to delete: 265774
key=265774, groups are 4+7+7+5+6+2, hashValue is 31, trimmed to 1
Enter first letter of show, insert, delete, or find: s
Table: 806169 964039 889845 -1 ** 65789 98765 ** ** **
Enter first letter of show, insert, delete, or find:
THIS IS THE PROGRAM THAT NEEDS TO BE MODIFIED:
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
private int divisor;
// -------------------------------------------------------------
public HashTable(int size) // constructor
{
arraySize = size;
hashArray = new DataItem[arraySize];
nonItem = new DataItem(-1); // deleted item key is -1
divisor = 1;
while (size > 0)
{
size/= 10;
divisor *= 10;
}
}
// -------------------------------------------------------------
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 int hashFunc(int key)
{
int hashVal = 0;
while(key > 0)
{hashVal += key % divisor;
key /= divisor;
}
return hashVal % arraySize; // hash function
}
// -------------------------------------------------------------
public void insert(DataItem item) // insert a DataItem
// (assumes table not full)
{
int key = item.getKey(); // extract key
int hashVal = hashFunc(key); // hash the key
// until empty cell or -1,
while(hashArray[hashVal] != null &&
hashArray[hashVal].getKey() != -1)
{
++hashVal; // go to next cell
hashVal %= arraySize; // wraparound if necessary
}
hashArray[hashVal] = item; // insert item
} // end insert()
// -------------------------------------------------------------
// -------------------------------------------------------------
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; // can’t 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; // can’t find item
}
// -------------------------------------------------------------
} // end class HashTable
////////////////////////////////////////////////////////////////
class HashTableApp
{
public static void main(String[] args) throws IOException
{
DataItem aDataItem;
int aKey, size, n, maxKeyVal;
// get sizes
System.out.println("(Try size=1000, N=3, max=1000000)");
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter number of items: ");
n = getInt();
System.out.print("Enter max key value: ");
maxKeyVal = getInt();
// make table
HashTable theHashTable = new HashTable(size);
for(int j=0; j<n; j++) // insert data
{
aKey = (int)(java.lang.Math.random() * maxKeyVal);
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 class HashTableApp
Explanation / Answer
Hello. I have made proper changes to your code to get the expected output. Made the divisor as 10 (always), and modified the hashFunc() method to display the information of key, groups, original hash value and trimmed value. Drop a comment if you have doubts. Thanks.
//HashTableApp.java
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
private int divisor;
// -------------------------------------------------------------
public HashTable(int size) // constructor
{
arraySize = size;
hashArray = new DataItem[arraySize];
nonItem = new DataItem(-1); // deleted item key is -1
/**
* divisor should always be 10 in order to get the expected output
*/
divisor = 10;
/*
* commented below lines as they're not needed anymore while (size > 0)
*
* {
*
* size /= 10;
*
* divisor *= 10;
*
* }
*/
}
// -------------------------------------------------------------
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 int hashFunc(int key)
{
/**
* Modified this method to show the processing info while calculating
* hash value
*/
int orig_key = key;
int hashVal = 0;
String groups = null;// to store the groups of digits
while (key > 0)
{
int digit = key % divisor;
hashVal += digit;
key /= divisor;
/**
* appending the digit to the string
*/
if (groups == null) {
groups = "" + digit;
} else {
groups += "+" + digit;
}
}
/**
* displaying the information
*/
System.out.printf(
"key=%d, groups are %s, hashValue is %d, trimmed to %d ",
orig_key, groups, hashVal, hashVal % arraySize);
return hashVal % arraySize; // hash function
}
// -------------------------------------------------------------
public void insert(DataItem item) // insert a DataItem
// (assumes table not full)
{
int key = item.getKey(); // extract key
int hashVal = hashFunc(key); // hash the key
// until empty cell or -1,
while (hashArray[hashVal] != null &&
hashArray[hashVal].getKey() != -1)
{
++hashVal; // go to next cell
hashVal %= arraySize; // wraparound if necessary
}
hashArray[hashVal] = item; // insert item
} // end insert()
// -------------------------------------------------------------
// -------------------------------------------------------------
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; // can’t 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; // can’t find item
}
// -------------------------------------------------------------
} // end class HashTable
// //////////////////////////////////////////////////////////////
public class HashTableApp
{
public static void main(String[] args) throws IOException
{
DataItem aDataItem;
int aKey, size, n, maxKeyVal;
// get sizes
System.out.println("(Try size=1000, N=3, max=1000000)");
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter number of items: ");
n = getInt();
System.out.print("Enter max key value: ");
maxKeyVal = getInt();
// make table
HashTable theHashTable = new HashTable(size);
for (int j = 0; j < n; j++) // insert data
{
aKey = (int) (java.lang.Math.random() * maxKeyVal);
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 class HashTableApp
/*OUTPUT*/
(Try size=1000, N=3, max=1000000)
Enter size of hash table: 10
Enter number of items: 4
Enter max key value: 1000000
key=586629, groups are 9+2+6+6+8+5, hashValue is 36, trimmed to 6
key=534113, groups are 3+1+1+4+3+5, hashValue is 17, trimmed to 7
key=367847, groups are 7+4+8+7+6+3, hashValue is 35, trimmed to 5
key=134598, groups are 8+9+5+4+3+1, hashValue is 30, trimmed to 0
Enter first letter of show, insert, delete, or find: s
Table: 134598 ** ** ** ** 367847 586629 534113 ** **
Enter first letter of show, insert, delete, or find: i
Enter key value to insert: 123456
key=123456, groups are 6+5+4+3+2+1, hashValue is 21, trimmed to 1
Enter first letter of show, insert, delete, or find: s
Table: 134598 123456 ** ** ** 367847 586629 534113 ** **
Enter first letter of show, insert, delete, or find: d
Enter key value to delete: 123456
key=123456, groups are 6+5+4+3+2+1, hashValue is 21, trimmed to 1
Enter first letter of show, insert, delete, or find: s
Table: 134598 -1 ** ** ** 367847 586629 534113 ** **
Enter first letter of show, insert, delete, or find: f
Enter key value to find: 123456
key=123456, groups are 6+5+4+3+2+1, hashValue is 21, trimmed to 1
Could not find 123456
Enter first letter of show, insert, delete, or find: f
Enter key value to find: 586629
key=586629, groups are 9+2+6+6+8+5, hashValue is 36, trimmed to 6
Found 586629
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.