91Ó°ÊÓ

(a)

$H=\{h_{a_1,a_2}:a_1,a_2∈\left[m\right]\}$and$h_{a_1,a_2}=\underset{i=1}{\overset{2}{}}{a}_i.x_{i}modm=(a_1{x}_1+a_2{x}_{2}modm)$

Assume that$x_2≠y_2$.

Now, to prove$H=\{h_{a_1,a_2}:a_1,a_2∈\left[m\right]\}$is universal, it is required to find the probability

$Pr[h_{a_1,a_2}(x_1,x_2)=h_{a_1,a_2}(y_1,y_2)]$

Re write the above equation as follows:

$a_1(x_1−y_1)≡a_2(y_2−x_2)modm$

Select$a_1$randomly from$\left[m\right]$ and assume$c=a_1(x_1−y_1)$.

Then$a_2≡c.{(y_2−x_2)}^{−1}\mathrm{mod}m$,

Now calculate the probability of selectingso that Equation$\left(1\right)$is true.

Thus$a_2≡c.{(y_2−x_2)}^{−1}\text{ }\mathrm{mod}\text{ }m$and obviouslycan be any one of the integers in.$\{0,1,…,m−1\}$ That is$a_2$,havepossible values.

Therefore, the probability of equation $\left(1\right)$holds is$\frac{1}{m}$.

Hence it is proved that given family of hash functions,$H$is universal.

(b)

Consider a family of hash functions$H=\{h_{a_1,a_2}:a_1,a_2\left[m\right]\}$ and

$\begin{array}{c}{h}_{a_{1,}{a}_2}=\underset{i=1}{\overset{2}{∑}}{a}_i.x_i\mathrm{mod}m\\ =a_1{x}_1+a_2{x}_2\mathrm{mod}m\end{array}$

Where$m=2^k$(That is,$m$is even).

From part (a)$H$,is universal and$(a_1{x}_1+a_2{x}_2)≡(a_1{y}_1+a_2{y}_2)\mathrm{mod}m$holds when there exists a unique inverse modulo$m$for $(y_2−x_2)$.

There will be a unique inverse modulo$m$for $(y_2−x_2)$, only if$m$is a prime number.

Since$m=2^k$and it is not a prime number (unless$k=1$), there exist no unique inverse modulo$m$for.

$(y_2−x_2)$

In order to select a hash function randomly from,$H$ need to select two integers

$a_1$and $a_2$randomly from.$\left[m\right]$ The set $\left[m\right]$has totalintegers.

To uniquely represent each number in set,$\left[m\right]$ at most$⌈\log m⌉$bits are required

Where,

$\begin{array}{c}⌈\log m⌉bits=⌈\log 2^k⌉\\ =k\text{ }bits\end{array}$.

Since it is required to choose two integers, the total number of random bits required to select a hash function is$2^k$ bits.

(c)

Consider a family of hash functions$f:\left[m\right]→[m−1]$.

In order to prove the above family of hash functions is universal, it is enough to prove that the probability of colliding any two data items$x$and $y$is$\frac{1}{m}−1$, if the hash function is randomly chosen from the family of hash functions. Where$m−1$is the number of buckets.

Assume$x≠y$and then calculate$P=\mathrm{Pr}[f\left(x\right)=f\left(y\right)]$.

The probability for$f\left(x\right)$ can be any one of integers of$[m−1]$ is$\frac{1}{m−1}$.

Similarly, the probability for$f\left(y\right)$can be any one of integers of $[m−1]$is.$\frac{1}{m−1}$

The probability for the outputs of$f\left(x\right)$and $f\left(y\right)$are same is.data-custom-editor="chemistry" $\frac{1}{m−1}×\frac{1}{m−1}=\frac{1}{{(m−1)}^2}$

However, there are$m−1$ways to be.$f\left(x\right)=f\left(y\right)$

That is$(f\left(x\right)=0,1,2,…,m−2)=(f\left(y\right)=0,1,2,…m−2)$,(total$m−1$ways)

Thus,$P=\underset{i=1}{\overset{m−1}{∑}}\frac{1}{{(m−1)}^2}$

or

$\begin{array}{l}P=(m−1)×\frac{1}{{(m−1)}^2}\\ P=\frac{1}{m−1}\end{array}$

Therefore, it is proved that$H$is universal.

Set $\left[m\right]=\{0,1,2,…,m−1\}$can be mapped to set $[m−1]=\{0,1,2,…,m−2\}$in${(m−1)}^m$ways such that $f$is a function.

Thus, the total number of functions $f:\left[m\right]→[m−1]$is${(m−1)}^m$.

To uniquely represent each function in$H$, at most $⌈\log {(m−1)}^m⌉=m\log (m−1)$bits are required.

Therefore,$m\log (m−1)$bits required to choose a function from$H$.