Berechnung der Gleichverteilung

Ideal wäre eine absolut gleiche Verteilung ohne Kollisionen, was allein durch den Hash-Algorithmus selbst unmöglich ist und nur durch diverse Hilfsmittel erreicht werden kann. Der worst-case wäre die Abbildung aller Schlüssel auf eine einzige Adresse der Tabelle. In der Praxis läßt sich bestenfalls eine zufällige Verteilung erreichen, welche natürlich Kollisionen beinhaltet. Diese Wahrscheinlichkeit der Verteilungen kann man mit Hilfe der Poisson-Verteilung annähernd vorhersagen: Die Formel dafür sieht wie folgt aus:

$\begin{displaymath}p(x)=\frac{\left(r/N\right)^x *~ e^{-\left(r/N\right)}}{x!}\end{displaymath}$

N= die Anzahl der verfügbaren Adressen
r= die Anzahl der zu speichernden Datensätze
x= die Anzahl der Datensätze, die auf eine gegebene Adresse verhasht werden.
p(x) gibt die Wahrscheinlichkeit an, daß einer gegebenen Adresse x Datensätze zugeordnet werden, vorausgesetzt, sie wurde auf alle Schlüssel angewandt.
r/N ergibt die Packungsdichte, bzw. die Anzahl an Datensätzen pro Speicherplatz.
Anhand der Formel wird ersichtlich, daß die Packungsdichte wesentlichen Einfluß auf das Auftreten von Kollisionen hat.

Beispiel

Gegeben seien N=3000 Adressen, r=2500 Datensätze.
Wenn wir berechnen wollen, wie groß die Wahrscheinlichkeit ist, das auf eine bestimmte Adresse 5 Schlüssel abgebildet werden, lautet die Berechnung:

$\begin{displaymath}p(5)=\frac{\left(2500/3000\right)^5 *~ e^{-\left(2500/3000\right)}}{0!}\approx 0,1747\end{displaymath}$

Nächste Seite Aufwärts Vorherige Seite Inhalt

Nächste Seite: Über dieses Dokument ... Aufwärts: Hashing Vorherige Seite: Beseitigung von Kollisionen Inhalt

2002-05-09