UGC NET CSE | January 2017 | Part 2 | Question: 24

Question

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 __________.

• A. $1$
• B. $1/n$
• C. $1/m$
• D. $n/m$

Answer 1

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 2

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

Comments

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

Answer 3

Ans: A

ref: https://gateoverflow.in/45237/hashing

Answer 4

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