Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Consider a hash function that distributes key...
Start Learning for Free
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.
- a)5
- b)6
- c)7
- d)10
Correct answer is option 'D'. Can you explain this answer?
Verified Answer
Consider a hash function that distributes keys uniformly. The hash tab...
For each entry probability of collision is 1/20 {as possible total spaces =20, and an entry will go into only 1 place}
Say after inserting x values probability becomes ½
(1/20).x = ½
X=10
Say after inserting x values probability becomes ½
(1/20).x = ½
X=10
Most Upvoted Answer
Consider a hash function that distributes keys uniformly. The hash tab...
Solution:
Given, the hash table size is 20.
Let the probability of collision after hashing 'n' keys be p(n).
We need to find the value of 'n' such that p(n) > 0.5.
Since the hash function distributes keys uniformly, the probability of collision between any two keys is 1/m, where m is the size of the hash table.
Let's assume that 'n' keys have been hashed already. Then, the number of possible pairs of keys that could collide is n(n-1)/2. Each pair has a collision probability of 1/20.
Therefore, the probability of collision after hashing 'n' keys is given by:
p(n) = n(n-1)/2 * 1/20 = n(n-1)/40
To find the value of 'n' such that p(n) > 0.5, we need to solve the following inequality:
n(n-1)/40 > 0.5
Simplifying this inequality, we get:
n^2 - n - 20 > 0
Solving for 'n' using the quadratic formula, we get:
n > (1 + sqrt(81))/2 or n < (1="" -="" />
n > 9.06 or n < />
Since 'n' is a positive integer, we can ignore the negative solution.
Therefore, the smallest integer value of 'n' that satisfies the inequality is:
n = 10
Hence, after hashing 10 keys, the probability that any new key hashed collides with an existing one exceeds 0.5.
Given, the hash table size is 20.
Let the probability of collision after hashing 'n' keys be p(n).
We need to find the value of 'n' such that p(n) > 0.5.
Since the hash function distributes keys uniformly, the probability of collision between any two keys is 1/m, where m is the size of the hash table.
Let's assume that 'n' keys have been hashed already. Then, the number of possible pairs of keys that could collide is n(n-1)/2. Each pair has a collision probability of 1/20.
Therefore, the probability of collision after hashing 'n' keys is given by:
p(n) = n(n-1)/2 * 1/20 = n(n-1)/40
To find the value of 'n' such that p(n) > 0.5, we need to solve the following inequality:
n(n-1)/40 > 0.5
Simplifying this inequality, we get:
n^2 - n - 20 > 0
Solving for 'n' using the quadratic formula, we get:
n > (1 + sqrt(81))/2 or n < (1="" -="" />
n > 9.06 or n < />
Since 'n' is a positive integer, we can ignore the negative solution.
Therefore, the smallest integer value of 'n' that satisfies the inequality is:
n = 10
Hence, after hashing 10 keys, the probability that any new key hashed collides with an existing one exceeds 0.5.
Free Test
FREE
| Start Free Test |
Community Answer
Consider a hash function that distributes keys uniformly. The hash tab...
Consider a hash function that distributes key uniformly the hash table size is 20 and exceed 0.5
ans 50 by 20 10 ans
ans 50 by 20 10 ans
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Top Courses for Computer Science Engineering (CSE)View all
Question Description
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.a)5b)6c)7d)10Correct answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2025 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about 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.a)5b)6c)7d)10Correct answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2025 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for 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.a)5b)6c)7d)10Correct answer is option 'D'. Can you explain this answer?.
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.a)5b)6c)7d)10Correct answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2025 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about 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.a)5b)6c)7d)10Correct answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2025 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for 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.a)5b)6c)7d)10Correct answer is option 'D'. Can you explain this answer?.
Solutions for 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.a)5b)6c)7d)10Correct answer is option 'D'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE).
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of 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.a)5b)6c)7d)10Correct answer is option 'D'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
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.a)5b)6c)7d)10Correct answer is option 'D'. Can you explain this answer?, a detailed solution for 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.a)5b)6c)7d)10Correct answer is option 'D'. Can you explain this answer? has been provided alongside types of 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.a)5b)6c)7d)10Correct answer is option 'D'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice 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.a)5b)6c)7d)10Correct answer is option 'D'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up
within 7 days!
within 7 days!
Takes less than 10 seconds to signup