Chainingverfahren

Die Hashtabelle ist eine array von m linearen Listen, wobei die i-te Liste alle k Schlüssel beinhaltet, für die gilt:

h(k)=i

Zugriff: Berechne h(k) und durchsuche die Liste T[h(k)].

$$\delta_h(k_1,k_2) = \left\{ \begin{array} {l} 1 \text{ f... ...) \wedge k_1 \neq k_2\\ 0 \text{ sonst} \end{array} \right.$$

$$\delta_h(k_1,S) := \sum_{k_2\in S} \delta_h(k_1,k_2), \text{ Anzahl Kollisionen von $k_1$\space mit $S$\space }$$

Zugriffskosten :

worst-case: h|_s= const $\Rightarrow$ Entartung des Hashings zu linearer Suche $\mathcal{O}(\vert S\vert)$

average-case :

-

Möge h das Universum U über [0..m-1] gleichverteilen

-

Seien alle Werte in U gleichwahrscheinlich als Argument von Access() ,

Insert() , Delete()

-

Sei $\beta = \frac{n}{m}$ der maximale Füllgrad von T, n= Anzahl Operationen

Dann: Die erwartete Laufzeit für n-Operationen =

Beweis: Durch die Gleichverteilung für den Wert h(k_i) bei der i-ten Operation

$$P(h(k)=j) = \frac{1}{m} \ \ ( 0 \leq j \leq m-1)$$

$\Rightarrow$ $\mathbbm{E}$ (Listenlänge) $\leq \frac{r}{m}$ nach der r-ten Operation
$\Rightarrow$ $\mathbbm{E}$ (Kosten von (n+1)-ten Operationen) $=\mathcal{O}(1+\frac{i}{m})$
$\Rightarrow$ $\mathbbm{E}$ (Kosten von n Operationen) $=\mathcal{O}((1+\frac{1}{2}\frac{n}{m})n)$ $\Diamond$