WikiDer > Linearsonde
In dem Informatik ist Linearsonde eine Möglichkeit, Kollisionen ('Kollisionen') beim Einfügen eines Elements in . zu vermeiden Hash-Tabellen helfen. Beim Einfügen an der durch die Hash-Funktion berechnet ist nicht möglich (weil bereits ein Item vorhanden ist), wird diese Position um ein Standardinkrement (normalerweise 1) erhöht, bis eine Position gefunden wird (solange die Hash-Tabelle nicht voll ist).
Die berechnete Position wird modular m berechnet, wobei m die Größe der Hash-Tabelle ist. Dadurch bleibt der berechnete Wert im blijft Intervall [0, m) von ganzen Zahlen und damit innerhalb der Hash-Tabelle:
- (h(k) i) mod m, mit i = 0,1,2, ... (Schrittweite ist 1)
Lineares Antasten hat den Nachteil, dass eine leere Position neben einem langen durchgehenden Stück eine höhere Chance hat, besetzt zu werden als eine leere Position neben einem kürzeren Stück (oder neben einer leeren Position): lange durchgehende Stücke haben eine höhere Chance, ausgeglichen zu werden länger. Dadurch werden die Elemente in der Hash-Tabelle nicht wie gewünscht verteilt.
Beispiel
Wir nehmen eine Hashtabelle mit Platz für 11 Items, wobei einige Plätze bereits belegt sind (nämlich 0, 4, 5, 6, 7 und 10) und Schrittgröße 1 (in der Praxis ist dies die am häufigsten gewählte Schrittgröße). Das gibt:
- (h(k) i) mod 11, mit i = 0,1,2, ...
Wir möchten ein Element mit dem Hashwert 54 einfügen (also h(k) = 54). Das Einfügen erfolgt wie folgt:
- (54 0) mod 11 = 10, Kollision, da dieser Platz bereits belegt ist
- (54 1) mod 11 = 0, Kollision
- (54 2) mod 11 = 1, keine Kollision, daher kann hier ein Artikel eingefügt werden.