2
$\begingroup$

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following claim:

Universal Hashing uses randomization.For the example of a compiler's symbol table, we find that the programmer's choice of identifiers cannot now cause consistently poor hashing performance.

Poor performance occurs only when the compiler chooses a random hash function that causes the set of identifiers to hash poorly, but the probability of this situation occurring is small and is the same for any set of identifiers of the same size.

Now let us assume that in the general case( not specifically the compiler example) we have a "Universal class of Hash function" as $\mathscr{H}$ and the set of keys be $K$.

As the situation described ,the poor performance occurs if for a randomly chosen hash function $h\in\mathscr{H}$ the hash function causes collision for each $\binom{|K|}{2}$ pair of keys. Intuitively that the probability of this happening is quite "small" is justifiable. But that the probability is same for all sets K of size n and independent of the actual keys in it was not received by me in an intuitive manner and I thought of finding the probability of such an event and satisfy myself.

From the definition of universal class of hash function we know that,

For each pair of distinct keys $k,l$ the number of functions $h\in \mathscr{H}$ , such that $h(k)=h(l)$ is atmost $\frac{|H|}{m}$ where $m$ is the number of slots in the hash table .i.e. for the set $A=\{h \in \mathscr{H} : h(k)=h(l)\}$ ,

$$|A|\leqslant|\mathscr{H}|/m \tag 1$$

Now from the above we need to find the number of hash functions which causes collision for all pair of keys.

Let $A_{x,y} \subseteq \mathscr{H},$ for $\forall x,y \in K$ such that the keys $x\neq y$, $A_{x,y}$ contains those hash function $h$ such that $h(x)=h(y)$.

Now

$$\lambda = \left| \bigcap\limits_{(x,y\in K)\land (x\neq y)} A_{x,y} \right| (say) \tag 2$$

We know that,

$$\left| \bigcup\limits_{(x,y\in K)\land (x\neq y)} A_{x,y} \right| \leq |\mathscr{H}|\tag 3$$

So the required probability which I am asking for becomes,

$$p=\frac{\lambda}{|\mathscr{H}|}\tag 4$$

Now how to combine $(1), (3)$ to get a bound for $(2)$ and hence get a bound for $(4)$.


I thought of an alternative approach though.

Let $h$ be the hash function chosen at random during the start of the execution of our algorithm. Suppose $X_{x,y}$ be the indicator random variable defined as :

$$X_{x,y} = \begin{cases} 1 &\quad\text{if $h(x)=h(y)$ }\\ 0&\quad\text{otherwise.}\\ \end{cases}$$

Where the randomness is due to the random selection of $h$ and not on the keys. Now by the definition of Universal Hashing, $Pr\{h(x)=h(y)\}\leq \frac{1}{m}$ where $h$ is randomly chosen hash function for keys $x,y$. So $E(X_{x,y})=Pr\{h(x)=h(y)\}\leq \frac{1}{m}$

Let $X$ be the random variable representing the total number of collisions.

$$X=\sum_{(x,y\in K)\land (x\neq y)} X_{x,y}$$

Taking expectations on both sides,

$$E[X]=E\left[ \sum_{(x,y\in K)\land (x\neq y)} X_{x,y}\right]$$

$$\implies E[X]=\sum_{(x,y\in K)\land (x\neq y)} E[X_{x,y}]= \binom{n}{2} E[X_{x,y}]\leq \binom{n}{2}.\frac{1}{m}$$

Now using Markov's Inequality we have,

$$Pr \left\{ X\geq\binom{n}{2}\right\} \leq \frac{E[X]}{\binom{n}{2}} $$

$$\leq \frac{\binom{n}{2}.\frac{1}{m}}{\binom{n}{2}}$$

$$=\frac{1}{m}$$

$$\therefore p=Pr \left\{ X\geq\binom{n}{2}\right\} \leq\frac{1}{m} \quad\text{(independent of the actual keys)}$$

Please help me out with the first approach or is my second approach legit?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.