In JAVA I am using Data Structure and algorithms in Java Second Edition chapter
ID: 3704448 • Letter: I
Question
In JAVA
I am using Data Structure and algorithms in Java Second Edition chapter 11
Program Must Compile and run Please WRITE UNDER ONE FILE!
Write a hash function to implement a digit-folding approach in the hash function
(as described in the “Hash Functions” section of this chapter). Your
program should work for any array size and any key length. Use linear probing.
Accessing a group of digits in a number may be easier than you think. Does it
matter if the array size is not a multiple of 10?
MUST COMPILE AND RUN ,PLEASE DISPLAY OUTPUT, Please Write under one File
Please include main method below with program sample output below the main method
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()
Output may look like:
(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:
Explanation / Answer
import java.io.*; //headerfile class FoldingHashTable//class { private HashDataItem[] hashArray; private int arraySize; private HashDataItem nonItem; public FoldingHashTable(int size)//foldinghashtablefunction { arraySize = size; hashArray = new HashDataItem[arraySize]; nonItem = new HashDataItem(-1); //deleted item key is -1 } public void displayTable()//displaytablefunction { System.out.print("Table: "); for(int j = 0; j 0) { temp /= 10; groupSize *= 10; } while(key > 0) { hashVal += key % groupSize; key /= groupSize; } return hashVal; } public void insert(HashDataItem 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; } public HashDataItem delete(int key) { int hashVal = hashFunc(key); while(hashArray[hashVal] != null) { if(hashArray[hashVal].getKey() == key) { HashDataItem temp = hashArray[hashVal]; hashArray[hashVal] = nonItem; return temp; } ++hashVal; hashVal %= arraySize; } return null; } public HashDataItem 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 FoldingHashTableApp { public static void main(String[] args) throws IOException { HashDataItem aDataItem; int aKey, size, n, keysPerCell; System.out.print("Enter size of hash table: "); size = getInt(); System.out.print("Enter initial number of items: "); n = getInt(); keysPerCell = 10; HashTable theHashTable = new HashTable(size); for(int j=0; jRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.