Virtual Gate Test Series: Algorithms - Hash Table(Linear Probing)

Question

Comments

References:

• http://ice-web.cc.gatech.edu/ce21/1/static/audio/static/pythonds/SortSearch/Hashing.html
• https://www.cs.vu.nl/~tcs/ds/lecture6.pdf

Answer 1

hf(key)= key mod 8

hf(10)= 2 (collision) then apply

(hf(key)+i) mod m where i represent no of time collision occurs.

hf(10)+1)mod 8=3 (collision)

hf(10)+2) mod 8=4(collision)

hf(10)+3) mod 8=5 (store 10 at index 5)

now similarly for element 5 there will be 2 collisions and 5 will be stored at index 7.

for element 15 again 2 collisions and 15 will be stored at index 1.

hence total 7 collisions.

Answer 2

order is 10,5,15.

now size of table is 8.

10%8 = 2.

at first it will go to 2,now 2 is occupied 1st collision,next it will go 3,same happened 2nd collision,next it will go 4,3rd collision,now it will go to 5,it is empty so 10 took that position. so for inserting 10  , 3 collision has occured.

5 % 8 = 5.

now at first  it will go to 5,but it is occupied ,so it will go to 6,but it is occupied also ,next it will go to 7,it is empty,so 5 can take that place.  so for inserting 5  , 2 collision has occured.

15 % 8 = 7

now at first  it will go to 7,but it is occupied ,so it will go to 0,but it is occupied also ,next it will go to 1,it is empty,so 15 can take that place.  so for inserting 15  , 2 collision has occured.

total =3 + 2 + 2 =7 collisions