Multi Choice Type QuestionConsider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5?Note: This question was asked in Gate CS Exam.Marks : 1Negative Marks : 0Answer here56710
Question
Multi Choice Type QuestionConsider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5?Note: This question was asked in Gate CS Exam.Marks : 1Negative Marks : 0Answer here56710
Solution
This question is based on the concept of the Birthday Paradox. The Birthday Paradox states that if there are n number of possibilities, after approximately √n trials, the probability of a collision (two trials resulting in the same outcome) is more than 50%.
In this case, the hash table size is 20. So, the number of possibilities (n) is 20.
The number of keys after which the probability of collision exceeds 0.5 is approximately √n.
So, √20 is approximately 4.47. But since we can't have a fraction of a key, we round this up to the nearest whole number, which is 5.
Therefore, after hashing 5 keys, the probability that any new key hashed collides with an existing one will exceed 0.5. So, the answer is 5.
Similar Questions
Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5?
What is the probability of a collision when hashing n keys into a hash table of size m, assuming that the hash function produces a uniform random distribution?
A good hash function should distribute keys uniformly across the hash table. Group of answer choicesTrueFalse
Collisions can be completely avoided in a hash table by choosing a perfect hash function. Group of answer choicesTrueFalse
he problem of collisions in hash algorithms relates to a mathematical problem called the ______________.This type of question contains radio buttons and checkboxes for selection of options. Use Tab for navigation and Enter or space to select the option.optionABirthday ParadoxoptionBMessage DigestoptionCSecure HashoptionDInstruction Pointer
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.