Redirected
recategorized by
3,072 views
6 votes
6 votes
Consider a hash table using uniform hashing with number of slots as $m=6$ and number of keys, $k=8$. Collisions are resolved by chaining. Assuming direct hashing is used, what is the expected number of slots that ends not being empty?
recategorized by

2 Answers

Best answer
8 votes
8 votes

We want to find expected no. of slots not being empty which 

$= \sum_{i=1}^6 1 \times P(\text{Slot}_i \text{ is not empty})$. 

$P(\text{Slot}_i \text{ is not empty}) = 1 - P(\text{Slot}_i \text{ is empty})$

So, our required expectation $= \sum_{i=1}^6 1 \times (1 - P(\text{Slot}_i \text{ is  empty}))
\\=\sum_{i=1}^6 1 \times \left(1 -  \frac{(6-1)^8}{6^8}\right) 
\\= 6 \times \left(1 - \frac {5^8}{6^8}\right) \\= 4.604$. 

Alternative way

Expected number of non-empty slots
$= 1 . P(1) + 2 . P(2) + \dots + 6 . P(6)$, where $P(i)$ is the probability that exactly $i$ number of slots are non-empty.

Since, collisions are resolved by chaining, if $8$ keys go to the same slot, $5$ other slots will be empty. 

Now, number of favourable cases for $P(i)$ is equal to the number of ways in which we can place $8$ distinct balls into $i$ distinct bins such that no bin is empty. This is given by $i! . S(8, i)$ where $S$ is the Stirling's number of second kind. 

We have $S(1,1) = 1, S(n, r) = S(n-1, r-1) + r \times S(n-1, r)$
So, using this we can get the triangle of Stirling's numbers

 

1
1 1
1 3 1
1 7 6 1
1 15 25 10 1
1 31 90 65 15 1
1 63 301 350 140 21 1
1 127 966 1701 1050 266 28 1

So, if $F(i)$ denote the no. of favourable cases for $P(i)$ 

$F(1) = {}^6C_1 . 1 . 1! = 6$

$F(2) = {}^6C_2 . 127 . 2! = 3810$

$F(3) = {}^6C_3 . 966 . 3! = 115920$

$F(4) = {}^6C_4 . 1701 . 4! = 612360$

$F(5) = {}^6C_5 . 1050 . 5! = 756000$

$F(6) = {}^6C_6 . 266 . 6! = 191520$

So, our expected number 

$= \frac{1 \times 6 + 2 \times 3810 + 3 \times 115920 + 4 \times 612360 + 5 \times 756000 + 6 \times 191520}{6^8}$

$=4.604$

selected by
11 votes
11 votes


Slot =6, keys =8

So Prob. of hashing to a particular slot = 1/m

Prob. of not hashing to a particular slot = (m-1)/m

Prob that particular slot ends up being empty = [(m-1)/m]k

Prob that particular slot is not being empty =1- [(m-1)/m]k

the prob. is same for all slot & hence expected no. will be same for all slots = m[1-[(m-1)/m]k ]

& m=6, & k=8 is given....So put the values you will get = 4.604

Related questions

0 votes
0 votes
1 answer
1
Ram Swaroop asked Jan 27, 2019
1,263 views
Consider the hashing table with 'm' slots and 'n' keys. If the expected number of probes in unsuccessful search is 3. The expected number of probes in a successful search...
0 votes
0 votes
1 answer
3
1 votes
1 votes
1 answer
4
Vishal Goyal asked Dec 6, 2016
671 views
Suppose we used a hash function H(n) to hash ‘n’ distinct elements (keys) into an array T of length ‘m’. What is the expected number of colliding pairs of element...