1,241 views
0 votes
0 votes

Consider an empty lash table of size = 10. The elements (12, 32, 25, 37, 46, 50, 47) are to be inserted, The hash function is (2x + 1) mod 10 and linear probing resolution technique is used let x be the no. of empty slots and y be the no. of collision then what is the value of 10y + x?
[Collisions on linear probed slot is counted as separate collisions]

Your Answer:

53

Correct Answer: 73    Status: incorrect

1 Answer

0 votes
0 votes

Keys are gives as 12,32,25,37,46,50,47.

Hash function H(k)=(2x+1)%10

CRT= Linear probing

Hash table using Linear probing
Index value
0  
1   51
2   50
3   46
4  
5    5
6   32
7   37
8 47
9  

LP(k,i)=(H(k)+i)%10

LP(12,0) = (5+0)%10 =5  

LP(32,0) = (5+0)%10 =5 (Collision)

LP(32,1) = (5+1)%10 =6

LP(25,0) = (1+0)%10 =1

LP(37,0) =(5+0)%10 =5 (Collision)

LP(37,1) = (5+1)%10 =6 (Collision)

LP(37,0) = (5+2)%10 =7

LP(46,0) = (3+0)%10 =3

LP(50,0) =(1+0)%10 =1 (Collision)

LP(50,1) = (2+0)%10 =2 

LP(47,0) = (5+0)%10 =5 (Collision)

LP(47,1) = (5+0)%10 =6 (Collision)

LP(47,1) = (5+0)%10 =7 (Collision)

LP(47,1) = (5+0)%10 =8

number of empty slot (X) =3

number of collision(Y) =7

so 10Y+X= 73 


Related questions

0 votes
0 votes
1 answer
1
tishhaagrawal asked Dec 16, 2023
311 views
Below is my approach to solving this question, can anyone please explain if I am doing it the right way?Let X = #free slotssince, m =7 and n = 3So, $4 \leqslant x\leqsla...
4 votes
4 votes
1 answer
4
Rohan Mundhey asked Nov 6, 2016
1,336 views