Universelles Hashing

Wir definieren eine Klasse H von geeigneten Hashfunktionen und wählen eine spezielle Hashfunktin zufällig aus H aus. Dabei soll für jedes $S\subset U$ ``fast jedes`` $h\in H$ die Schlüsselmenge S ``fast`` gleichverteilen über [0..m-1]. Formal:

Definition: H heißt c-universell ($c\in \mathbbm{R}$) g.d.w. $\forall k_1,k_2 \in U$ gilt:

$$\frac{\vert\{\ h\in H \vert\ \delta_h(k_1,k_2)=1 \}\vert}{\vert H\vert\ }\leq \frac{c}{m}$$

Beispiel einer 4-universellen Hashtabelle:
Seien $N\in \mathbbm{N}$ prim, $m\in \mathbbm{N}$, und $\forall a,b \in [0..N-1]:$

$$h_{a,b}(k)=\left((ak+b) \text{ \underline{mod} } N \right) \text{ \underline{mod} } m \ \forall k \in U \subset [0..N-1]$$

Dann ist $H=\{h_{a,b} \ \vert \ 0 \leq a,b \leq N-1 \}$ 4-universell.