Hashing

Definition:
Unter Hashing versteht man die Abbildung von Schlüsselwerten auf Hashwerte (ganze Zahlen) mittels Hashfunktion. Gespeichert werden die Elemente in der Hashtabelle, Operationen sind Find, Insert und Delete.

Definition:
Eine Hashfunktion ist genau dann perfekt, wenn sie den Schlüsseln injektiv einen Hashwert zuordnet. Ist die Hashfunktion bijektiv, so heißt sie minimal perfekt.

Definition:
Sei $H$ endliche Kollektion von Hashfunktionen. $H$ heißt universell, wenn für je zwei verschiedene Schlüssel $x$ und $y$ gilt:

$\frac{\vert\{ h \in H: h(x)=h(y) \}\vert}{\vert H\vert} \leq \frac{1}{m}$

Also ist die Wahrscheinlichkeit für eine Kollision bei bel. $h \in H$ höchstens $1/m$.

Definition:
Der Maximale Füllgrad $\beta$ bei $n$ Elementen und $m$ Hashwerten ist $\beta = n / m$.