Register

Hashing

1,593 views
4 votes
4 votes

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

User Avatar

4 Answers

3 votes
3 votes
Option c

Probability that slot 0 and 1 are filled =2/m

Probability that slot 0 and 1 are not filled=(1-2/m)

Probability that slot 0 and 1 end up being empty is (1-2/m)^keys =(1-2/m)^3=

((m-2)/m) ^3

check this .. Nythng wrong let me know..
User Avatar
1 votes
1 votes
table of Size M  
XXXXX XXXXX                 

Places Where XXXXX is Written  are not allowed to be filled . That's the Summary of the question

first Insertion , We don't want the element to come at the these two places .

(m-2/m)*(m-2/m)*(m-2/m)

for all the three Insertions.

Answer is C

 

 

 

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
0 votes
0 votes
1 answer
3
smartmeet asked Feb 8, 2017
4,522 views
Hashing
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
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 isa) Less than 1...
User Avatar
0 votes
0 votes
1 answer
4
tishhaagrawal asked Dec 16, 2023
352 views
Made Easy Test Series : Consider an open addressing hashing scheme with m slots and n keys. Assuming uniform hashing, the expected number of empty slots in the hash table for m=7 and n=3 is equal to ____________(Round off to two decimal places)
Below is my approach to solving this question, can anyone please explain if I am doing it the right way?Let X = #free slotssince, m =7 and n = 3So, $4 \leqslant x\leqsla...
User Avatar
Link Copied!