WikiDer > Quadratische Sondierung

In dem Informatik ist quadratisches Antasten eine Möglichkeit, Kollisionen ('Kollisionen') beim Einfügen eines Elements in . zu vermeiden Hash-Tabellen helfen. Beim Einfügen an der durch das Hash-Funktion berechnet ist nicht möglich (da bereits ein Artikel vorhanden ist), diese Position ist mit a . gekennzeichnet quadratischFunktion erhöht, bis eine Position gefunden wird oder bis mehrmals keine Position gefunden wurde (diese Methode garantiert nicht, dass auch eine möglicherweise noch leere Position gefunden wird).

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:

${displaystyle h(k,i)=(h(k) c_{1}i c_{2}i^{2})}$ mod m, mit i = 0,1,2, ... und ${displaystyle c_{2}eq 0}$

Beispiel

Visuelle Darstellung der Arbeitsweise des quadratischen Antastens im Beispiel

Wir nehmen eine 11-Item-Hashtable mit einigen bereits belegten Plätzen (nämlich 0, 4, 5, 6, 7 und 10), ${displaystyle c_{1}=0}$ und ${displaystyle c_{2}=1}$ (in der Praxis ist dies auch die am häufigsten gewählte Einstellung). Das gibt:

${Anzeigestil h(k,i)=(h(k) i^{2})}$ mod 11, mit i = 0,1,2, ...

Wir möchten ein Element mit dem Hashwert 48 einfügen (also h(k) = 48). Das Einfügen erfolgt wie folgt:

(48 ${Anzeigestil 0^{2}}$) mod 11 = 4, Kollision, da dieser Platz bereits belegt ist

(48 ${Displaystil 1^{2}}$) mod 11 = 5, Kollision

(48 ${Displaystil 2^{2}}$) mod 11 = 8, keine Kollision, daher kann das Element hier eingefügt werden.

Siehe auch

• Linearsonde
• doppeltes hashing