Sondowanie kwadratowe

Sondowanie kwadratowe to otwarty schemat adresowania w programowaniu komputerowym służący do rozwiązywania kolizji skrótów w tablicach mieszania . Sondowanie kwadratowe polega na pobraniu pierwotnego indeksu skrótu i ​​dodaniu kolejnych wartości dowolnego wielomianu kwadratowego , aż do znalezienia wolnego miejsca.

Przykładowa sekwencja wykorzystująca sondowanie kwadratowe to:

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

Sondowanie kwadratowe może być bardziej wydajnym algorytmem w otwartej tablicy adresowania , ponieważ lepiej pozwala uniknąć problemu grupowania, który może wystąpić w przypadku sondowania liniowego , chociaż nie jest odporne. Zapewnia również dobre buforowanie pamięci, ponieważ zachowuje pewną lokalizację odniesienia ; jednakże sondowanie liniowe ma większą lokalność, a tym samym lepszą wydajność pamięci podręcznej.

Funkcja kwadratowa

Niech h ( k ) będzie funkcją skrótu odwzorowującą element k na liczbę całkowitą w [0, m −1], gdzie m jest rozmiarem tabeli. Niech i ^-ta pozycja sondy dla wartości k będzie dana funkcją

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

gdzie c ₂ ≠ 0 (Jeśli c ₂ = 0, to h ( k , i ) ulega degradacji do sondy liniowej ). Dla danej tablicy mieszającej wartości c ₁ i c ₂ pozostają stałe.

Przykłady:

• Jeśli ${\ Displaystyle h (k, i) = (h (k) + i + i ^ {2}) {\ pmod {m}}}$ , wówczas sekwencja sondująca będzie następująca: ${\ Displaystyle h (k), h (k) + 2, h (k) + 6, ...}$
• Dla m = 2 ⁿ dobrym wyborem stałych są c ₁ = do ₂ = 1/2, ponieważ wartości h ( k , i ) dla i w [0, m −1] są różne. Prowadzi to do sekwencji próbnej ${\ Displaystyle h (k), h (k) + 1, h (k) + 3, h (k) + 6, ...} ($ liczby trójkątne ), gdzie wartości rosną o 1, 2, 3, . ..
• Dla liczby pierwszej m > 2 większość wyborów c1 i c2 sprawi, że _h ( k , i ) _będzie odrębne dla i w [0, ( m −1)/2]. Takie wybory obejmują c ₁ = c ₂ = 1/2, c ₁ = c ₂ = 1 i c ₁ = 0, c ₂ = 1. Jednak jest tylko m /2 różne sondy dla danego elementu, wymagające innych technik, aby zagwarantować, że wstawienie zakończy się sukcesem, gdy współczynnik obciążenia przekroczy 1/2.
• Dla , gdzie $p$ i p ${\ Displaystyle h (k, i) = (h (k) + i + ni ^ {2}) {\ pmod {m}}}$ równymi 2 (degraduje się do sondy liniowej, gdy = 1) , to = daje cykl wszystkich odrębnych sond. Można to obliczyć w pętli jako: ${\ displaystyle h (k, 0) = h (k)}$ i ${\ Displaystyle h (k, i + 1) = (h (k, i) + 2 cale + n + 1) {\ pmod {m}}}$
• Dla dowolnego m pełny cykl z sondowaniem kwadratowym można osiągnąć poprzez zaokrąglenie m do najbliższej potęgi 2, obliczyć indeks sondy: ${\ Displaystyle h (k, i) = h (k) + ((i ^ {2} + i)/2) {\ pmod {roundUp2 (m)}}} i pomiń iterację,$ gdy ${\ displaystyle h (k, i)> = m}$ . Jest maksimum $\ displaystyle roundUp2 (m) -m <m/2}$ pominięto iteracje, a iteracje te nie odnoszą się do pamięci, więc jest to szybkie działanie na większości nowoczesnych procesorów. Zaokrąglenie m można obliczyć w następujący sposób:

  
	
	    
	    
	    
	    
	    
	    
	 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  ++  ; 
	 
 powrót  v  ;  } 

Ograniczenia

Znaki naprzemienne

Jeśli znak przesunięcia jest naprzemienny (np. +1, -4, +9, -16 itd.) i jeśli liczba segmentów jest liczbą pierwszą przystającą do 3 modulo 4 (np. 3) ${\ displaystyle p}$$)$ 7, 11, 19, 23, 31 itd.), wówczas pierwsze $modulo$ będą unikalne ( . $wolne wiadro, o ile istnieje co najmniej jedno.$ uzyskuje się permutację od 0 do

Linki zewnętrzne

• Samouczek/sondowanie kwadratowe