Wikiversity

Kurs:Algorithmen und Datenstrukturen/Vorlesung/Hashtabellen Kollisionsstrategie

< Kurs:Algorithmen und Datenstrukturen | Vorlesung


Startseite
Vorlesung


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


     

Abgerufen von „https://de.wikiversity.org/w/index.php?title=Kurs:Algorithmen_und_Datenstrukturen/Vorlesung/Hashtabellen_Kollisionsstrategie&oldid=586207“