1,618 views
1 votes
1 votes
Consider a hash table of size 10 that uses open addressing with the linear probing. Let h(k)=K mod10 be the hash function used .A sequence of records wit keys:83,84,95,74,23,86,41,62,72   is inserted into initially empty hash table ,the bin of which are indexed from 0 to  9 .the number of unsuccessful probes to find the index of bins  which contains last element

1 Answer

3 votes
3 votes

Hash table after inserting: 83,84,95

0  
1  
2  
3 83
4 84
5 95
6  
7  
8  
9  

When inserting 74, location 4 is already filled, so we move to next location, the first location which is free is 6. Insert it there.

0  
1  
2  
3 83
4 84
5 95
6 74
7  
8  
9  

Similarly entering other elements: 23,86,41,62

0  
1 41
2 62
3 83
4 84
5 95
6 74
7 23
8 86
9  

Now when inserting the last element 72:

0  
1 41
2                        62 <-first probe
3 83 <-2nd probe
4 84 <-3rd probe
5 95 <-4th probe
6 74 <-5th probe
7 23 <-6th probe
8 86 <-7th probe
9 72 <- 8th probe (success)

So, total 7 unsuccessful probes for entering the last element.

Related questions

0 votes
0 votes
1 answer
4
srestha asked Jan 27, 2019
263 views
void foo(int n) { if(n==1) printf("#"); for(i=0;i<n;i++) foo(n-1); }Number of time # will be printed , when foo(7) is called_________