in DS recategorized
1,161 views
2 votes
2 votes

If $h$ is chosen from a universal collection of hash functions and is used to hash $n$ keys into a table of size $m$, where $n \leq m$, the expected number of collisions involving a particular key $x$ is less than __________.

  1. $1$
  2. $1/n$
  3. $1/m$
  4. $n/m$
in DS recategorized
1.2k views

6 Answers

1 vote
1 vote

If h is any hashing function and is used to hash n keys into a table of size m, where n<=m, the expected number of collisions involving a particular key x is less than 1.

option is A

0 votes
0 votes

Answer is less than 1. Though it is not mentioned in the options tat r given. It is a scenario of Universal Hashing. Please kindly visit d link given below for more information. 

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap12.htm

1 comment

options 2,3,4 are all less than one. Which is correct answer?
0
0
0 votes
0 votes
0 votes
0 votes

THIS IS THEOREM OF UNIVERSAL HASHING

If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n≤m, the expected number of collisions involving a particular key xx is less than 1.

http://www.cs.nmsu.edu/~ipivkina/Spring08cs372/Cormen/chapter12HashTables.htm

Answer:

Related questions