0
$\begingroup$

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).

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

1 Answer 1

2
$\begingroup$

$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 $<$).

$\endgroup$
3
  • $\begingroup$ can you please say the meaning of the notation $h\in [m]^U$ $\endgroup$ Jun 25, 2020 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, 2020 at 20:53
  • $\begingroup$ thanks for the help. $\endgroup$ Jun 25, 2020 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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