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?

11_3

You MUST use this 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

{

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()

Your posted output after solving the question MUST be this one:

(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: