Kvadratisk sondering

Quadratic probing är ett öppet adresseringsschema i datorprogrammering för att lösa hashkollisioner i hashtabeller . Kvadratisk sondering fungerar genom att ta det ursprungliga hashindexet och lägga till successiva värden av ett godtyckligt kvadratiskt polynom tills en öppen lucka hittas.

Ett exempel på en sekvens som använder kvadratisk sondering är:

$H+1^{2},H+2^{2},H+3^{2},H+4^{2},...,H+k^{2} }$

Kvadratisk sondering kan vara en mer effektiv algoritm i en öppen adresseringstabell , eftersom den bättre undviker klustringsproblemet som kan uppstå med linjär sondering , även om det inte är immunt. Det ger också bra minnescache eftersom det bevarar en viss referensplats ; linjär sondering har emellertid större lokalitet och därmed bättre cacheprestanda. ^{[ tveksamt – diskutera ]}^{[ citat behövs ]}

Kvadratisk funktion

Låt h ( k ) vara en hashfunktion som mappar ett element k till ett heltal i [0, m −1], där m är storleken på tabellen. Låt den i: ^te sondpositionen för ett värde k ges av funktionen

h(k,i)=h(k)+c_{1}i+c_{2}i ^{2}{\pmod {m}}

₂ där c2 ≠ 0 (Om c2 = ₂ = 0, then h(k,i) degrades to a linear probe). For a given hash table, the values of c₁ and c₂ remain constant.

Exempel:

Om $h(k,i)=(h(k)+i+i^{2}){\pmod {m}}$ , då blir sondsekvensen $h(k),h(k)+2,h(k)+6,...$
För m = 2 ⁿ är ett bra val för konstanterna c ₁ = c ₂ = 1/2, eftersom värdena på h ( k , i ) för i i [0, m −1] alla är distinkta. ${\displaystyle h(k),h(k)+1,h(k)+3,h(k)+6,...} (triangulära$ en sondsekvens talen ) där värdena ökar med 1, 2, 3, . ..
För primtal m > 2 kommer de flesta valen av c ₁ och c ₂ att göra h ( k , i ) distinkt för i i [0, ( m −1)/2]. Sådana val inkluderar c ₁ = c ₂ = 1/2, c ₁ = c ₂ = 1 och c ₁ = 0, c ₂ = 1. Det finns dock bara m /2 distinkta sonder för ett givet element, vilket kräver andra tekniker för att garantera att insättningar kommer att lyckas när belastningsfaktorn överstiger 1/2.
För $m=n^{p}$ , där m , n och p är heltal större eller lika med 2 (nedbryts till linjär sond när p = 1), då $h(k,i)=(h(k)+i+ni^{2}){\pmod {m}}$ ger cykel av alla distinkta sonder. Det kan beräknas i loop som: $h(k,0)=h(k)$ och $h(k,i+1)=(h(k,i)+2in+n+1){\pmod {m}}$
För varje m kan full cykel med kvadratisk sondering uppnås genom att avrunda m uppåt till närmaste potens av 2, beräkna sondindex: $h(k,i)=h(k)+((i^{2}+i)/2){\pmod {roundUp2(m)}}$ , och hoppa över iteration när $h(k,i)>=m$ . Det finns maximal $roundUp2(m)-m<m/2$ överhoppade iterationer, och dessa iterationer hänvisar inte till minnet, så det är snabbt drift på de flesta moderna processorer. Avrundning uppåt m kan beräknas genom:

  
	
	    
	    
	    
	    
	    
	    
	
	 
 uint64_t  roundUp2  (  uint64_t  v  ){  v  --  ;  v  |=  v  >>  1  ;  v  |=  v  >>  2  ;  v  |=  v  >>  4  ;  v  |=  v  >>  8  ;  v  |=  v  >>  16  ;  v  |=  v  >>  32  ;  v  ++  ;  returnera  v  ;  }

Begränsningar

Växlande tecken

Om tecknet för offset alterneras (t.ex. +1, −4, +9, −16, etc.), och om antalet hinkar är ett primtal $p$ kongruent med 3 modulo 4 (t.ex. 3 , 7, 11, 19, 23, 31, etc.), då kommer de första $p$ -offseten att vara unika (modulo $p$ ). ^{[ ytterligare förklaring behövs ]} Med andra ord, en permutation på 0 till $p-1$ erhålls, och följaktligen kommer en ledig hink alltid att hittas så länge som minst en existerar.

externa länkar

Handledning/kvadratisk sondering