# Hash function, $h(k) = \lfloor km \rfloor$ is simple uniform for real $k$ independently, uniformly distributed in the range $0 \leq k < 1$

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

• $k$ is a continuous random variable with a constant density function, nothing wrong with that. Jun 25, 2020 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 $$<$$).
• can you please say the meaning of the notation $h\in [m]^U$ Jun 25, 2020 at 20:52
• In this context $[m]=\{0,1,...,,m-1\}$ and $[m]^U$ is the set of functions from $U$ to $[m]$. Jun 25, 2020 at 20:53