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

Aus Wikiversity


Kollisionsstrategien[Bearbeiten]

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[Bearbeiten]

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

Lineares Sondieren[Bearbeiten]

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

  • für eine Konstante c
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[Bearbeiten]

Die Idee beim quadratischen Sondieren ist, dass falls der Index h(e) besetzt ist versucht wird . Eine Variante hierfür ist

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