Die offene Adressierung ist ein Verfahren zur Kollisionsauflösung beim Hashing. Wenn ein Eintrag an einer schon belegten Stelle in der Tabelle angelegt werden soll, wird stattdessen eine andere freie Stelle genommen.
Definitionen
Die Hashfunktion nimmt zwei Werte an:
- Die Position
wird verwendet, wenn sie frei ist. - Ansonsten ist der Reihe nach eine neue Position
zu bestimmen, bis eine freie gefunden wurde. - Der Tupel
heißt Prüfsequenz. - Insbesondere muss gelten:
.
Verfahren
Sei
Lineares Sondieren (linear probing)
Es wird um
Quadratisches Sondieren (quadratic probing)
Nach jedem erfolgslosen Suchschritt wird das Intervall quadriert.
Doppeltes Hashing (double hashing)
Eine weitere Hashfunktion
Anmerkungen
- Vorsicht beim Löschen von Schlüsseln:
- Durch Fortschaltung kann es zu nicht erkennbaren Lücken kommen
- Lösung: Statt Schlüssel zu löschen werden sie als gelöscht markiert
- Effiziente Implementierung:
- Statt die Kollisionsfolge immer wieder zu berechnen, wird ein Verweisvektor angelegt, der direkt auf die nächste Position verweist