== 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í =
{{TODO|Vůbec sem něco napsat}}
== Se separovanými řetězci ==
Neuspořádané, uspořádané
== S přemísťováním ==
== S dvěma ukazateli ==
== Srůstající hashování ==
Bez pomocné paměti, s pomocnou pamětí.
== S lineárním přidáváním ==
== Dvojité hashování ==
== 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.
