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/n$ $1/m$ $n/m$ DS ugcnetjan2017ii cryptography hashing data-structures + – go_editor asked Mar 24, 2020 recategorized May 24, 2020 go_editor 1.9k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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 Prasanjeet Ghosh answered Apr 25, 2018 Prasanjeet Ghosh comment Share Follow See all 0 reply Please log in or register to add a comment.
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 Devshree Dubey answered Feb 4, 2017 Devshree Dubey comment Share Follow See 1 comment See all 1 1 comment reply Sankaranarayanan P.N commented Jul 27, 2017 reply Follow Share options 2,3,4 are all less than one. Which is correct answer? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Ans: A ref: https://gateoverflow.in/45237/hashing rishu_darkshadow answered Sep 2, 2017 rishu_darkshadow comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 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 Mohit Kumar 6 answered May 7, 2020 Mohit Kumar 6 comment Share Follow See all 0 reply Please log in or register to add a comment.