Kvadratické sondování - Quadratic probing - Wikipedia
![]() | tento článek potřebuje další citace pro ověření.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:
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ý ][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 ith poloha sondy pro hodnotu k být dán funkcí
kde C2 ≠ 0. (Pokud C2 = 0, tedy h(k,i) degraduje na a lineární sonda. Za dané hash tabulka, hodnoty C1 a C2 zůstat konstantní.
Příklady:
- Li , pak bude sekvence sondy
- Pro m = 2n, dobrá volba pro konstanty jsou C1 = C2 = 1/2, jako hodnoty h(k,i) pro i v [0,m−1] jsou odlišné. To vede k sekvenci sondy o (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í C1 a C2 udělá h(k,i) odlišné pro i v [0, (m-1) / 2]. Mezi takové volby patří C1 = C2 = 1/2, C1 = C2 = 1 a C1 = 0, C2 = 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 ),[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 (prvočíslo větší než 3) s počátečním umístěním a dvě alternativní umístění a (kde a Pokud tato dvě místa ukazují na stejný klíčový prostor, ale , pak
- .
Tak jako je také prvočíslo nebo musí být dělitelné .Od té doby a jsou různé (modulo ), , a protože obě proměnné jsou větší než nula, . Protikladem tedy první alternativní umístění po musí být jedinečný a následně lze vždy najít prázdné místo, pokud nanejvýš 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 shodné s 3 modulo 4 (např. 3, 7, 11, 19, 23, 31 atd.), pak první posuny budou jedinečné (modulo ).[je třeba další vysvětlení ] Jinými slovy, permutace 0 až je získán a následně bude vždy nalezen bezplatný segment, pokud alespoň jeden existuje.
Reference
- ^ Hopgood, F. Robert A .; Davenport, James H. (Listopad 1972). „Kvadratická hashovací metoda, když velikost stolu je síla 2“. Počítačový deník. 15 (4): 314–5. doi:10.1093 / comjnl / 15.4.314. Citováno 2020-02-07.
- ^ Weiss, Mark Allen (2009). „§5.4.2 Kvadratické snímání“. Datové struktury a analýza algoritmů v C ++. Pearson Education. ISBN 978-81-317-1474-4.