recategorized
1,888 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$
recategorized

6 Answers

1 votes
1 votes

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

Answer:

Related questions

1 votes
1 votes
7 answers
2
go_editor asked Mar 24, 2020
1,518 views
Which of the following is a valid heap? $a$$b$$c$$d$
0 votes
0 votes
4 answers
4
go_editor asked Mar 24, 2020
989 views
Match the following :$\begin{array}{llll} & \textbf{List – I} & {} & \textbf{List – II} \\ \text{a.} & \text{Absurd} & \text{i.} & \text{Clearly impossible being con...