{{TIN066 Skripta}}
== Slovníkový problém ==
Mějme universum prvků U a jeho podmnožinu S. Tu chceme reprezentovat a umět na ní provádět operace MEMBER, INSERT a DELETE. Nechci mít v paměti prostor pro celé U, proto si zavedu hashovací funkci <math>h\colon U \to \{0..m-1\}</math>, pak prvky ukládám do pole délky m na index podle <math>h(x)</math>.
* Problémem jsou '''kolize''': <math>x, y \in S: x \ne y,\ h(x) = h(y)</math>.
* Ještě nás bude zajímat '''load factor''' <math>\alpha = |S|/m</math>.
= Hashování se separovanými řetězci =
{{TODO|Důkazy složitostí (ale bez zamlžení toho, co už tu je; možná lemmata a detaily na zvláštní stránce?)}}
Každá položka hashe vede na spoják s kolidujícími prvky (řetězce jsou prosté, nic v nich není dvakrát). V nejhorším případě budu mít jediný spoják se vším.
Paměti žere každá položka <math>O(1+l(i))</math> (l(i) je délka spojáku), ''očekávané'' délky spojáků se řídí binomickým pravděpodobnostním rozdělením (s parametrem 1/m). Z toho vypadne, že:
* <math>\mathbb{E}\ l = \alpha</math>
* <math>\hbox{var}\ l = n{1 \over m}\left(1 - {1 \over m}\right)</math>
Zběsilými a děsivými sumacemi na tři stránky se dobereme k očekávané délce ''nejdelší'' položky <math>O({\log n \over \log \log n})</math> za předpokladu, že <math>\alpha \le 1</math>.
=== Neuspořádané řetězce ===
Dobře, jak dlouho bude trvat něco najít? Očekávaný počet testů při neúspěšném hledání bude:
<math>(1 - 1/m)^n + n/m</math> tzn. cca <math>e^{-\alpha} + \alpha</math>
(pravděpodobnost prázdného řetězce plus pro každou délku ta délka krát pravděpodobnost, že to bude ona).
Očekávaný počet testů při úspěšném vyhledání <math>1 + \alpha/2</math>. To je vidět celkem intuitivně, dokázat to formálně je trošku pracnější, ale už jsme tu přeskočili i horší věci. ;-)
=== Uspořádané řetězce ===
Očekávaný počet testů při úspěšném vyhledávání je stejný jako neuspořádaných řetězců. Při neúspěšném vyhledávání to můžeme utnout dříve, konkr. se lze dopracovat k počtu testů <math>e^{-\alpha} + 1 + \alpha/2 - (1 - e^{-\alpha})/\alpha</math>.
= "Inline" hashování =
(Toto není oficiální název, kdo ví, jestli je nějaký?)
Separované řetězce potřebují pamět navíc, když vím, že <math>\alpha</math> bude malé, nacpěme řetězce přímo do nevyužitých položek tabulky. Pak můžu dělat různé věci.)
== S přemísťováním ==
Tabulka bude mít pomocné prvky (další/předchozí prvek v řetězci), v případě, že do položky budu chtít uložit něco, co tam vážně patří, přendám prvek jinam. Očekávané hodnoty všeho budou stejné jako u separovaných řetězců, ale INSERT/DELETE budou samozřejmě náročnější.
== S dvěma ukazateli ==
Hashování s přemísťováním, ale odkaz na předchozí prvek nahradíme odkazem ''begin'' na začátek řetězce; řetězec tedy nemusí začínat na "své" položce. Odpadá nutnost přemísťování (jen se mění begin), zase je maličko větší očekávaný počet testů.
== Srůstající (coalesced) hashování ==
Máme jen jeden pomocný ukazatel ''next'', prvek pak prostě přidáme do řetězce, který zrovna prochází jeho položkou; v řetězci se tak časem mohou ocitnout prvky s různými hashi. Neumíme efektivně mazat.
{{TODO|Počty testů}}
=== Bez pomocné paměti (standardní) ===
LISCH (''late'') přidá prvek na konec řetězce, EISCH (''early'') přidá prvek do řetězce za prvek na kolidující položce (volnou položku pro přidávaný prvek seženu jedno jak). EISCH je trochu rychlejší (neformálně - pravděpodobnost práce s nově přidaným prvek je vyšší).
=== S pomocnou pamětí ===
Přidáme '''oblast přetečení''', což bude přímo neadresovatelný seznam, kam házíme kolidující nové prvky - až když je oblast plná, začneme je vkládat přímo na volná místa tabulky. (Tedy ukazatel next může procházet klidně skrz oblast přetečení.) EICH, LICH fungují stejně, VICH (''varied'') vloží nový prvek za poslední, který je ještě v pomocné části, nebo jako EICH (pokud řetězec přes pomocnou část nevede).
== S lineárním přidáváním ==
Bez pomocných položek pro práci s tabulkou, prostě nový prvek přidám na nejbližší následující volné místo (předpokládám cyklickou paměť). Hodně triviální implementace, ale složité a pomalé DELETE. Nevhodné pro netriviální <math>\alpha</math>, začnou se vytvářet shluky.
Očekávaný počet testů:
* Neúspěšný případ: <math>{1 \over 2}\left(1 + \left({1 \over 1 - \alpha}\right)^2\right)</math>
* Úspěšný případ: <math>{1 \over 2}\left(1 + {1 \over 1 - \alpha}\right)</math>
== Dvojité hashování ==
Jako lineární přidávání, další volnou pozici ale hledám chytřeji než lineárně - zavedu si druhou hashovací funkci, pak postupně pro rostoucí ''i'' testuji <math>(h_1(x) + ih_2(x)) \mod m</math>. Samozřejmě je vhodné, aby <math>h_2(x) \not| m</math>. DELETE je zase otrava. Když druhý hash zvolíme chytře, bude fungovat o dost lépe než lineární.
{{TODO|Odhady testů}}
= Externí hashování =
Chceme minimalizovat počet přístupů do stránkované externí paměti. V OZD se následující učilo pod jménem "Faginovo hashování".
Data rozhazujeme do stránek, každá stránka má atribut ''i'' - prvních ''i'' bitů hashe všech položek ve stránce je stejných. Dále si držíme adresář - mapování hashů na stránky, ve kterém indexujeme pomocí prvních ''j'' bitů hashe (<math>i \le j</math>); několik položek adresáře může ukazovat na tu samou stránku (pak <math>i < j</math>). Pokud se stránka naplní, zvýšíme ''i'' a stránku rozštěpíme, pokud tím porušíme invariant, zvýšíme i ''j''.
Adresář by se měl vejít do jedné stránky (nebo ho prostě držíme v paměti), potom MEMBER jsou max. 3 externí operace (nalezení 2 operace, třetí příp. update a zápis zpět na disk), INSERT/DELETE max. 6 operací (lookup 2 operace, pak buď uložení jako třetí, nebo např. pro INSERT rozštěpení: 3.,4. zápis dvou nových stránek, 5. znovunačtení adresáře (proč si jej nedržíme v paměti?), 6. uložení nového adresáře).
Nechť ''b'' je počet prvků na stránku a ''n'' počet všech prvků:
* Očekávaný počet použitých stránek bude <math>n \over b\ln 2</math>; tedy je zaplněno zhruba 69% možných položek v paměti.
* Očekávaná velikost adresáře bude <math>{e \over b\ln 2}n^{1+1/b}</math>; tedy superlineární! Mez použitelnosti (nárůst adresáře kolem 5%) pro <math>b=100</math> je zhruba <math>n=10^{10}</math>, pro větší n je potřeba i větší b.
