Register

GO Classes DPP | GATE CS, DA | Data Structure | Uniform Hashing

• retagged by
190 views
3 3 votes

A hash table has $m$ slots and stores $n$ keys. Assume simple uniform hashing, so each key is equally likely to hash into any slot, independently of other keys. Collisions are resolved by chaining.

What is the probability that the first slot ends up empty?

  1. $\left(\frac{1}{m}\right)^n$
     
  2. $\left(\frac{m-1}{m}\right)^n$
     
  3. $1 - \left(\frac{1}{m}\right)^n$
     
  4. $1 - \left(\frac{m-1}{m}\right)^n$

1 Answer

1 1 vote

For one key, probability that it does not hash into the first slot is:

$\frac{m-1}{m}$

There are $n$ keys, and each key hashes independently.

So, probability that none of the $n$ keys hash into the first slot is:

$\left(\frac{m-1}{m}\right)^n$

Correct option: B.

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

3 3 votes
1 1 answer
208
208 views
GO Classes asked Jul 16
208 views
GO Classes DPP | GATE CS, DA | Data Structure | Expected Non-Empty Slots
A hash table has $m$ slots and stores $n$ keys. Assume simple uniform hashing. Collisions are resolved by chaining.What is the expected number of slots that end up non-em...
2 2 votes
1 1 answer
209
209 views
GO Classes asked Jul 16
209 views
GO Classes DPP | GATE CS, DA | Data Structure | Hashing
Consider the following statements about hash tables.$\text{S1}:$ The worst-case complexity of checking whether an object is present in a hash set is $O(1)$.$\text{S2}:$ T...
4 4 votes
2 2 answers
241
241 views
GO Classes asked Jul 16
241 views
GO Classes DPP | GATE CS, DA | Data Structure | Hashing With Chaining
Insert the integer keys$47, 61, 36, 52, 56, 33, 92$in the given order into a hash table of size $7$.The hash function is:$h(k) = (10k + 4) \bmod 7$Collisions are resolved...
2 2 votes
1 1 answer
192
192 views
GO Classes asked Jul 16
192 views
GO Classes DPP | GATE CS, DA | Data Structure | Collision-Free Hash Parameter
For the keys : $\text{47, 61, 36, 52, 56, 33, 92}$Suppose the hash function is :$h(k) = ((10k + 4) \bmod c) \bmod 7$where $c$ is a positive integer.What is the smallest v...