Kvadratické sondování - Quadratic probing - Wikipedia

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Kvadratické sondování"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Září 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Kvadratické sondování je otevřené adresování schéma v programování k vyřešení hashovací kolize v hash tabulky. Kvadratická sonda funguje tak, že vezme původní hash index a přidá po sobě jdoucí hodnoty libovolného kvadratický polynom dokud nenajdete otevřený slot.

Příklad sekvence používající kvadratické sondování je:

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

Kvadratická sonda může být efektivnějším algoritmem v otevřené adresování protože se lépe vyhne problémům s klastrováním, ke kterým může dojít lineární sondování, ačkoli to není imunní. Poskytuje také dobré ukládání do mezipaměti, protože některé zachovává referenční lokalita; lineární sondování má však větší lokalitu a tedy lepší výkon mezipaměti.^{[pochybný – diskutovat][Citace je zapotřebí ]}

Kvadratická funkce

Nechat h(k) být a hashovací funkce který mapuje prvek k na celé číslo v [0,m−1], kde m je velikost tabulky. Nech i^th poloha sondy pro hodnotu k být dán funkcí

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

kde C₂ ≠ 0. (Pokud C₂ = 0, tedy h(k,i) degraduje na a lineární sonda. Za dané hash tabulka, hodnoty C₁ a C₂ zůstat konstantní.

Příklady:

• Li ${ displaystyle h (k, i) = (h (k) + i + i ^ {2}) { pmod {m}}}$, pak bude sekvence sondy ${ displaystyle h (k), h (k) + 2, h (k) +6, ...}$
• Pro m = 2ⁿ, dobrá volba pro konstanty jsou C₁ = C₂ = 1/2, jako hodnoty h(k,i) pro i v [0,m−1] jsou odlišné. To vede k sekvenci sondy o ${ Displaystyle h (k), h (k) + 1, h (k) + 3, h (k) +6, ...}$ (dále jen trojúhelníková čísla ) kde se hodnoty zvyšují o 1, 2, 3, ...
• Pro nejlepší m > 2, většina možností C₁ a C₂ udělá h(k,i) odlišné pro i v [0, (m-1) / 2]. Mezi takové volby patří C₁ = C₂ = 1/2, C₁ = C₂ = 1 a C₁ = 0, C₂ = 1. Existují však pouze m/ 2 odlišné sondy pro daný prvek, vyžadující další techniky, aby bylo zaručeno, že vložení bude úspěšné, když je faktor zatížení vyšší než 1/2.

Omezení

Při použití kvadratického sondování však (s výjimkou trojúhelníkové číslo případy velikosti hash tabulky ${ displaystyle 2 ^ {n}}$),^[1] neexistuje žádná záruka, že bude prázdná buňka nalezena, jakmile bude tabulka zaplněna více než z poloviny, nebo ještě dříve, pokud je velikost tabulky kompozitní,^[2] protože kolize musí být vyřešena maximálně polovinou stolu.

Tuto inverzi lze prokázat takto: Předpokládejme, že hash tabulka má velikost ${ displaystyle p}$ (prvočíslo větší než 3) s počátečním umístěním ${ displaystyle h (k)}$ a dvě alternativní umístění ${ displaystyle h (k) + x ^ {2} { pmod {p}}}$ a ${ displaystyle h (k) + y ^ {2} { pmod {p}}}$ (kde ${ displaystyle 0 leq x}$ a ${ Displaystyle y leq p / 2}$Pokud tato dvě místa ukazují na stejný klíčový prostor, ale ${ displaystyle x neq y}$, pak

${ displaystyle h (k) + x ^ {2} = h (k) + y ^ {2} { pmod {p}}}$

${ displaystyle x ^ {2} = y ^ {2} { pmod {p}}}$

${ displaystyle x ^ {2} -y ^ {2} = 0 { pmod {p}}}$

${ displaystyle (x-y) (x + y) = 0 { pmod {p}}}$.

Tak jako ${ displaystyle p}$ je také prvočíslo ${ displaystyle (x-y)}$ nebo ${ displaystyle (x + y)}$ musí být dělitelné ${ displaystyle p}$.Od té doby ${ displaystyle x}$ a ${ displaystyle y}$ jsou různé (modulo ${ displaystyle p}$), ${ displaystyle (x-y) neq 0}$, a protože obě proměnné jsou větší než nula, ${ displaystyle (x + y) neq 0}$. Protikladem tedy první ${ displaystyle p / 2}$ alternativní umístění po ${ displaystyle h (k)}$ musí být jedinečný a následně lze vždy najít prázdné místo, pokud nanejvýš ${ displaystyle p / 2}$ místa jsou vyplněna (tj. hash tabulka není plná více než z poloviny).

Střídavé znaky

Pokud se střídá znaménko odsazení (např. +1, −4, +9, −16 atd.) A pokud je počet segmentů prvočíslo ${ displaystyle p}$ shodné s 3 modulo 4 (např. 3, 7, 11, 19, 23, 31 atd.), pak první ${ displaystyle p}$ posuny budou jedinečné (modulo ${ displaystyle p}$).^{[je třeba další vysvětlení ]} Jinými slovy, permutace 0 až ${ displaystyle p-1}$ je získán a následně bude vždy nalezen bezplatný segment, pokud alespoň jeden existuje.

Reference

externí odkazy

• Výukový / kvadratický průzkum