Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Hashtabellen Kollisionsstrategie

Kollisionsstrategien

Auf dieser Seite werden die Kollisionsstrategien bei Hashtabellen behandelt. Eine der Strategien ist die Verkettung von Überläufern bei Kollisionen. Die Idee dieser Strategie ist, dass alle Einträge einer Array Position in einer verketteten Liste verwaltet werden. Die andere Strategie ist das Sondieren, das heißt das Suchen einer alternativen Position. Hierbei gibt es mehrere Varianten: Das lineare Sondieren, das quadratische Sondieren, das doppelte Hashen, das Sondieren mit Zufallszahlen und viele mehr.

Verkettung der Überläufer

0	100
1
2	42	->	202	->	2
3	333
4
5	5
6	666	->	36
7
8
9	19

Lineares Sondieren

Die Idee beim linearen Sondieren ist, dass falls der Index h(e) besetzt ist versucht wird $h(e)+1,h(e)+2,h(e)+3,...,h(e)+i,...$. Varianten hierfür sind

• $h(e)+c,h(e)+2c,h(e)+3c,...$ für eine Konstante c
• $h(e)+1,h(e)-1,h(e)+2,h(e)-2,...$

	leer	insert 89	insert 18	insert 49	insert 58	insert 69
0				49	49	49
1					58	58
2						69
3
4
5
6
7
8			18	18	18	18
9		89	89	89	89	89

Quadratisches Sondieren

Die Idee beim quadratischen Sondieren ist, dass falls der Index h(e) besetzt ist versucht wird $h(e)+1,h(e)+4,h(e)+9,...,h(e)+i^{2},...$. Eine Variante hierfür ist

• $h(e)+1,h(e)-1,h(e)+4,h(e)-4...$

Diese Art des Sondierens ist allerdings anfällig gegenüber falsch gewähltem N, also der Feldgröße. Beispielsweise wählen wir N=16. Das Sondieren verläuft hier zyklisch ohne alle Elemente zu testen. Für N sollte eine Primzahl gewählt werden.

	leer	insert 89	insert 18	insert 49	insert 58	insert 69
0				49	49	49
1
2					58	58
3						69
4
5
6
7
8			18	18	18	18
9		89	89	89	89	89