== 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>.
== S přemísťováním ==
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. Ta 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í hashování ==
{{TODO|Vůbec sem něco napsat}}
Bez pomocné paměti, s pomocnou pamětí.
== 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í ==
V OZD se 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.
