Hash-Funktion, $ H (k)=lfloor KM \ Rfloor $ ist einfacher Uniform für echte $ K $ unabhängig, einheitlich im Bereich von $ 0 \ leq k <1 $ verteilt

Question

Ich ging durch den Text Einführung in Algorithmen von Cormmen et. al wo ich auf die folgende Aussage gestoßen bin:

Wenn bekannt ist, dass die Tasten als zufällige RECHNE-Nummern $ K $ unabhängig und gleichmäßig im Bereich $ 0 \ LEQ verteilt sind k <1 $ , die Hash-Funktion

$$ h (k)=lfloor KM \ rfloor $$ erfüllt den Zustand einfacher einheitlicher Hashing.

Nun, was ich verstehen kann, dass sie wahrscheinlich einheitliche Störungen im "kontinuierlichen" Sinn und nicht im diskreten Sinne in Betracht ziehen. Hatte es im diskreten Sinne gewesen, nehme an, anzunehmen, dass der $ N $ Schlüssel der Wahrscheinlichkeitsmassenfunktion (PMF) ist konstant und gleich dem $ 1 / N $ und so ist es gleichermaßen wahrscheinlich, dass jeder Schlüssel in dem Hashing verwendet wird - durch das gewünschte Ergebnis.

Aber wir scheinen irgendwie in Schwierigkeiten zu sein, wenn die Verteilung auf kontinuierlich bezeichnet wird (ich fühle mich so wegen der Linie: "Uniform in den Bereich $ 0 \ leq k <1 $ ")

$ F (x) $ Seien Sie die zugehörige Wahrscheinlichkeitsdichtefunktion (PDF) und aus den angegebenen Informationen, die wir haben $ f (x)= 1 $ , (das leicht fundiert ist, integriert, $ f (x) $ im Bereich $ 0 $ bis $ 1 $ und gleichermaßen mit $ 1 $ und deuten darauf hin In der gleichmäßigen Verteilung ist das PDF ständig).

Nun, obwohl das p.d.f eine konstante, aber p.d ist nicht die Wahrscheinlichkeit. Die Wahrscheinlichkeit an einem Spektrumpunkt ist $ 0 $ . Nun, wie man dieses Ergebnis nutzt, um an den Anspruch der Autoren zu gelangen.

oder bin ich ganz in der Ansicht, dass die Verteilung kontinuierlich ist?

(es gibt eine Antwort hier , aber es geht nicht in dieses Detail, da die Frage anders ist schließlich).

Answer 1

$ h \ in [m] ^ ^ u $ Erfüllt die einfache einheitliche Hashing-Annahme, wenn $ x \ in u$ wird nach dem Zufallsprinzip gleichmäßig ausgewählt, dann ist $ h (x) $ einheitlich über $ [m] verteilt$ oder äquivalent $ \ Vorall i \ in [m]: \ pr \ limits_ {x \ in u} [h (x)= i]=frac {1} {m} $ .In unserem Fall haben wir:

$ \ pr [h (x)= i]=PR \ Big [\ lfloor mx \ rfloor= i \ big]=pr [i \ le mx .

Wir haben die Tatsache verwendet, dass, wenn $ x $ einheitlich über $ [0,1] $ dann $ \ pr [a \ le x \ le b]= BA $ (Die Gleichheit gilt mit allen vier Kombinationen von $ \ le $ und $ <$ ).