= Externí hashování (?? zkouší se to ještě vůbec ??)=
== Statické hashovací metody ==
Jako [[Státnice - Hašování#Perfektní hashování|perfektní hashování]] se označuje nejen stav, kdy funkce nedává pro danou množinu žádné kolize, ale i takový systém, kde máme zaručený čas <math>O(1)</math> pro přístup k záznamu.
=== Cormackovo perfektní hashování ===
Hashování odpovídá "velké funkci a malé tabulce" ze [[Státnice - Hašování#Menší tabulka|sekce o hashování]]. Máme soubor a adresář. Krom primární hashovací funkce <math> h\,\!</math> jsou potřeba další hashovací funkce <math> h_i(k,r)=(k\mod(2i + 100r +1))\mod r\,\!</math>, kde:
* <math> r\,\!</math> je velikost oboru hodnot (počet kolizí)
* <math> i\,\!</math> je nějaký vhodný parametr - číslo hash fce (hledá se postupným zkoušením, dokud není výsledek bez kolizí).
V adresáři uchováváme pro každý záznam odkaz do primárního souboru, <math> r\,\!</math> a <math> i\,\!</math>. V primárním souboru máme klíč a data. Při hledání:
# Zahashujeme klíč pomocí <math> h\,\!</math>, dostaneme se do adresáře, pokud je tam <math> r=0\,\!</math>, nenašli jsme.
# Pokud <math> r\geq 1\,\!</math>, spočítám podle uloženého <math> i\,\!</math> hash-fci <math> h_i\,\!</math>, vezmu odkaz do primárního souboru, přičtu výsledek <math> h_i\,\!</math> a v primárním souboru zkontroluju, jestli jsem našel co jsem hledal.
Pro '''INSERT''' spočítám <math> h\,\!</math> a:
# Pokud na daném místě v adresáři nic není, najdu volné místo v primárním souboru délky 1 a vložím
# Pokud tam už něco je, najdu volné místo délky <math> r+1\,\!</math>, zvětším <math> r\,\!</math> a najdu <math> i\,\!</math>, aby kolizní od sebe rozházela a přeházím je na nové místo.
<math> r\,\!</math> nemusím zvětšovat o 1, ale rychleji, takže najdu požadované <math> i\,\!</math> lépe (pokud mám blbý <math> h_i\,\!</math>, někdy <math> r\,\!</math> prostě musím zvětšit o víc).
Toto hashování lze použít i pro dynamický paměťový prostor, když z primárního souboru uděláme nesouvislý prostor, kam lze přidávat stránky.
=== Perfektní hashování Larson-Kajla ===
Uchováváme menší pomocnou tabulku než předchozím případě -- pro každou stránku adresového prostoru máme jen jednu hodnotu -- ''separátor''. Máme:
* Množinu <math> M\,\!</math> hashovacích funkcí <math>h_i</math>, které vytvářejí pro každý záznam posloupnost <u>stránek</u>, do kterých ho můžeme zkoušet vkládat
* Navíc druhou sadu jim jednozn. odpovídajících funkcí <math>s_i</math>, které počítají ''signaturu''.
Pokud je separátor stránky větší než signatura záznamu, bude záznam v této stránce, jinak ho tam nemůžu vložit. Po přeplnění vyhodím záznamy s největší signaturou a zmenším separátor. Prvek se nemusí povést vložit (když mi dojdou obě sady funkcí).
Pokud vkládám do plné stránky, nemůžu prvek vložit, i když má prvek menší signaturu než separátor - separátor pak musím zmenšit a ze stránky vyhodit i něco dalšího, čímž dojde ke kaskádování.
Toto hashování je vhodné pro málo vkládání a hodně čtení -- mám zaručený jen jeden přístup na disk, protože malý adresář se do paměti vejde.
=== Dotazy na částečnou shodu ===
Máme-li záznamy s <math> n\,\!</math> atributy, použijeme pro každý z atributů zvláštní hashovací funkci, která generuje <math> d_i\,\!</math>-bitový výsledek (''signaturu atributu''). ''Signatura'' (hash) celého ''záznamu'' je pak konkatenací signatur atributů. Pro adresový prostor o velikosti <math> M=2^d\,\!</math> stránek volíme délky signatur atributů tak, aby <math> \sum d_i = d\,\!</math>.
Dotaz na částečnou shodu je potom dotaz, kde bity některých atributů jsou nahrazeny "?". Nazveme ''<math> s\,\!</math>-bitovou signaturu dotazu'', má-li zadaných <math> s\,\!</math> bitů. Takový dotaz je <math> 2^{d-s}</math>-krát dražší než přímý konkrétní.
Je-li pravděpodobnost dotazů na <math>i</math>-tý atribut rovna <math> P_i\,\!</math>, vyjde průměrná cena dotazů:
:<math>\sum_{q\subseteq\{1,..n\}}(P_q\cdot\Pi_{i\not\in q}2^{d_i})\,\!</math>
Ideální rozvržení <math> d_i\,\!</math> proto vychází (Lagrangovými multiplikátory):
:<math> d_i = (d - \sum_{j=1}^{n} \log_2 P_j)/n + \log_2 P_i\,\!</math>.
Je nutné upravit případné extrémy a přepočítat.
Pro urychlení dotazů můžeme použít ''deskriptory stránek'':
* Máme ''deskriptor záznamů'': <math> w = w_1 + .. + w_n\,\!</math>-bitový řetězec, kde pro každý atribut <math> A_1,.. A_n\,\!</math> máme právě jednu jedničku (může být zadáno jinak, ex. vzorce pro ideální <math> w_i\,\!</math> i počet jedniček k nim).
* Deskriptor stránek je bitový OR deskriptorů všech záznamů ve stránce.
* Při hledání vyrobím ''deskriptor dotazů'': místo "?" dám samé nuly. Pokud má dotaz někde v deskriptoru "<math> 1\,\!</math>" a stránka "<math> 0\,\!</math>", nemusím tam hledat.
Lze udělat i dvouúrovňově -- s ''deskriptory segmentů''.
Další možnost urychlení jsou ''Grayovy kódy'', které se snaží řešit nesouvislost oblasti stránek se záznamy vyhovujícími dotazům (např. <math> 10???1010\,\!</math>). Jde o jiný způsob kódování binárních čísel - dvě po sobě jdoucí čísla se liší vždy jen v jednom bitu. Max. zisk - o <math>50\%</math> lepší než binární. Konverze čísla do Grayova kódování z pozičního vypadá následovně:
:<math>G(x)=B(x)\ \mathrm{xor}\ B(\lfloor \frac{x}{2}\rfloor)\,\!</math>
Zpětně (<math>g_i</math> je i-tý bit Grayova kódu, <math>n</math>-tý bit je nejvyšší):
:<math>b_n = g_n</math>, <math>b_i = g_i\ \mathrm{xor}\ b_{i+1}</math>
== Dynamické hashování ==
=== Rozšiřitelné hashování -- Fagin (Koubkovo "externí hashování") ===
Kromě primárního souboru (nebo souborů, protože jde o dynamickou strukturu) mám pomocnou strukturu -- ''adresář'' s pointery na stránky o velikosti <math>2^d</math> (přičemž některé stránky mohou být v adresáři uvedeny víckrát) a používám hashovací funkci s rovnoměrným rozdělením.
Vždy použiju ''jen prvních <math> d\,\!</math> bitů hashe'', minimum kolik potřebuju. Podle nich určím záznam v adresáři a z něj najdu stránku. Pro stránku se může používat míň bitů, proto na ní může ukazovat víc záznamů v adresáři. Když se stránka naplní, rozštěpím ji na 2 podle dalšího bitu hash-funkce.
Pokud už stránka používá stejně bitů jako adresář, musím zvětšit o 1 bit i adresář (a zdvojnásobit jeho velikost), s ostatními stránkami nic nedělám. Při vypouštění záznamů lze stránky slévat, pokud si pamatuju jejich zaplněnost (můžu slévat jen stránky, které se liší jen v posledním bitu).
Adresář můžeme ukládat na jedné stránce externí paměti. Potom '''FETCH''' jsou max. 3 operace a '''INSERT''' nebo '''DELETE''' max. 6 operací s externí pamětí. Očekávaný počet použitých stránek je <math> \frac{n}{b\ln 2}\,\!</math>, kde <math>b</math> je počet prvků v jedné stránce, a velikost adresáře <math> \frac{e}{b\ln 2}n^{1+\frac{1}{b}}\,\!</math> -- to je víc než lineární růst, tj. nelze používat donekonečna (bez důkazů).
=== Lineární hashování -- Litwin ===
V tomto případě nemám adresář, jen oblast přetečení, přístupnou pointry z primárních stránek. Data vkládám do primárních stránek, po každých <math> L\,\!</math> '''INSERT'''ech se vynuceně štěpí určená stránka (v pořadí podle čísel stránek <math> 0, 1, 00, 01, 10, 11, 000\,\!</math>). Podle hashe (jeho konec musí odpovídá číslu stránky) se rozdělují při štěpení prvky.
'''FETCH''': když mám aktuálně <math> n\,\!</math> stránek, vezmu posledních <math> \lfloor\log_2 n\rfloor + 1\,\!</math> bitů hashe (pokud je to <math> >n\,\!</math>, zanedbám horní bit) a tím dostanu číslo stránky. Když v ní prvek není a stránka je přetečená, podívám se ještě do oblasti přetečení.
Při štěpení je nutné vrátit do rozštěpených stránek i záznamy z oblasti přetečení. Problémem jsou více zaplněné stránky na konci, tedy ještě nerozštěpené. Řešením je buď nerovnoměrné rozdělení hash-fce, nebo skupinové štěpení stránek.
==== Skupinové štěpení stránek ====
Rozšíření Litwina pro lepší využití stránek:
* Stránky jsou vždy organizovány vždy v <math> s\,\!</math> skupinách po <math> g\,\!</math> stránkách (začínáme s <math>s_0</math> skupinami, postupně se <math>s</math> zvětšuje, <math>g</math> zůstává).
* Mám inicializační hash-funkci <math>h\,\!</math> do <math>\{0\dots (g\cdot s_0)-1\}\,\!</math>.
* Štěpím také po <math> L\,\!</math> vložení, vždy <math> g\,\!</math> stránek do <math> g+1\,\!</math>, na to mám nezávislé hashovací funkce <math> h_0,...h_{\infty}\,\!</math> do <math>\{0\dots g\}\,\!</math>.
* Až dostanu <math> s\,\!</math> skupin po <math> g+1\,\!</math> stránkách, přeorganizuju stránky zpátky do skupin po <math> g\,\!</math> (můžu přidat nějaké prázdné, aby to vycházelo).
Při hledání se počítají všechna prehashování úplně od začátku - je to docela HW náročné, ale proti rychlosti disků se vyplatí.
==== Spirálová paměť ====
Tohle je další rozšíření Litwinova hashování, tentokrát pro exponenciální rozdělení klíčů. Místo rozdělení jedné stránky na starou a novou tu starou zahodí a přidá dvě nové.
Klíče jsou nejprve rovnoměrně rozděleny hash-funkcí <math> G(c,k)\to \langle c, c+1\rangle\,\!</math> (<math> c\in\mathbb{R}^+_0\,\!</math>) , pak přepočteny do <math>\langle b^c, b^{c+1}\rangle\,\!</math> a zaokrouhleny na konkrétní čísla stránek. Při změně <math> c\,\!</math> se mění velikost prostoru.
Při expanzi se nové <math> c\,\!</math> volí tak, aby zničilo stránku, která se štěpí (nejnižší číslo):
:<math> c_{n+1} := log_b( f + 1 )\,\!</math> (kde <math> f\,\!</math> je číslo 1. stránky).
Aby se mi neposouvaly všechny stránky pořád dál od 0, první zahozené stránce dám nové číslo a znova ji použiju -- přepočítávání log. stránek na fyzické se pak dělá rekurzivně:
# Je-li <math> \lfloor\,\!</math>logická stránka<math> / b\rfloor < \lfloor( 1+\,\!</math>logická stránka<math> )/b\rfloor\,\!</math>, pak fyzická stránka <math> :=\,\!</math> fyzická stránka(<math> \lfloor\,\!</math>logická stránka<math> / b\rfloor\,\!</math>)
# Jinak fyzická stránka <math> =\lfloor\,\!</math>log. stránka<math> / b\rfloor\,\!</math>. )
{{Statnice I2}}
