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 DS hashing data-structures chaining uniform-hashing + – smartmeet asked Feb 8, 2017 smartmeet 4.5k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Smriti012 commented Feb 8, 2017 reply Follow Share Option A?? 0 votes 0 votes smartmeet commented Feb 8, 2017 reply Follow Share yes, explain plz! 0 votes 0 votes Smriti012 commented Feb 8, 2017 reply Follow Share According to me, Because load factor <=1 Correct me if I am wrong! 0 votes 0 votes bad_engineer commented Feb 8, 2017 reply Follow Share is there any relation between load factor and collision??? 0 votes 0 votes Please log in or register to add a comment.
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. :) Devshree Dubey answered Feb 9, 2017 • selected Feb 10, 2017 by smartmeet Devshree Dubey comment Share Follow See all 0 reply Please log in or register to add a comment.