Fonction de hachage, $h(k) = \lfloor km floor$ est simple et uniforme pour réel $k$ de façon indépendante, distribuée de manière uniforme dans la gamme $0 \leq k < 1$

Question

J'allais à travers le texte d'Introduction aux Algorithmes par Cormen et.al.d'où je suis venu à travers la déclaration suivante:

Si les clés sont connus pour être aléatoire des nombres réels $k$ indépendamment et uniformément distribués dans la gamme $0 \leq k < 1$ la fonction de hachage

$$h(k) = \lfloor km floor$$ satisfait à la condition de simple et uniforme de hachage.

Maintenant ce que je peux comprendre qu'ils sont sans doute compte tenu de l'uniforme disturbution dans le "continu" sens et non pas dans le discret sens.S'il avait été dans la discrète sens alors supposons que, pour $n$ les clés de la probabity fonction de masse (p.m.f) est constante et égale à $1/n$ et donc, il est tout aussi probable pour chaque clé à utiliser dans le hachage n'par yeilding le résultat souhaité.

Mais il semble que nous sorte dans la difficulté, si la période de distribution visé est continue (je me sens tellement à cause de la ligne:"distribués uniformément dans l' la gamme $0 \leq k < 1$")

Laissez $f(x)$ être associée fonction de densité de probabilité (p.d.f) et à partir de l'information donnée, nous avons $f(x)=1$(ce qui est assez facile à trouvé, l'intégration de $f(x)$ dans la gamme $0$ pour $1$ et le prenant avec $1$ et de noter que dans la distribution uniforme de la p.d.f est une constante).

Maintenant que les p.d.f est une constante, mais p.d.f n'est pas la probabilité.Plutôt probabilité à un spectre point est $0$.Maintenant comment utiliser ce résultat pour obtenir à la demande des auteurs.

Ou suis-je totalement à la faute compte tenu de la répartition d'être continue?

(Il n'y est une réponse ici, mais il ne va pas dans ce détail que la question est différente, après tout).

Answer 1

$h\in [m]^U$ satisfait à la fois simple et uniforme de hachage supposition, si lors de l' $x\in U$ est choisi uniformément au hasard, alors $h(x)$ est distribué uniformément sur $[m]$, ou , de manière équivalente $\forall i\[m]:\Pr\limits_{x\in U}[h(x)=i]=\frac{1}{m}$.Dans notre cas, nous avons:

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

Nous avons utilisé le fait que si $x$ est distribué uniformément sur $[0,1]$ alors $\Pr[a\le x\le b]=b-a$ (l'égalité tient tous les quatre combinaisons de $\le$ et $<$).