13,734 views
0 votes
0 votes
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 .

1 Answer

1 votes
1 votes
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

Related questions

0 votes
0 votes
0 answers
3
Desert_Warrior asked Mar 11, 2016
720 views
Consider a hash table with 'm' slots that uses chaining for collision resolution. the table is initially empty. What is probability that after 4 keys are inserted then at...
0 votes
0 votes
0 answers
4
Na462 asked Sep 15, 2018
743 views
Which of following is true ?A. A secure hash function can never produce any collisions.B. Cryptographic function is deterministicC. Host using DHCP on wired network can b...