1,161 views

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$

## 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

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.

### 1 comment

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

Ans: A

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

1 vote