This is java Linear-probing distribution. Write a program, HashProbing.java, tha
ID: 3604249 • Letter: T
Question
This is java
Linear-probing distribution.
Write a program, HashProbing.java, that inserts N/2 random int keys into an array of size N using the linear probing strategy described in the context of hash tables. Note: we're not actually hashing an entry here, just imagining that we've been given the results of some hash function for N/2 elements, where the hash function is randomly distributed.
Next, we wish to compute the average cost for a search miss in the resulting partly-filled array. In other words, suppose a new element that doesn't match one of the hashed elements is given to us, and the hash function maps it to a random location in the array; how many probes will be required to recognize that this entry does not have a match? (remember: once a hashed search lands on a filled cell, it must proceed along sequential positions until it finds an empty one)
Do this for N = 103, 104, 105, 106. Discuss the extent to which your results validate Proposition M in the book (p 473): In a linear-probing hash table with M lists and N = M keys, the average number of probes (under Assumption J) required is
for search hits and search misses (or inserts), respectively. Capture your discussion in the README file.
Explanation / Answer
import java.util.Arrays;
import java.util.Scanner;
public class HashProbing {
//hash table
static int[] HashTable;
//size of hash table
static int N;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
System.out.println("Enter the size of hash table. ");
N = in.nextInt();
HashTable = new int[N];
Arrays.fill(HashTable, 0);
//example insertion
System.out.println(insertElement(2));;
System.out.println(insertElement(7));;
System.out.println(insertElement(6));;
System.out.println(insertElement(5));;
//example search
System.out.println(search(7));
System.out.println(search(9));
}
//insert function for hash table
public static int insertElement(int e){
if(HashTable[e%N]==0){HashTable[e%N] = e;return (e%N);}
else{
int i = 1;
do{
if(HashTable[(e%N)+i]==0){HashTable[(e%N)+i] = e; return (e%N)+i;}
else{i++;}
}while((e%N)+i < N);
if(((e%N)+i == N)){
int j=0;
do{
if(HashTable[j]==0){HashTable[j] = e; return j;}
else{j++;}
}while(j<(e%N));
}
}
return -1;
}
//searching an element in hash table
public static int search(int e){
int misses=0;
if(HashTable[e%N]==e){return (e%N);}
else{
misses++;
int i = 1;
if(((e%N)+i != N)){
do{
if(HashTable[(e%N)+i]==e){return (e%N)+i;}
else{i++;misses++;}
}while((e%N)+i < N);
}
if(((e%N)+i == N)){
int j=0;
do{
if(HashTable[j]==e){return j;}
else{j++;misses++;}
}while(j<(e%N));
}
}
return -1;
}
//finding number of misses for an element in hash table
public static int find_misses(int e){
int misses=0;
if(HashTable[e%N]==e){return misses;}
else{
misses++;
int i = 1;
if(((e%N)+i != N)){
do{
if(HashTable[(e%N)+i]==e){return misses;}
else{i++;misses++;}
}while((e%N)+i < N);
}
if(((e%N)+i == N)){
int j=0;
do{
if(HashTable[j]==e){return misses;}
else{j++;misses++;}
}while(j<(e%N));
}
}
return misses;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.