edited by
10,310 views
19 votes
19 votes

​​​Suppose we are given $n$ keys, $m$ hash table slots, and two simple uniform hash functions $h_{1}$ and $h_{2}.$ Further suppose our hashing scheme uses $h_{1}$ for the odd keys and  $h_{2}$ for the even keys. What is the expected number of keys in a slot?

  1. $\frac{m}{n}$
  2. $\frac{n}{m}$
  3. $\frac{2n}{m}$
  4. $\frac{n}{2m}$
edited by

2 Answers

Best answer
28 votes
28 votes
Answer B

$\color{blue} {\text{Uniform hash function definition : } } Pr[h(x) = i] = 1/m$

which means for every $x$, we have equal probability of mapping to any of slot $i$.

Quick Question-

$\color{red} {\text{Hash function given in question is Uniform ? } } $

Take any slot $i$ and calculate probability of mapping some arbitrary $x$ to $i$?
i.e. $\color{blue} {Pr[h(x) = i] = } \color{red}{?}$

Let the probability of choosing $h_1$ is $p$ and choosing $h_2$ is $1-p$ then

$\Pr[h(x) = i] = \color{red} {p}Pr[h_1(x) = i] + \color{red} {(1-p)} Pr[h_2(x) = i] $
$\Rightarrow Pr[h(x) = i] = \frac{\color{red} {p}}{m} + \frac{\color{red} {1-p}}{m} \text{ (since }h_1\text{ and  }h_2\text{ both are uniform hash functions)}$
$= \frac{1}{m}$

As you see, value of $p$ does not matter but we can calclulate $p$ as $ = \frac{\text{number of even keys}}{\text{Total keys}}$

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Since $h$ is uniform, we can say it will distribute all keys uniformly. This means if there are 50 keys and 10 slots then each slot will get 5 keys. i.e. $\frac{n}{m}$ is answer.

 

But we can do this using probability.

let $X$ = Number of items in slot $\color{red}{1}$. (Note that I am. only talking about some random slot, say slot $\color{red}{1}$ )

 

$  X_i =  \left\{
\begin{array}{ll}
1 & \text{if } i^{th} \text{ item maps to slot 1 } \\ 0& \text{otherwise} \end{array} \right. $

Very easily, we can say $X = X_1 + X_2 + \dots X_n $

They are asking $E[X]$
 

$E[X] = E[X_1 + X_2 + \dots X_n] $

$E[X] = E[X_1] + E[X_2] + \dots E[X_n] $

How to calulate $E[X_i]$ ? – There could be 2 methods, one given below and the other is in first comment.

Once we calculate $P(X_i = 1) \text{ and } P(X_i = 0)$ then finding $E[X_i]$ is straight forward and so $E[X]$

$P(X_i = 1) = \frac{1}{m} $ because whatever happens within black box ( $h1 or h2$), the overall hash function will be uniform.

$E[X_i] =  1 P(X_i = 1) + 0 P(X_i = 0)  = \frac{1}{m} $

Hence,

$E[X] = \frac{n}{m} $
edited by
4 votes
4 votes

m – Hash Table Size

n –  Number of keys 

m – slots = n – keys 

∴ 1-slots = n/m keys/slots .

it is load factor .

1 flag:
✌ Low quality (abir_banerjee)
Answer:

No related questions found