edited by
10,439 views
54 votes
54 votes

Consider a hash table with $n$ buckets, where external (overflow) chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a particular bucket is $\frac{1}{n}$. The hash table is initially empty and $K$ distinct values are inserted in the table.

  1. What is the probability that bucket number $1$ is empty after the $K^{th}$ insertion?
  2. What is the probability that no collision has occurred in any of the $K$ insertions?
  3. What is the probability that the first collision occurs at the $K^{th}$ insertion?
edited by

6 Answers

Best answer
60 votes
60 votes
  1. Probability that buckets other than $1$ are selected $= \dfrac{n-1}{n}$
    This should happen $k$ times and each of the $k$ events are independent so $\dfrac{(n-1)^k}{n^k}$
     
  2. When $k=1,$ probability of no collision $= \dfrac{n}{n}$ (for only one insert, there can be no collission)
    For $k=2$ probability of no collision $= \dfrac{n}{n}\times \dfrac{n-1}{n}$
    For $k=n$ probability of no collision $= \dfrac{n}{n}\times \dfrac{n-1}{n}\times\dfrac{n-2}{n}\times \ldots \times \dfrac{n-k+1}{n}$ for $k\leq n$
    For $k>n$ probability of no collision $= 0$ (even though we are using chaining without a collision a chain cannot start)
     
  3. Probability of first collision at $(k=1) $ $  = \dfrac{k-1}{n}$
    Probability of first collision at $(k=2) $ $  = \dfrac{n}{n} \times \dfrac{k-1}{n}$
    Probability of first collision at $(k=3) $  $= \dfrac{n}{n} \times \dfrac{n-1}{n} \times \dfrac{k-1}{n}$
    Probability of first collision at $(k\leq n)$  $ = \dfrac{n}{n} \times \dfrac{n-1}{n}\times\dfrac{n-2}{n} \times \ldots \times \dfrac{n-k+2}{n} \times \dfrac{k-1}{n} $
    Probability of first collision at $(k =  n+1)$  $ = \dfrac{n}{n} \times \dfrac{n-1}{n}\times\dfrac{n-2}{n} \times \ldots \times \dfrac{1}{n} \times \dfrac{n}{n} $
    For $k>n+1$  probability of first collision $= 0$ (as it should have definitely happened in one of the previous $(n+1)$ insertions.
edited by
32 votes
32 votes
Given that A hash table contains 'n' buckets, Chaining is used to resolve the collisions and Initially Hash table is Empty.

The Probability that a key value is hashed to a particular bucket is $\frac{1}{n}$

we need to insert K distinct values into the hash table.

there are 'n' buckets, named as bucket 1, bucket 2, bucket 3,..... bucket 'n'

 

A) What is the probability that bucket number 1 is empty after the K$^{th}$ insertion?

after inserting one value in to the hash table, what is the probability that " bucket 1" is empty ?

there are "(n-1)" buckets excepts bucket 1, So it lead to $\color{red}{(\frac{n-1}{n})}$

after inserting second value in to the hash table, what is the probability that " bucket 1" is empty ?

there are "(n-1)" buckets excepts bucket 1 ( we don't care even it is collision in other bucket ) , So it lead to $\color{red}{(\frac{n-1}{n})}(\frac{n-1}{n})$

after inserting third value in to the hash table, what is the probability that " bucket 1" is empty ?

there are "(n-1)" buckets excepts bucket 1, So it lead to $\color{red}{(\frac{n-1}{n})^2}(\frac{n-1}{n}) = \color{red}{(\frac{n-1}{n})^3}$

after inserting  K$^{th}$ value, probability that " bucket 1" is empty = $\color{red}{(\frac{n-1}{n})^{(K-1)}}(\frac{n-1}{n}) = \color{red}{(\frac{n-1}{n})^K}$

 

B) What is the probability that no collision has occurred in any of the K insertions?

for inserting one value in to the hash table, we have 'n' buckets ==> map to any bucket = $\color{red}{n}.\frac{1}{n}$

for inserting second value in to the hash table, we have '(n-1)' buckets due to the previously mapped bucket we can't use = $\color{green}{\frac{n}{n}}.\color{red}{(n-1)}\frac{1}{n}$

for inserting third value in to the hash table, we have '(n-2)' buckets due to the previously mapped bucket we can't use = $\color{green}{\frac{n}{n}}.\color{green}{\frac{(n-1)}{n}}.\color{red}{(n-2)}.\frac{1}{n}$

........

for inserting (K-1)$^{th}$ value in to the hash table, we have '(n-(k-2))' buckets due to the previously mapped bucket we can't use =

$\color{green}{\frac{n}{n}.\frac{(n-1)}{n}.\frac{(n-2)}{n}.....\frac{(n-(K-3))}{n}}..\color{red}{(n-(K-2))}\frac{1}{n}$

for inserting K$^{th}$ value in to the hash table, we have '(n-(k-1))' buckets due to the previously mapped bucket we can't use = $\color{green}{\frac{n}{n}.\frac{(n-1)}{n}.\frac{(n-2)}{n}.....\frac{(n-(K-2))}{n}}..\color{red}{(n-(K-1))}\frac{1}{n}$

 

Note :-

if K > n, then there should be collision.

 

C) What is the probability that the first collision occurs at the K$^{th}$ insertion?

so upto K-1 we don't have any collision... and at K$^{th}$ insertion we have to collision.

for collision at K$^{th}$ insertion, we have to choose any (K-1) buckets which are previously mapped.

= $\color{green}{\frac{n}{n}.\frac{(n-1)}{n}.\frac{(n-2)}{n}.....\frac{(n-(K-2))}{n}}..\color{red}{(K-1)}\frac{1}{n}$

 

Note :-

if K = n+1, then it must be collision. So K > n+1 can't be the first collision
edited by
21 votes
21 votes

We can redefine the above problem using definition of function

we have two set , A={1,2,...k} B={1,2,....n}   

Now a hash function maps one element of set A to exactly one element of set B.

Total Mappings=No.of functions from set A to Set B=n^k

1. probability that bucket number 1 is empty after the Kth insertion

           Total functions from set A to set B-{1}/All possible functions=(n-1)^k/n^k

2. probability that no collision has occurred in any of the K insertions

                      Total one-to-one function from set A to set B/All possible functions=P(n,k)/n^k           ,P means permutation

3.probability that the first collision occurs at the Kth insertion

 (Total one-to-one function from set A-{k} to set B)*(No of ways kth element can map such that collision occur)/All possible functions=p(n,k-1)*(k-1)/n^k

5 votes
5 votes
$a)$ $\dfrac{n-1}{n}$

$b)$ $\dfrac{n}{n}\times \dfrac{n-1}{n}\times \dfrac{n-2}{n}............\times \dfrac{n-(k-1)}{n}$

$c)$ $\underbrace{\dfrac{n}{n}\times \dfrac{n-1}{n}\times \dfrac{n-2}{n}.....\times \dfrac{n-(k-2)}{n}}\times \underbrace{\dfrac{k-1}{n}}$

      $no\ collisions\ till\ (k-1)\ insertions$           $k^{th}\ insertion$

 

$But\ k^{th}\ insertion\ must\ collide\ with\ any\ one\ of\ those\ (k-1)\ insertions $

Related questions

45 votes
45 votes
6 answers
4
Kathleen asked Sep 29, 2014
8,815 views
Let $G$ be the graph with $100$ vertices numbered $1$ to $100$. Two vertices $i$ and $j$ are adjacent if $\vert i-j \vert =8$ or $\vert i-j \vert=12$. The number of con...