retagged by
714 views
1 votes
1 votes
consider a hash table with 8 slots that uses chaining for collision resolution.The table is initially empty. What is the probability that after 4 keys are inserted, atleast a chain of size 3 is created?(assume simple uniform hashing is used)

a. 29*8-3

b.8-4

c 8-3

d 3*8-1
retagged by

1 Answer

0 votes
0 votes
its prob=

all 4 keys will go to same slot + 3 keys will go to same slot and 1 key will go to any one of the 7 slot

=1/8*1/8*1/8*1/8 + 1/8*1/8*1/8*7/8

=1/8^4(1+7)

=1/8^-3

answer should be (c)

Related questions

0 votes
0 votes
1 answer
1
Anshul_S asked Oct 26, 2016
461 views
Given a hash table with 6 keys and 10 slots, with simple uniform hashing. If collisions are resolved by chaining then the probability that first slot ends up empty?
0 votes
0 votes
1 answer
2
qwertyui asked Sep 24, 2016
428 views
what is the expected number of probs requires when inserting an element into an open address hash table with load factor x (assume uniform hashing)a 1/(1-x)b 1/(1+x)c 1/x...
0 votes
0 votes
1 answer
3
tishhaagrawal asked Dec 16, 2023
309 views
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...