Register

Hashing

4,532 views
0 votes
0 votes
If h is any hashing function and is used to hash n keys into a table of size m, here n<=m, the expected number of collisions involving a particular key x is

a) Less than 1
b) Less than n
c) Less than m
d) Less than n/2
User Avatar

1 Answer

Best answer
2 votes
2 votes

Ans. Option A - less than 1.

This is a theorem in 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 x is less than 1."

Reference: You can check the "Universal Hashing" section of the following link (for details):
http://www.cs.nmsu.edu/~ipivkina/Spring08cs372/Cormen/chapter12HashTables.htm

And a simiar question has been asked earlier too. 

Please refer Cormen on Algorithm for further reading. Yeah!!!

Refer d link below as well:

https://gateoverflow.in/45237/hashing

I hope d explanation helps u. :)

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
Rahul_Rathod_ asked Dec 28, 2018
422 views
hashing
A) (1-(N / K)) ^ r b) (1-(K / N)) ^ r c) (1+(N / K)) ^ r-1 d) (1-(K / N)) ^ r-1
A) (1-(N / K)) ^ r b) (1-(K / N)) ^ r c) (1+(N / K)) ^ r-1 d) (1-(K / N)) ^ r-1
User Avatar
1 votes
1 votes
0 answers
2
hrcule asked Aug 9, 2018
513 views
Hashing
Suppose we used a hash fu action H(n) to hash n distinct elements (key) into an array T of length m. What is expected number of collision, if simple uniform hashing is used.
Suppose we used a hash fu action H(n) to hash n distinct elements (key) into an array T of length m. What is expected number of collision, if simple uniform hashing is us...
User Avatar
4 votes
4 votes
4 answers
3
Shubham Kumar Gupta asked Dec 3, 2017
1,594 views
Hashing
Suppose you insert three keys into a hash table with m slots. Assuming the simple uniform hashing assumption, and given that collisions are resolved by chaining, what is the probability that both slots 0 and 1 are empty? (A) (m−2) /(m−1) (B) (m−2) /m (C) ((m−2) /m )3 (D) None
Suppose you insert three keys into a hash table with m slots. Assuming the simple uniform hashing assumption, and given that collisions are resolved by chaining, what is ...
User Avatar
Link Copied!