((( using java ))) In hash table that is based on chaining approach, long linked
ID: 3583915 • Letter: #
Question
((( using java )))
In hash table that is based on chaining approach, long linked list needs more
time to be searched to find or delete an element. To enhance this structure, you need to add a new method called rehash that receives a an integer number represents a threshold so your method will calculate the average number of nodes currently in the table (total number of nodes divided by table size), if this average is greater than threshold (received parameter), your method should duplicate the table size, and rehash all elements according to the new table, otherwise, this method does nothing.
#plz write the code on eclipse or any programming program and test it , thanks in advance
Explanation / Answer
Program:
import java.util.Hashtable;
import java.util.Scanner;
public class Hashing {
public static void main(String[] args) {
float threshold; //Threshold is taken as 70%
int m=0;
System.out.println("Enter table size:");
Scanner s = new Scanner(System.in);
int size = s.nextInt(); // Initial Hash table size
int a[] = new int[10];
System.out.println("Enter the elements:");
for(int i=0;i<a.length;i++){ // Reading elements for putting into HashTable
a[i] = s.nextInt();
}
//Creating Hashtable of Map Interface Type in Collection
Hashtable<Integer, Integer> ht = new Hashtable<Integer, Integer>();
int k=0;
while(a.length > k) { // Iterating through all elements
int value = a[k];
int key = value%size; // Finding the key into hash table
if(ht.containsKey(key)){ // Checking the key whether it already allocated
while(size >= key++){ //Then storing in next empty location
if(!ht.containsKey(key)){
ht.put(key, value); // KEY,VALUE Pair
break;
}
if(key==size){ // If table size is reached last position, to start again from first position
key=0;
}
}
} else {
ht.put(key, value); // If it is new it will keep in Hashtable
}
System.out.println(ht);
// elements of hashtable / size of hashtable >70%
threshold = ((k+1)*100)/size; // Calculating for threshold value
if(threshold>70){
m++;
//System.out.println("Hash Table before rehashing: "+ht);
System.out.println("Threshold is greater than 70%");
System.out.println("**********************************");
ht = new Hashtable<Integer, Integer>();
size = (m+1)*size; // Rehashing the double size of hashtable size
k=-1;
}
k++;
if(m>2) break; // Took upto two Rehashing loops, so m = 2;
}
System.out.println("After rehashing:");
System.out.println(ht);
}
}
OUTPUT:
javac Hashing.java
java Hashing
Enter table size:
7
Enter the elements:
25 26 40 20 13 89 78 65 90 34
{4=25}
{5=26, 4=25}
{6=40, 5=26, 4=25}
{7=20, 6=40, 5=26, 4=25}
{7=20, 6=40, 5=26, 4=25, 1=13}
Threshold is greater than 70%
**********************************
{11=25}
{12=26, 11=25}
{13=40, 12=26, 11=25}
{6=20, 13=40, 12=26, 11=25}
{6=20, 14=13, 13=40, 12=26, 11=25}
{6=20, 5=89, 14=13, 13=40, 12=26, 11=25}
{8=78, 6=20, 5=89, 14=13, 13=40, 12=26, 11=25}
{9=65, 8=78, 6=20, 5=89, 14=13, 13=40, 12=26, 11=25}
{14=13, 13=40, 12=26, 11=25, 9=65, 8=78, 7=90, 6=20, 5=89}
{14=13, 13=40, 12=26, 11=25, 10=34, 9=65, 8=78, 7=90, 6=20, 5=89}
Threshold is greater than 70%
**********************************
{25=25}
{26=26, 25=25}
{40=40, 26=26, 25=25}
{20=20, 40=40, 26=26, 25=25}
{20=20, 40=40, 26=26, 25=25, 13=13}
{20=20, 40=40, 5=89, 26=26, 25=25, 13=13}
{20=20, 40=40, 5=89, 26=26, 36=78, 25=25, 13=13}
{20=20, 40=40, 5=89, 26=26, 36=78, 25=25, 13=13, 23=65}
{20=20, 40=40, 13=13, 36=78, 6=90, 5=89, 26=26, 25=25, 23=65}
{20=20, 40=40, 13=13, 36=78, 34=34, 6=90, 5=89, 26=26, 25=25, 23=65}
After rehashing:
{20=20, 40=40, 13=13, 36=78, 34=34, 6=90, 5=89, 26=26, 25=25, 23=65}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.