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

If the keys are known to be random real numbers $k$ independently and uniformly distributed in the range $0 \leq k < 1$ , the hash function

$$h(k) = \lfloor km \rfloor$$ satisfies the condition of simple uniform hashing.

Now what I can understand that they are probably considering uniform disturbution in the "continuous" sense and not in the discrete sense. Had it been in the discrete sense then suppose for $n$ keys the probabity mass function (p.m.f) shall be constant and equal to $1/n$ and so it shall be equally likely for each key to be used in the hashing there-by yeilding the desired result.

But we seem sort of in trouble if the distribution being referred to is continuous (I feel so because of the line: "uniformly distributed in the range $0 \leq k < 1$")

Let $f(x)$ be the associated probability density function (p.d.f) and from the given information we have $f(x)=1$,(which is quite easily found, integrating $f(x)$ in the range $0$ to $1$ and equating it with $1$ and noting that in uniform distribution the p.d.f is a constant).

Now though the p.d.f is a constant but p.d.f is not the probability. Rather probability at a spectrum point is $0$. Now how to use this result to get to the claim of the authors.

Or am I entirely at fault considering the distribution to be continuous?

(There is an answer here, but it does not go into this detail as the question there is different after all).

  • 1
    $\begingroup$ $k$ is a continuous random variable with a constant density function, nothing wrong with that. $\endgroup$ – Ariel Jun 25 '20 at 20:48

$h\in [m]^U$ satisfies the simple uniform hashing assumption if when $x\in U$ is chosen uniformly at random, then $h(x)$ is uniformly distributed over $[m]$, or equivalently $\forall i\in[m]: \Pr\limits_{x\in U}[h(x)=i]=\frac{1}{m}$. In our case we have:

$\Pr[h(x)=i]=\Pr\big[\lfloor mx \rfloor=i\big]=\Pr[i\le mx < i+1]=\frac{i+1}{m}-\frac{i}{m}=\frac{1}{m}$.

We used the fact that if $x$ is uniformly distributed over $[0,1]$ then $\Pr[a\le x\le b]=b-a$ (the equality holds with all four combinations of $\le$ and $<$).

  • $\begingroup$ can you please say the meaning of the notation $h\in [m]^U$ $\endgroup$ – Abhishek Ghosh Jun 25 '20 at 20:52
  • 2
    $\begingroup$ In this context $[m]=\{0,1,...,,m-1\}$ and $[m]^U$ is the set of functions from $U$ to $[m]$. $\endgroup$ – Ariel Jun 25 '20 at 20:53
  • $\begingroup$ thanks for the help. $\endgroup$ – Abhishek Ghosh Jun 25 '20 at 20:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.