Register

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

• retagged by
163 views
2 2 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

0 0 votes

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
181
181 views
GO Classes asked Jul 16
181 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
176
176 views
GO Classes asked Jul 16
176 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
182
182 views
GO Classes asked Jul 16
182 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
151
151 views
GO Classes asked Jul 16
151 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...