|
Die einfachste Methode mit offener Adressierung wird lineares Austesten genannt. Im Falle einer Kollision wird einfach die nächste Position in der Hash-Tabelle untersucht. Ist diese leer, können die Daten dort gespeichert werden. Wenn auch diese Position belegt ist, wird wieder die nächste Position untersucht, solange bis eine leere Position erreicht wurde.
Beispiel:
Der Umfang der Tabelle für lineares Austesten ist größer als für getrennte Verkettung, doch die Gesamtgröße des verwendeten Speicherplatzes ist geringer, da keine Verkettungen benutzt werden.
Allgemein gilt: Für eine Hash-Tabelle, die zu weniger als zwei Dritteln gefüllt ist, erfordert lineares Austesten im Durchschnitt weniger als fünf Tests.
|
