Hash Function

Question

Which of the following is the least suitable hash function H(x) where X is some non negative integer ?

1. h(k) =k%n

2.h(k) =k*k %n

3.h(k)=(gcd(k+1,2k+2) +k ) %n

Linear probing is used for collision resolution .

Comments

Is the ans option(3) ?

---

Do not know the answer.

---

Could you please add some more details to the question, such as the range of values that k or n can take.. ?

Answer 1

Considering k from 0 to 9 and n=10

Case(1): h(k)=k%10

0%10=0,1%10=1,2%10=2 similarly 9%10=9

Collision rate=0

Case(2):h(x)=k*k%10

(0*0)%10=0

(1*1)%10=1

(2*2)%10=4

(3*3)%10=9

(4*4)%10=6

(5*5)%10=5

(6*6)%10=6

(7*7)%10=9

(8*8)%10=4

(9*9)%10=1

Collision rate=4/10

Case(3):h(k)=(gcd(k+1),(2k+2)+k)%10

0--->(gcd(1,2)+0)%10=1

1-->(gcd(2,4)+1)%10=3

2-->(gcd(3,6)+2)%10=5

3-->(gcd(4,8)+3)%10=7

4-->(gcd(5,10)+4)%10=9

5-->(gcd(6,12)+5)%10=1

6-->(gcd(7,14)+6)%10=3

7-->(gcd(8,16)+7)%10=5

8-->(gcd(9,18)+8)%10=7

9-->(gcd(10,20)+9)%10=9

Collision rate=5/10

Since collision rate is highest for case(3), it is least likely to be selected as a hash function

Comments

But mam here it is said that we have to use linear probing for collision resolution so why should we consider the effect of clustering?

---

Primary clustering occurs in case of linear probing also

PS: I am also a fellow aspirant like you not mam

---

Yes only primary clustering not secondary clustering but I think we should give much preference to collision resolution than clustering