Sondieren

Definition:
Beim offenen Hashing ist die Hashtabelle ein fester Speicherbereich der Größe $m$ und somit $n \leq m$, also $\beta \leq 1$. Tritt eine Kollision auf, so wird für das Element über Sondierung eine neue Position bestimmt.

Operationen:
Beim Suchen eines Elements wird entlang der Sondierungsfunktion so lange verglichen, bis entweder das Element gefunden wird oder eine Leerstelle auftritt.
Gelöschte Elemente müssen in der Hashtabelle erhalten bleiben, da die Sondierung sonst Elemente mit gleicher Hashfunktion nicht mehr finden kann. Sie werden als ''überschreibbar'' markiert.

Definition:
Das Lineare Sondieren erhöht bei einer Kollision die Hashfunktion um eins:
$h(x)=h(x)+1 \>mod\> m$

Definition:
Das Quadratische Sondieren testet bei einer Kollision alternierend Adressen mit quadratischer Entfernung: $h(x), h(x)+1, h(x)-1, h(x)+4, h(x)-4, ...$

Analyse:

$\alpha$	lin. erfolgreich	lin. erfolglos	quadr. erfolgreich	quadr. erfolglos
0.5	1.5	2.5	1.39	2
0.9	5.5	50.5	2.56	10
0.95	10.5	200.5	3.15	20