Please use double-hashing to insert randomly generated keys (as integers) rangin
ID: 3731047 • Letter: P
Question
Please use double-hashing to insert randomly generated keys (as integers) ranging from 0-1000 into an array of size 100 elements. You'll then have to write a function retrieve these hashed keys. Have the retrieval function return the index of the key once it's been found (be sure to return the correct index if we we have a collision and have to probe to a new index!) For the double hashing function, use the one found at the bottom of page 272. Then, use h1(k) = k mod m and h2(k) = 1 + (k mod m') where m=101 and m'=100 I would like you to insert 10 randomly generated keys into your array. Output how many collisions there are total when inserting these numbers into your array, and also the largest number of probes needed to insert one of the keys. Keep track of which key caused this largest number of probes, and use it to test your retrieval function. Output the key you're going to retrieve and the index at which it can be found Repeat the last paragraph of instructions when inserting 25 keys, 50 keys, 75 keys, and 100 keys. 100 keys likely won't complete. Let it run for 1 minute before using Ctrl+C to quit. Make your output clear as to what I'm looking at please Finally, as the last bit of output from your program, write a sentence or two on how the average number of probes needed when inserting keys relates to the average number of probes needed when retrieving keysExplanation / Answer
PROGRAM:
#include <stdio.h>
#include <stdlib.h>
int averageprobes_s=0;
int h[100];
// For Double hashing i used HASH1 FOR first time. if it is full then I used hash1 + i*hash 2
int hash1(int k)
{
int i;
i=k%101;
return i;
}
int hash2(int k)
{
int i;
i=1+(k%100);
return i;
}
int hash3(int k, int j)
{
int i=hash1(k)+j*hash2(k);
i=i%100;
return i;
}
int insert(int key){
int j=0;
int i;
i=hash1(key);
// printf("hello %d key %d ",i,h[i]);
while(h[i] != -1 && j < 100){
j++;
i=hash3(key,j);
}
if(j >= 100){
printf("CAN'T INSERT ");
return -1;
}
else{
h[i]=key;
// printf("%d ",i);
return j;
}
}
int search(int k)
{
int j=0;
int i;
i=hash1(k);
if(h[i] == -1){
printf("NOT FOUND ");
return -1;
else{
while(h[i] != k && j < 100 && h[i] != -1 ){
j++;
i=hash3(k,j);
}
if(h[i] == k){
//averageprobes_s = averageprobes_s + j;
return i;
}
else{
printf("NOT FOUND ");
return -1;
}
}
}
int main(void) {
int probes=0,index=0,collisons=0,a[100],i;
for(i=0;i<100;i++)
h[i]=-1;
for(i=0;i<75;i++){
a[i]=rand()%1000;
int probes_return=insert(a[i]);
if(probes_return > 0)
collisons=collisons+probes_return;
if(probes_return > probes){
probes=probes_return;
index=i;
}
}
printf("total no of collisons for inserting keys is :%d ",collisons);
printf("largest no of probes for inserting random numner %d is : %d ",a[index],probes);
printf("key to to search is :%d ",a[index]);
int key_index=search(a[index]);
if(key_index >= 0)
printf("key %d found at %d position ",a[index],key_index);
printf("%d ",h[key_index]);
printf("VERIFIED ");
// printf("total no of probes for searching keys is :%d ",averageprobes_s);
printf("average no of probes for inserting the keys is greater than the average no of probes required for seraching. This is observed by inserting AND seraching with k keys AnD caluclate the total probes.");
return 0;
}