Write a program in Java that implements the Hashtable: a) The Hashtable has the
ID: 664710 • Letter: W
Question
Write a program in Java that implements the Hashtable: a) The Hashtable has the size = 50 (an array of size 50) b) It uses the Double Hashing technique to determine the hash code c) Implement with the Open Addressing style (i.e., no bucket and no linked list), all the keys are stored in the Hashtable itself d) Test the Hashtable and hashcode method by hashing these values into the table: [1255, 9898, 4782, 7980, 2975, 4342, 8885, 5322, 1298] e) Display the hashcode and the final probe number used for each value before inserting it into the Hashtable f) Display the contents of the entire Hashtable to see where these values are located in the table
Explanation / Answer
Answer:
import java.io.*;
import java.util.*;
import java.lang.Integer;
class Data_Item1
{
public int iData1;
public Data_Item1(int k1)
{ iData1 = k1; }
}
class Hash_Table12
{
Data_Item1[] hash_Array1;
int array_Size1;
Data_Item1 nonItem;
int num_items1;
Hash_Table12(int size1)
{
array_Size1 = size1;
hash_Array1 = new Data_Item1[array_Size1];
nonItem = new Data_Item1(-1);
num_items1 = 0;
}
public void displayTable12()
{
System.out.print("TABLE: ");
for(int k1=0; k1<array_Size1; k1++)
{
if(hash_Array1[k1] != null)
System.out.print(hash_Array1[k1].iData1+ " ");
else
System.out.print("** ");
}
System.out.println("");
}
public int hashFunc1(int key1)
{
return key1 % array_Size1;
}
public int hashFunc2(int key1)
{
return 5 - key1% 5;
}
public void insert(int key1, Data_Item1 item1, int size1)
// (ASSUMES TABLE NOT FULL)
{
if (num_items1 == size1)
System.out.println(" ERROR. TABLE FULL.");
else
num_items1++;
int hashVal1 = hashFunc1(key1);
int step_Size = hashFunc2(key1);
while(hash_Array1[hashVal1] != null &&
hash_Array1[hashVal1].iData1 != -1)
{
hashVal1 += step_Size;
hashVal1 %= array_Size1;
}
hash_Array1[hashVal1] = item1;
} // END INSERT()
public Data_Item1 delete(int key1)
{
int hash_Val = hashFunc1(key1);
int step_Size = hashFunc2(key1);
while(hash_Array1[hash_Val] != null)
{
if(hash_Array1[hash_Val].iData1== key1)
{
num_items1--;
Data_Item1 temp1 = hash_Array1[hash_Val];
hash_Array1[hash_Val] = nonItem;
return temp1;
}
hash_Val += step_Size;
hash_Val %= array_Size1; // FOR WRAPAROUND
}
return null; // CAN'T FIND ITEM
}
public Data_Item1 find(int key1) // FIND ITEM WITH KEY
// (assumes table not full)
{
int hash_Val = hashFunc1(key1); // HASH THE KEY
int step_Size = hashFunc2(key1); // GET STEP SIZE
while(hash_Array1[hash_Val] != null) // UNTIL EMPTY CELL,
{ // IS CORRECT HASHVAL?
if(hash_Array1[hash_Val].iData1 == key1)
return hash_Array1[hash_Val]; // YES, RETURN ITEM
hash_Val += step_Size; // ADD THE STEP
hash_Val %= array_Size1; // FOR WRAPAROUND
}
return null; // CAN'T FIND ITEM
}
} /
public class HashDoubleAppImplementation
{
public static void main(String[] args) throws IOException
{
int aKey1;
Data_Item1 aData_Item1;
int size1, k2;
putText12("ENTER SIZE OF HASH TABLE: ");
size1 = getInt12();
putText12("ENTER INITIAL NUMBER OF ITEMS: ");
k2 = getInt12();
Hash_Table12 theHashTable12 = new Hash_Table12(size1);
for(int k1=0; k1<k2; k1++) // INSERT DATA
{
aKey1 = (int)(java.lang.Math.random() * 2 * size1);
aData_Item1 = new Data_Item1(aKey1);
theHashTable12.insert(aKey1, aData_Item1, size1);
}
while(true) // interact with user
{
putText12("ENTER FIRST LETTER OF ");
putText12("SHOW, INSERT, DELETE, OR FIND: ");
char choi1 = getChar12();
switch(choi1)
{
case 's':
theHashTable12.displayTable12();
break;
case 'i':
putText12("ENTER KEY VALUE TO INSERT: ");
aKey1 = getInt12();
aData_Item1 = new Data_Item1(aKey1);
theHashTable12.insert(aKey1, aData_Item1, size1);
break;
case 'd':
putText12("ENTER KEY VALUE TO DELETE: ");
aKey1 = getInt12();
theHashTable12.delete(aKey1);
break;
case 'f':
putText12("ENTER KEY VALUE TO FIND: ");
aKey1 = getInt12();
aData_Item1 = theHashTable12.find(aKey1);
if(aData_Item1 != null)
System.out.println("FOUND " + aKey1);
else
System.out.println("COULD NOT FIND " + aKey1);
break;
default:
putText12("INVALID ENTRY ");
}
} // END WHILE
} // END MAIN()
public static void putText12(String sst1)
{
System.out.println(sst1);
System.out.flush();
}
public static String getString12() throws IOException
{
InputStreamReader isr123 = new InputStreamReader(System.in);
BufferedReader buff12 = new BufferedReader(isr123);
String s12 = buff12.readLine();
return s12;
}
public static char getChar12() throws IOException
{
String st1 = getString12( );
return st1.charAt(0);
}
public static int getInt12() throws IOException
{
String st1 = getString12();
return Integer.parseInt(st1);
}
} // end class HashDoubleAppImplementation
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.