{{TOC float}}
{{TODO|vyházet zbytečnosti, zpřehlednit}}
==Hashování==
Základní motivací pro hashování je ''slovníkový problém'', kdy máme za úkol reprezentovat množinu <math>S\,\;</math> prvků z nějakého univerza <math> U\,\!</math> a provádět na ní následující operace:
* '''MEMBER''' (je třeba, aby tato operace probíhala velmi rychle)
* '''INSERT'''
* '''DELETE'''
Aby byl '''MEMBER''' rychlý, bylo by nejlepší mít v paměti pole bitů o velikosti <math> U\,\!</math>. V případě, že <math> |S|<<|U|\,\!</math> (a navíc <math>U\,\;</math> může být neúnosně velké), použiji ''hashovací funkci'' <math> h:U\to\{0,\dots,m-1\}\,\!</math> a množinu <math> S\,\!</math> reprezentuji polem s <math> m\,\!</math> políčky tak, že <math> x\in S\,\!</math> je uložen na indexu <math> h(x)\,\!</math>. Předpokládejme, že funkce <math> h\,\!</math> se dá spočítat v čase <math> O(1)\,\!</math> -- jiné funkce vlastně nemají smysl, protože nepřináší dostatečné zrychlení.
Problém je, když nastane ''kolize'': <math> x\neq y\,\!</math>, <math> h(x)=h(y)\,\!</math>. Jednotlivé druhy hashování, které následují, se liší strategiemi předcházení a řešení kolizí.
Pro následující analýzy si označíme:
* <math> |S|=n\,\!</math>
* <math> |U|=N\,\!</math>
* ''Load factor'' (faktor zaplnění) -- <math> \alpha=\frac{n}{m}\,\!</math>.
===Hashování se separovanými řetězci===
V tomto typu hashování se kolize řeší ''řetězením ve spojácích'': pro každé políčko založíme zvlášť spoják všech prvků, které se do něj hashují. Všechny algoritmy je musí projít. Předpokládejme, že řetězce jsou prosté -- nic se v nich neopakuje. V nejhorším případě mají všechny prvky stejný hash a máme jen jeden seznam.
Paměťová náročnost je pro každý seznam <math> O(1+l(i))\,\!</math>, kde <math> l(i)\,\!</math> je délka toho seznamu.
Existují dvě varianty -- neuspořádaná a s s uspořádanými prvky v řetězcích. Liší se jedině v [[#Očekávaný počet testů|očekávaném počtu testů]] pro neúspěšné hledání (když dojdu v řetězci za místo, kde by byl hledaný prvek, můžu skončit).
Pro odhad složitosti alogritmů předpokládáme, že:
* Hashovací funkce <math> h\,\!</math> rozděluje data rovnoměrně
* Sama reprezentovaná množina <math> S\,\!</math> je náhodný výběr z <math> U\,\!</math> s rovnoměrným rozdělením
Tyto předpoklady v praxi ale splněny být nemusí.
====Očekávaná průměrná délka řetězců====
Pro odhad složitosti se počítá '''očekávaná délka řetězců'''. Označme délku <math> i\,\!</math>-tého řetězce jako <math> \mathbf{l}(i)\,\!</math>. Potom pravděpodobnost, že tento řetězec má délku <math> l\,\!</math>, bude:
:<math>P(\mathbf{l}(i) = l) = p_{n,l} = \mathbf{}\binom{n}{l}(\frac{1}{m})^{l}(1-\frac{1}{m})^{n-l}\,\!</math>
Toto je jen aproximace, pro případ, že <math> N>>n^2 m\,\!</math>, ale lze použít. Očekávaná délka řetězce pak vychází jako (rozepíšu faktoriál a vytknu <math> \frac{n}{m}\,\!</math>, pak změním rozsah sumace <math> 1\dots n\,\!</math>, pak <math> 0\dots n-1\,\!</math>):
:<math>E(l)=\sum_{l=0}^{n}lp_{n,l}=\frac{n}{m}\sum_{l=0}^{n-1}\mathbf{}\binom{n-1}{l}(\frac{1}{m})^l(1-\frac{1}{m})^{n-1-l}=\frac{n}{m}(\frac{1}{m}+1-\frac{1}{m})^{n-1}=\frac{n}{m}=\alpha\,\!</math>
====Očekávaná délka nejdelšího řetězce====
Tento údaj však sám o sobě nestačí, počítá se i očekávaný nejhorší případ (očekávaná '''délka nejdelšího řetězce'''). Ta se definuje následovně:
:<math>EMS = \sum_{j}j P(\max_{j} \mathbf{l}(i) = j) = \sum_{j} P(\max_{i}\mathbf{l}(i) \geq j )\,\!</math>
Z toho (pravděpodobnost disjunkce jevů je <math>\leq\,\;</math> součet jednotlivých pravděpodobností; vyčíslení: počet podmnožin správné velikosti a pravděpodobnost, že mají stejný hash):
:<math>P(\max_{i}\mathbf{l}(j)\geq j ) \leq \sum_{i}P(\mathbf{l}(i)\geq j) \leq m \mathbf{}\binom{n}{j}(\frac{1}{m})^j = \frac{\prod_{k=0}^{j-1}(n-k)}{j!}(\frac{1}{m})^{j-1} \leq n (\frac{n}{m})^{j-1}\frac{1}{j!}\,\!</math>
Najdeme mezní hodnotu <math> j_0\,\!</math>, pro které <math> n(\frac{n}{m})^{j-1}\frac{1}{j!}\leq 1\,\!</math>. Označme <math> k_0 = \min\{j|n\leq j!\} \,\!</math>. Potom <math> j_0 \leq k_0\,\!</math>. Ze Stirlingovy formule plyne, že <math>\log x! = \Theta(x\log x)\,\!</math>. Z toho odvodíme (hodně neformálně):
:<math>\log k_0! = k_0 \log k_0 = O(\log n)\,\;</math>
:<math>\log k_0 + \log\log k_0 \approx \log k_0 = O(\log\log n)\,\;</math>
:<math>k = \frac{k_0 \log k_0}{\log k_0} = O(\frac{\log n}{\log\log n})\,\;</math>
Pro <math> \alpha\leq 1\,\!</math> platí, že <math> EMS = O(j_0)\,\;</math>:
:<math>EMS=\sum_{j}P(\max_{i}\mathbf{l}(i)\geq j)\leq \sum_{j}\min\{1,n(\frac{n}{m})^{j-1}\frac{1}{j!}\} = \sum_{j=1}^{j_0}1 + \sum_{j=j_0+1}^{\infty}(n(\frac{n}{m})^{j-1}\frac{1}{j!}) \leq j_0 + \sum_{j=j_0+1}^{\infty}\frac{n}{j!} = \dots \leq j_0 + \frac{1}{j_0}\,\!</math>
A tedy očekávaná délka nejdelšího řetězce je <math>O(\frac{\log n}{\log\log n})\,\;</math>.
====Očekávaný počet testů====
'''Testy''' jsou porovnání toho, co hledáme, s nějakým prvkem, nebo zjištění, že řetězec je prázdný. Jejich očekávaný počet je další odhad efektivity struktury. Rozlišujeme úspěšné a neúspěšné hledání.
Neúspěšné hledání (Je-li délka řetězce <math> 0\,\!</math>, jeden test stejně provedu, jinak otestuji celý řetězec):
:<math>E(T) = p_{n,0} + \sum_l p_{n,l} = (1-\frac{1}{m})^n + \frac{n}{m} \approx e^{-\alpha} + \alpha\,\!</math>
S uspořádanými řetězci končím dřív (<math> e^{-\alpha}+1+\frac{\alpha}{2}-\frac{1}{\alpha}(1-e^{-\alpha})\,\!</math>).
Počet testů pro úspěšné vyhledávání je roven počtu testů provedených při vložení prvku: <math> \frac{1}{n}\sum_{i=0}^{n-1}\left(1+\frac{i}{m}\right)\,\! = 1 + \frac{n-1}{2m} \approx 1 + \frac{\alpha}{2}</math>.
===Hashování s přemísťováním===
Nevýhoda sep. řetězců -- nutnost alokovat další paměť, to je neefektivní. Proto zavedu do tabulky další pomocné položky a řetězce nacpu přímo do ní. V případě přemísťování mám v tabulce navíc jednoduše odkaz na předch. a násl. prvky v řetězci. Pokud vkládám a už tam je něco z jiného řetězce, tak to něco přehodím jinam. Algoritmy jsou jednoduché, jen při DELETE prvního prvku řetězce je nutné dát druhý (je-li) na jeho místo.
Očekáváný počet testů je stejný jako pro hashování se separovanými řetězci. Nevýhoda: přemísťování v tabulce je náročnější než 1 test -- INSERT a DELETE jsou pomalejší.
===Hashování se 2 ukazateli===
Místo ukazatele na předch. prvek používá odkaz na začátek řetězce "begin" -- řetězec už nemusí začínat na indexu svého hashe. Algoritmy místo přesouvání mění "begin" (ten je na <math> j\,\!</math>-tém políčku vyplněn, právě když existuje řetězec prvků s hashem <math> j\,\!</math>; INSERT všechno cpe na konec řetězce, zakládá-li nový, do "begin" píše, kde; DELETE jen upravuje odkazy na násl., nebo "begin").
Počet testů -- o něco větší, kvůli začátku řetězce jinde; úspěšné: <math> 1+\frac{(n-1)(n-2)}{6m^2} + \frac{n-1}{2m}\approx 1 + \frac{\alpha^2}{6} + \frac{\alpha}{2}\,\!</math>, neúspěšné přibližně <math> 1+\frac{\alpha^2}{2}+\alpha+e^{-\alpha}(2+\alpha)-2\,\!</math>.
===Srůstající (coalesced) hashování===
Má jen 1 položku v tabulce navíc (ukazatel na další prvek "next"), řetězce obsahují hodnoty s různými hashi. Prvek <math> s\,\!</math> vkládáme vždy do řetězce, obsahujícího <math> h(s)\,\!</math>-té políčko v tabulce. Různé metody: standardní (bez pomocné paměti) LISCH, EISCH a bezpřívlastkové (s pomocnou pamětí) LICH, VICH, EICH.
====Bez pomocné paměti -- LISCH a EISCH====
LISCH je "late insertion", tedy přidává se za poslední prvek řetězce. EISCH ("early") přidává za první prvek. Alg. MEMBER stejný pro oba (jen projití řetězce po "next"). Alg. INSERT: u LISCH projití celého řetězce (v případě že není prázdný, jinak jednoduše vložím na správné políčko) s testy na přítomnost prvku, potom vložení na lib. volné místo v tabulce \& připojení na konec řetězce. Pro EISCH -- přepojení ukazatelů "next" a vložení do řetězce za 1. prvek (pokud řetězec je neprázdný).
Algoritmy DELETE nejsou známy, kromě primitivních. Problém -- zachování náhodného usp. prvků v řetězcích, pokud nedodržím, zhorší to očekávané doby. Možné také prvky jen označit jako odstraněné a jejich místa použít při vkládání dalších (ale zpomaluje hledání). EISCH je o něco rychlejší na úspěšné vyhledání (větší pravděpodobnost práce s novým prvkem), očekávaný počet testů stejný.
'''Počet testů v neúspěšném případě''' -- mějme prvky <math> s_1,\dots,s_n\,\!</math> uložené (stejně pravděpodobně) na (libovolných) adresách <math> a_1,\dots,a_n\,\!</math> a hledáme <math> s_{n+1}\,\!</math>. Počet testů při takovém hledání budiž <math> C(a_1,a_2,\dots,a_n;a_{n+1})\,\!</math>, potom očekávaný počet testů je (pro <math> c_{n,l}\,\!</math> počet řetězců délky <math> l\,\!</math>, které přispívají celkem <math> 1+2+\dots+l = l + \mathbf{}\binom{l}{2}\,\!</math> porovnáními):
:<math>\frac{\sum_{\mbox{vsechny posl. }a_i}C(a_1,\dots,a_n;a_{n+1})}{m^{n+1}}=\frac{c_{n,0}+\sum_{l=1}^{n}lc_{n,l}+\sum_{l=1}^{n}\mathbf{}\binom{l}{2}c_{n,l}}{m^{n+1}}\,\!</math>
a <math> c_{n,0}\,\!</math> je počet prázdných řádků, tedy <math> c_{n,0}=(m-n)m^n\,\!</math>, <math> lc_{n,l}\,\!</math> je součet délek všech řetězců v reprezentacích <math> n\,\!</math>-prvk. množin, tedy <math> \sum_{l=1}^n lc_{n,l}= nm^n\,\!</math>. Poslední člen <math> := S_n\,\!</math>, 2 možnosti vzniku řetězce délky <math> l\,\!</math> přidáním dalšího prvku do <math> n-1\,\!</math>-prvkové množiny -- buď přidávám do řetězce (délky <math> l-1\,\!</math>), nebo řetězec (pův. délky <math> l\,\!</math>) nezměním:
:<math>S_n = \sum_{l}\mathbf{}\binom{l}{2}(m-l)c_{n-1,l} + \sum_l\mathbf{}\binom{l}{2}(l-1)c_{n-1,l-1} = mS_{n-1} - \sum_l l^2c_{n-1,l}=(m+2)S_{n-1}+(n-1)m^{n-1}\,\!</math>
(úpravy: rozepsání rozdílů, vykrácení, rozpis <math> l^2\,\!</math> jako <math> l^2-l + l=\mathbf{}\binom{l}{2}+l\,\!</math>), pak získám nerekurentní vztah:
:<math>S_n = (m+2)^{n-1} S_0 + \sum_{i=0}^{n-1}(m+2)^i(n-1-i)m^{n-1-i} = (m+2)^{n-1}\sum_{i=1}^{n-1}i\left(\frac{m}{m+2}\right)^i = \frac{1}{4}(m(m+2)^n - m^{n+1} - 2nm^n\,\!</math>
(úpravy: <math> S_0 = 0\,\!</math>, obrácení sumace a vytknutí <math> m+2^{n-1}\,\!</math>, použití vztahu <math> T_n^c=\sum_{i=1}^n ic^i=\frac{nc^{n+2}-(n+1)c^{n+1}+c}{(c-1)^2}\,\!</math> spočítaného z <math> (c-1)T_n^c=nc^{n+1}+(\sum_{i=2}^n-c^i)-c\,\!</math>). Tedy očekávaný počet testů je:
:<math>1+\frac{1}{4}\left(\left(1+\frac{2}{m}\right)^n - 1 - \frac{2n}{m}\right)\approx 1 + \frac{1}{4}(e^{2\alpha}-1-2\alpha)\,\!</math>
'''Úspěšný případ''' -- pro LISCH podobně jako u separovaných řetězců, tj. počet testů při vkládání prvku. Metoda EISCH nesplňuje předpoklady. Porovnání klíčů při neúspěšném vyhledávání je (bez hrabání na prázdná políčka) <math> \frac{n}{m}+ \frac{1}{4}\left(\left(1+\frac{2}{m}\right)^n - 1 - \frac{2n}{m}\right) = \frac{1}{4}\left(\left(1+\frac{2}{m}\right)^n - 1 + \frac{2n}{m}\right)\,\!</math>. Očekávaný počet testů při úspěšném je <math> 1+\sum_{i=0}^{n-1}(''por. při neúsp.'')\,\!</math> a to je
:<math>1+\sum_{i=0}^{n-1}\frac{1}{4}\left(\left(1+\frac{2}{m}\right)^i-1+\frac{2i}{m}\right)=1+\frac{m}{8n}\left(\left(1+\frac{2}{m}\right)^n-1-\frac{2n}{m}\right)+\frac{n-1}{4m}\approx 1+\frac{1}{8\alpha}(e^{2\alpha}-1-2\alpha)+\frac{\alpha}{4}\,\!</math>
Pro metodu EISCH potom vychází (bez důkazu)
:<math>\frac{m}{n}\left(\left(1+\frac{1}{m}\right)n-1\right)\approx\frac{1}{\alpha}(e^{\alpha}-1)\,\!</math>
Všechny odhady mají odchylku <math> O(\frac{1}{m})\,\!</math>.
====S pomocnou pamětí -- LICH, VICH, EICH====
Paměť je dělená na (hash-funkcí) přímo adresovatelnou a pomocnou část (bez přístupu hash-funkcí). Při kolizích nejdříve bereme řádky z pomocné části, pak teprve z přímo adresovatelné, tj. oddalujeme srůstání řetězců -- chování se podobá separovaným do určitého okamžiku. Varianty -- "early", "late", "varied". Také nemá přirozené efektivní DELETE.
LICH vždy přidává na konec řetězce, EICH v případě neprázdného řetězce vždy za 1. prvek a VICH vždy za poslední prvek v pomocné paměti nebo (pokud žádné v pomocné paměti nejsou) za 1. prvek řetězce (tj. chová se na pomocné paměti jako LICH a v přímo adresovatelné části jako EICH). Algoritmy až na VICH jsou stejné jako pro standardní, rozhodující je výběr volného řádku pro vložení: např. "z nejvyšší adresy" může zaručit používání pomocné paměti.
'''Složitost''' -- použití <math> n\,\!</math> -- počtu uložených prvků, <math> m\,\!</math> -- velikosti přímé paměti, <math> m'\,\!</math> -- celk. velikosti paměti a <math> \alpha=\frac{n}{m'}\,\!</math> -- faktor zaplnění, <math> \beta=\frac{m}{m'}\,\!</math> -- adresovací faktor. <math> \lambda\,\!</math> budiž jediné nezáp. řešení rovnice <math> e^{-\lambda}+\lambda=\frac{1}{\beta}\,\!</math>. Pokud je <math> \alpha\leq\lambda\beta\,\!</math>, pak pro všechny verze vychází očekávaný počet testů <math> e^{-\frac{\alpha}{\beta}}+\frac{\alpha}{\beta}\,\!</math> v neúspěšném případě a <math> 1+\frac{\alpha}{2\beta}\,\!</math> v úspěšném (chyba: <math> O(\log\frac{m'}{\sqrt{m'}})\,\!</math>. V případě, že <math> \alpha\geq\lambda\beta\,\!</math> (začínají srůstat řetězce), se metody liší a vychází divnosti. V neúspěšném případě je VICH a LICH lepší než EICH, v úspěšném vede VICH před EICH a LICH (vždy o jednotky procent). Doporučená <math> \beta=0.86\,\!</math>. Pro hledání volného řádku se hodí např. spojový seznam volných řádků.
===Lineární přidávání===
Nemá žádné položky pro práci s tabulkou, nalezení dalšího prvku je přímo v algoritmu. Nejjednodušší -- lineární přidávání: v případě kolize naleznu nejbližší vyšší volné políčko a vložím tam. Předpokládám "cyklickou" paměť. Problém: shluky -- při velkém zaplnění se dost zpomaluje, nepodporuje efektivní DELETE (a primitivní způsoby taky rychlé nejsou). Pro test přeplnění -- dobré uchovávát počet uložených prvků nebo mít zarážku (nikdy neobsazované pole).
Počet testů -- <math> \frac{1}{2}\left(1+\left(\frac{1}{1-\alpha}\right)^2\right)\,\!</math> v neúspěšném a <math> \frac{1}{2}\left(1+\left(\frac{1}{1-\alpha}\right)\right)\,\!</math> v úspěšném případě (bez důkazu).
===Dvojité hashování===
Vylepšení předchozího, aby nevznikaly shluky tak rychle: výběr následujícího řádku bude závislý na předchozím, rovnoměrně rozmístěný. Použiji 2. hash-fci <math> h_2\,\!</math>, vždy hledám takové <math> i\,\!</math> od <math> 0\,\!</math>, že <math> (h_1(x) + i\cdot h_2(x)) \mod m\,\!</math> je volné políčko, tj. při operaci INSERT i hledání postupně přičítám <math> h_2(x)\,\!</math> a modulím. Nutné je, aby <math> h_2(x) \not | m\,\!</math>, abych měl prosté posloupnosti. Idea, že jde pro každé <math> x\,\!</math> o náh. permutaci, není úplně přesná, ale v praxi stačí, aby z <math> h_1(x) = h_1(y)\,\!</math> plynulo, že <math> h_2(x)\,\!</math> a <math> h_2(y)\,\!</math> budou odlišné. Nevýhoda -- zas nemá efektivní DELETE. Přeplnění se řeší pořád stejně.
Nutné funkce volit správně (i lineární přidávání je spec. příp. dvojitého hashování, kdy <math> h_2 \equiv 1\,\!</math>), pak vychází znatelně rychlejší než lin. přidávání; sice nelze splnit předpoklad náhodnosti, použitý v teoretické analýze, ale přiblížit se mu ano.
'''Počet testů''' -- (teoreticky, na zákl. předpokladu náhodnosti) '''v neúspěšném případě''': označme <math> q_i(n,m)\,\!</math> pravděpodobnost, že při zaplnění <math> \frac{n}{m}\,\!</math> je pro nějaké <math> x\,\!</math> prvních <math> i-1\,\!</math> políček, kam bych ho mohl vložit, plných. Potom <math> q_i(n,m) = \frac{\prod_{j=0}^{i-1}(n-j)}{\prod_{j=0}^{i-1}(m-j)}\,\!</math> a tedy <math> q_i(n,m)=\frac{n}{m}q_{i-1}(n-1,m-1)\,\!</math>. Potom očekávaný počet testů (v urč. případě prvních <math> j-1\,\!</math> obsazených, <math> j\,\!</math> volné) je
:<math>C(n,m)=\sum_{j=0}^n(j+1)(q_j(n,m)-q_{j+1}(n,m))=\sum_{j=0}^n(q_j(n,m))=1+\frac{n}{m}C(n-1,m-1)=\frac{m+1}{m-n+1}\,\!</math>
(předposlední z rekurentního vztahu pro <math> q_j\,\!</math>, poslední krok dokázat indukcí).
'''Testy v úspěšném případě''' -- stejná metoda jako u dřívějších analýz, takže vychází
:<math>\frac{1}{n}\sum_{i=0}^{n-1}C(i,m)=\frac{1}{n}\sum_{i=0}{n-1}\frac{m+1}{m-i+1}\approx\frac{1}{\alpha}\ln\left(\frac{m+1}{m-n+1}\right)\approx\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\,\!</math>
===Srovnání===
Podle počtu testů:
{| border="1" cellspacing="0"
! !! neúspěšné !! úspěšné
|-
|1. || separované uspořádané řetězce || separované (usp. i neusp.) řetězce, přemísťování
|-
|2. || separované řetězce, přemísťování || dva ukazatele
|-
|3. || dva ukazatele || VICH
|-
|4. || VICH, LICH || LICH
|-
|5. || EICH || EICH
|-
|6. || LISCH, EISCH || EISCH
|-
|7. || dvojité hashování || LISCH
|-
|8. || lineární přidávání || dvojité hashování
|-
|9. || || lineární přidávání
|}
===Implementační dodatky===
VICH je při vhodném <math> \alpha\,\!</math> lepší než dva ukazatele. Lineární přidávání nepoužívat pro <math> \alpha > 0.7\,\!</math>, dvojité hashování pro <math> \alpha > 0.9\,\!</math>. Separované řetězce a obecné srůstající hashování používají víc paměti, přemísťování a dvojité hashování zas víc času, tj. nelze říct, které je jednoznačně lepší.
Pro hledání volných řádků se většinou používá seznam (zásobník). Přeplnění se většinou řeší držením <math> \alpha\,\!</math> v rozumném intervalu (<math><1/4, 1>\,\!</math>) a přehashováním do jinak velké tabulky (<math> 2^i\cdot m\,\!</math>) při pře- nebo podtečení; v praxi se doporučuje přehashování odkládat (např. pomocnými tabulkami) a provádět při nečinnosti systému.
DELETE se ve strukturách, které ho nepodporují, řeší označením políčka jako smazaného s možností využití při vkládání. V případě, že polovina polí je blokovaná tímto způsobem, se vše přehashuje. Pro srůstající hashování se toto používat nemusí, máme metody na zachování náhodnosti rozdělení dat.
V praxi je výhodné, známe-li něco o rozdělení vstupních dat, aby ho hashovací funkce kopírovala (většinou to ale nejde), jinak musíme předpokládat rovnoměrnost, což zaručeno zdaleka není. Nutnost rovnoměrného rozdělení vstupních dat lze obejít, viz níže.
==Universální hashování==
'''Idea''': mít místo pevné hash-funkce nějakou množinu <math> H\,\!</math>, z níž funkci náhodně rovnoměrně vyberu. Pak se analýza dělá přes všechny <math> h\in H\,\!</math> a platí pro všechny <math> S\subset U\,\!</math> (<math> S\,\!</math> je daná pevně a <math> h\,\!</math> se k ní volí; <math> |U|=N\,\!</math>). Pro spočítatelnost a formalizaci nutné analytické zadání funkcí <math> h\,\!</math> a známá velikost množiny, což obejdu očíslováním funkcí <math> H = \{ h_i; i\in I \}\,\!</math> a počítáním s indexy (očekávaná hodnota je průměr přes <math> I\,\!</math>). Při použití skutečné velikosti <math> H\,\!</math> v odhadech bychom dostali horší výsledky.
'''Definice''': Systém funkcí <math> H = \{ h_i; i \in I\}: U\to \{0,\dots,m-1\}\,\!</math> je <math> c\,\!</math>-universální, pokud <math> \forall x,y\in U, x\neq y: |\{i\in I; h_i(x)=h_i(y)\}|\leq \frac{c|I|}{m}\,\!</math>.
====Existence <math> c\,\!</math>-universálních systémů====
Předpokládejme, že universum má tvar <math> U=\{0,1,\dots,N-1\}\,\!</math> kde <math> N\,\!</math> je nějaké prvočíslo a vezmeme funkce typu
:<math>h_{a,b}(x)=((ax + b) \mod N)\mod m\,\!</math>
Jsou dobře použitelné, protože se dají počítat rychle. Tato množina funkcí je universální -- vyjdeme z Frobeniovy věty o jednoznačnosti řešení soustav lin. rovnic (protože <math> N\,\!</math> je prvočíslo, můžeme pracovat v <math> \mathbb{Z}_N\,\!</math>, coz je těleso). Rovnice
:<math>h_{a,b}(x)=h_{a,b}(y)\,\!</math>
je ekvivalentní s
:<math>\exists i\in\{0,\dots,m-1\} \wedge \exists r,s\in\{0,\dots,\lceil\frac{N}{m}\rceil -1\} : (ax + b \equiv i + rm) \mod N</math>
:<math>(ay+ b \equiv i + sm) \mod N \,\!</math>
Počet řešení soustavy je omezený číslem <math> m\cdot\lceil\frac{N}{m}\rceil^2\,\!</math> (<math> i\,\!</math> -- <math> m\,\!</math> hodnot, <math> r,s\,\!</math> -- <math> \lceil\frac{N}{m}\rceil\,\!</math> hodnot pro daná <math> x,y\,\!</math>). Pak je systém <math> c\,\!</math>-univerzální pro <math> c = \left(\lceil\frac{N}{m}\rceil\right)^2 / \left(\frac{N}{m}\right)^2\,\!</math> (rozšířím vzorec pro počet řešení <math> \frac{N^2}{m^2}\,\!</math>). Jeho velikost opdovídá <math> N^2\,\!</math>.
====Vlastnosti====
Vyrobíme si pomocnou funkci
:<math>\delta_i(x,y)= 1 \mbox{ pro } h_i(x)=h_i(y), x\neq y \mbox{ a } = 0 \mbox{ jinak }\,\!</math>
Chceme potom spočítat součet <math> \delta_i(x,S)=\sum_{y\in S}\delta_i(x,y)\,\!</math>. Z výsledku vidíme očekávanou délku řetězce pro libovolnou (jednu) množinu dat. Tohle pak sečtu přes všechny mé hash-funkce a z <math> c\,\!</math>-univerzality dostanu
:<math>\sum_{i\in I}\delta_i(x,S)=\sum_{y\in S}\sum_{i\in I}\delta_i(x,y) \leq \sum_{y\in S,x\neq y} c\frac{|I|}{m} = \begin{cases} (|S|-1)c\frac{|I|}{m} & \mbox{ pro } x\in S \\ |S|c\frac{|I|}{m} & \mbox{ jinak } \end{cases}\,\!</math>
Z toho dopočítám (podělením <math> |I|\,\!</math>) horní odhad očekávaného <math> \delta_i(x,S)\,\!</math>, výsledek: očekávaný čas operací MEMBER, INSERT a DELETE v <math> c\,\!</math>-univ. hashování je <math> O(1+c\alpha)\,\!</math> (kde faktor naplnění <math> \alpha=\frac{|S|}{m}\,\!</math>). Čas <math> n\,\!</math> po sobě jdoucích operací na původně prázdné tabulce je <math> O(n(1+\frac{c}{2}\alpha))\,\!</math>. To není lepší hodnota než mají separované řetězce (<math> O(1+\alpha)\,\!</math>), ale tady nechci rovnoměrné rozdělení dat (rovnoměrný výběr <math> i\,\!</math> můžu ovlivnit).
Mějme nějakou očekávanou hodnotu délky řetězce, chci vědět kolik hash-funkcí jí porušuje kolikrát. Z Markovovy nerovnosti se tohle dá spočítat. Máme dánu očekávanou hodnotu <math> \delta_i(x,S) := \mu\,\!</math> a <math> t\geq 1\,\!</math>. Označme <math> I'=\{i\in I|\delta_i(x,S)\geq t\mu\}\,\!</math>. Potom z <math> \mu > \frac{\sum_{i\in I'}\delta_i(x,S)}{|I|} \geq \frac{|I'|}{I}t\mu\,\!</math> dostaneme <math> \frac{|I'|}{|I|} < \frac{1}{t}\,\!</math>. Pravděpodobnost vybrání takovéto "špatné" funkce je tedy menší než <math> \frac{1}{t}\,\!</math>.
Výběr vhodného <math> i\,\!</math> není úplně jednoduchý, protože funkcí může být např až <math> N^2\,\!</math>, tj. nelze provést jednoduchým zavoláním náh. generátoru, nýbrž např. náhodným vybráním každého bitu čísla. Chceme kvůli tomu najít co nejmenší <math> c\,\!</math>-univerzální systémy.
====Dolní odhady velikosti univ. systémů====
Očíslujme hash-funkce z <math> I\,\!</math> a induktivně definujme množiny <math> U_i\,\!</math> jako největší podmnožiny <math> U_{i-1}\,\!</math> takové, že <math> h_{i-1}(U_i)\,\!</math> je jednoprvková. Platí <math> |U_i|\geq \lceil \frac{U_{i-1}}{m}\rceil\,\!</math>, tedy <math> |U_i|\geq\lceil\frac{N}{m^i}\rceil\,\!</math> -- velikost těchto množin klesá s logaritmem a <math> |I|\geq \frac{m}{c}(\lceil\log_m N\rceil -1)\,\!</math>. Takže velikost univ. systému roste alespoň úměrně logaritmu velikosti univerza.
Dokážeme '''existenci 5-univerzálního systému''': Zvolme <math> t\in\mathbb{N}\,\!</math> a k němu vezměme <math> t\,\!</math>-té prvočíslo <math> p_t\,\!</math> tak, že <math> t\ln p_t\geq m\ln N\,\!</math>. Definujme systém funkcí <math> H=\{g_{c,d,l}(x)|t<l\leq 2t, c, d\in\{0,1,\dots,p_{2t}-1\}\}\,\!</math> kde <math> ((c(x\mod p_l)+d)\mod p_{2t})\mod m\,\!</math>. Zřejmě <math> |H|=tp_{2t}^2\,\!</math>. Z teorie čísel plyne, že <math> p_t = O(t\log t)\,\!</math>, tedy <math> \log|H| =\log t + 2\log p_{2t} = O(\log t+2\log 2t+2\log\log 2t)=O(\log t)=O(\log m+\log\log N)\,\!</math>, tj. splňuje odhad.
Spočteme odhad <math> |G = \{(c,d,l); h_{c,d,l}(x)=h_{c,d,l}(y)\}|\,\!</math>, když si množinu rozdělíme na <math> G_1 = \{(c,d,l)\in G; x\mod p_l \neq y\mod p_l\}\,\!</math> a <math> G_2 =\{(c,d,l)\in G;x\mod p_l=y\mod p_l\}\,\!</math>. Pro <math> (c,d,l)\in G_1\,\!</math> existují <math> i\in\{0,\dots,m-1\}\,\!</math> a <math> r,s\in\{0,\dots,\lceil\frac{p_{2t}}{m}\rceil-1\}\,\!</math>, že <math> (c(x\mod p_l)+d\equiv i+rm)\mod p_{2t}\,\!</math> a <math> (c(y\mod p_l)+d\equiv i+sm)\mod p_{2t}\,\!</math>. Z toho dostávám regulární (z vl. <math> G_1\,\!</math>) matici nad <math> \mathbb{Z}_{p_{2t}}\,\!</math>, podle Frobeniovy věty dostávám jedno <math> (c,d)\,\!</math> pro každé <math> (l,i,r,s)\,\!</math> -- celk. počet prvků je
:<math>|G_1|\leq tm(\lceil\frac{p_{2t}}{m}\rceil)^2\leq \frac{tp_{2t}^2}{m}\left(1+\frac{m}{p_{2t}}\right)^2=\frac{|H|}{m}\left(1+\frac{m}{p_{2t}}\right)^2\leq 4\frac{|H|}{m}\,\!</math>
Pro <math> G_2\,\!</math> si označím <math> L=\{l;t<l\leq 2t, x\mod p_l = y\mod p_l\}\,\!</math>. Potom <math> (c,d,l)\in G_2\,\!</math> jen když <math> l\in L\,\!</math>, takže
:<math>|G_2|\leq |L| p_{2t}^2\leq \frac{tp_{2t}^2}{m} = \frac{|H|}{m}\,\!</math>
za podmínky <math> |L|<t/m\,\!</math>, která je splněna z <math> \prod_{l\in L}p_l\leq |x-y|\leq N\,\!</math> (<math> P\,\!</math> dělí <math> |x-y|\,\!</math>) a <math> P>p_t^|L|\,\!</math> (<math> l>t\,\!</math>), což dává <math> |L|\leq\ln N/\ln p_t\,\!</math> a dále z definice. Celkem tedy <math> |G|=|G_1|+|G_2|\leq 5\frac{|H|}{m}\,\!</math>. Za dalších podmínek se dá dokázat i <math> 3.25\,\!</math>-univerzálnost takového systému.
'''Dolní odhad <math> c\,\!</math>''': Platí: <math> c>1-\frac{m}{N}\,\!</math>. Spočítáme <math> \sum_{h\in H}\sum_{x,y\in U}\delta_h(x,y)\,\!</math>: pro pevnou <math> h\,\!</math> vezmu <math> \sum_{x,y\in U}\delta_h(x,y)=\sum_{i=0}^{m-1}u_{i,h}(u_{i,h}-1)\geq \frac{(\sum_{i=0}^{m-1}u_{i,h})^2}{m}-N =\frac{N^2}{m}-N\,\!</math> (z Cauchy-Schwarze, <math> u_{i,h}=|\{x\in U,h(x)=i\}|\,\!</math>). Tedy <math> \sum_{h\in H}\sum_{x,y\in U}\delta(x,y)\geq \frac{|H|N(N-m)}{m}\,\!</math>. Zároveň platí <math> \sum_{h\in H}\sum_{x,y\in U}\delta(x,y)\leq\sum_{x,y\in U}c\frac{|H|}{m}=N^2c\frac{|H|}{m}\,\!</math>, z toho výsledek.
==Perfektní hashování==
Idea -- nalézt hash-funkci, která nedělá kolize pro danou množinu. Nevýhoda: nelze přirozeným způsobem realizovat INSERT, tj. v praxi se nesmí moc často vyskytovat. Tabulka by neměla být o mnoho větší než množina a funkce <math> h\,\!</math> rychle spočitatelná a její realizace nezabírat moc paměti (žádná zadávání tabulkou). Soubor funkcí <math> H:U\to \{0,\dots,m-1\}\,\!</math> je <math> (N,m,n)\,\!</math>-perfektní, pokud <math> \forall S\subseteq U\,\!</math> takové, že <math> |S|=n\,\!</math> existuje <math> h\in H\,\!</math> perfektní pro <math> S\,\!</math>.
====Odhady velikosti====
Každá funkce <math> h\,\!</math> je perfektní pro <math> \sum\{\prod_{j=0}^{n-1}|h^{-1}(i_j);0\leq i_0<\dots<i_{n-1}<m\}\,\!</math>, z Cauchy-Schwarze je max. pro <math> \forall i: |h^{-1}(i)|=\frac{N}{m}\,\!</math>, takže je perfektní pro max. <math> \mathbf{}\binom{m}{n}(\frac{N}{m})^n\,\!</math> množin. Z toho
:<math>|H|\geq \frac{\mathbf{}\binom{N}{n}}{\mathbf{}\binom{m}{n}\left(\frac{N}{m}\right)^n}\,\!</math>
Druhý odhad, přes množiny jako u <math> c\,\!</math>-univ. systémů při <math> |H|=\{h_1,\dots,h_t\}\,\!</math>, dostávám pak <math> |U_t|\leq 1\,\!</math> a <math> N/m^t\leq 1\,\!</math>, tedy <math> t\geq \frac{log N}{log m}\,\!</math>.
====Existence====
Přes matice: <math> M(H)\,\!</math> typu <math> N\times t\,\!</math>. <math> M(H)_{x,i}=h_i(x)\,\!</math>. Pak žádná funkce z <math> H\,\!</math> není perfektní, když <math> M(H)\,\!</math> nemá prostý sloupec. Takových matic je max. <math> \left(m^n-\prod_{i=0}^{n-1}(m-i)\right)^t\cdot m^{(N-n)t}\,\!</math> (počet všech funkcí minus počet prostých (repr. podmaticemi s <math> n\,\!</math> řádky), to celé krát libovolné doplnění na <math> N\,\!</math> řádek). Podmnožin <math> U\,\!</math> velikosti <math> n\,\!</math> je pak <math> \mathbf{}\binom{N}{n}\,\!</math>, čímž vynásobeno mám počet matic, odp. <math> (N,m,n)\,\!</math>-perfektnímu systému. Všech matic je <math> m^{Nt}\,\!</math> -- dám do nerovnosti, vydělím <math> m^{Nt}\,\!</math>, pak zlogaritmuju a zintegruju :) a dostávám podmínku existence <math> t\geq n(\ln N)e^{\frac{n^2}{m}}\,\!</math>.
====Konstrukce funkce====
Chceme splnit rychlou spočitatelnost a paměťovou nenáročnost. Předpokládám univerzum prvočíselné velikosti a funkce typu
:<math>h_k(x)=(kx\mod N)\mod m\,\!</math>
Ozn. <math> b_i^k=|\{x\in S; (kx\mod N)\mod m=i\}|\,\!</math>. Potom pokud <math> h_k(x)\,\!</math> není perfektní, pak nějaké <math> b_i^k =2\,\!</math> a mám <math> \sum_{i=0}^{m-1}(b_i^k)^2\geq n+2\,\!</math>.
Odhadnu výraz <math> \sum_{k=1}^{N-1}((\sum_{i=0}^{m-1}(b_i^k)^2)-n) = \sum_{x\neq y\in S}|\{k; 1\leq k<N, h_k(x)=h_k(y)\}\,\!</math> -- tj. existují <math> i,r,s\,\!</math> taková, že <math> kx\equiv i + rm\mod N\,\!</math> a <math> ky\equiv i + sm\mod N\,\!</math>, z toho <math> k(y-x)\equiv (s-r)m\mod N\,\!</math> a protože je <math> \mathbb{Z}_N\,\!</math> těleso, <math> \forall t\in\{-\lfloor\frac{N}{m}\rfloor,\dots,\lfloor\frac{N}{m}\rfloor\} \exists! k\,\!</math> takové, že <math> k(y-x)\equiv tm\mod N\,\!</math> a takových <math> t\,\!</math> je tedy nejvýše <math> 2\lfloor\frac{N}{m}\rfloor =2\lfloor\frac{N-1}{m}\rfloor\,\!</math>. Dostávám tedy odhad <math> 2(N-1)\frac{n(n-1)}{m}\,\!</math> a z něj (při zachování podmínky perfektnosti <math> h_k(x)\,\!</math>) <math> \sum_{i=0}^{m-1}(b_i^k)^2\leq \frac{2n(n-1)}{m}+n\,\!</math>.
Dá se dokázat trochu slabší předpoklad, že <math> P(k;\sum_{i=0}^{m-1}(b_i^k)^2<\frac{3n(n-1)}{m}+n)\geq 1/4\,\!</math>, který je základem pravděpodobnostního algoritmu. Pak mám deterministický algoritmus, který pro <math> m=n(n-1)+1\,\!</math> nalezne perfektní <math> h_k\,\!</math> v čase <math> O(nN)\,\!</math> (<math> \sum (b_i^k)^2 < 3n\,\!</math>) a pravděpodobnostní, který pro <math> m=2n(n-1)\,\!</math> najde perfektní <math> h_k\,\!</math> v čase <math> O(n)\,\!</math> (<math> \sum (b_i^k)^2 < 4n\,\!</math>).
Mám tedy konstrukci perfektní hash-funkce, ta ale nesplňuje požadavek na malou tabulku (<math> m=\Theta(n^2)\,\!</math>). To se dá vyřešit tak, že po nalezení této funkce najdeme všechny neprázdné množiny <math> S_i=\{s\in S;h_k(s)=i\}\,\!</math> a pro jim odpovídající <math> c_i=|S_i|(|S_i|-1)+1\,\!</math> (pro dvojnásobek v pravděp. metodě) najdeme <math> k_i\,\!</math> takové, že <math> h_{k_i}\,\!</math> je perfektní funkce pro <math> S_i\,\!</math> do tabulky velikosti <math> c_i\,\!</math>. Definujme <math> d_i=\sum_{j=0}^{i-1}c_j\,\!</math>, potom pokud <math> h_k(x)=l\,\!</math>, pak <math> g(x)=d_l+h_{kl}(x)\,\!</math> je perfektní, její hodnota spočitatelná v čase <math> O(1)\,\!</math> a hashuje do tabulky velikosti <math> O(3n)\,\!</math> (<math> O(6n)\,\!</math> s pravděp. případě), je naleznutelná v čase <math> O(nN)\,\!</math> (<math> O(n)\,\!</math>) a pro její uložení do paměti jsou potřeba hodnoty <math> k\,\!</math> a <math> k_i\,\!</math>, vyžadující <math> O(n\log N)\,\!</math> paměti. Pro výpočet <math> g(x)\,\!</math> potřebuji 2 násobení, 2 modulo a 1 sčítání (pro <math> d_i\,\!</math> v paměti), tabulka má velikost <math> \sum c_i\leq\sum (b_i^k)^2<3n\,\!</math>.
===="Malá" funkce====
Toto stále nesplňuje požadavek na málo paměti pro uložení. Víme, že pro <math> m\in\mathbb{N}\,\!</math> je počet prvočísel, která ho dělí <math> O(\frac{\log m}{\log\log m})\,\!</math>, z toho úvahou o dělitelích <math> D=\prod_{1\leq i<j\leq n}(s_j-s_i)\leq N^{n^2}\,\!</math> na <math> n\,\!</math>-prvkové <math> S\,\!</math> a vzorce <math> p_t\leq 2t\ln t\,\!</math> dostanu, že existuje <math> p\,\!</math> o velikosti <math> O(\ln D)=O(n^2\ln N)\,\!</math> takové, že <math> \phi_p(x)=x\mod p\,\!</math> je perfektní pro <math> S\,\!</math>. Deterministické nalezení trvá <math> O(n^3\log n\log N)\,\!</math> (test perfektnosti každého <math> O(n\log n)\,\!</math>), proto použijeme pravděpodobnostní alg (mezi <math> 4cn^2\ln N\,\!</math> přir. čísly je aspoň <math> 1/2\,\!</math> prvočísel, která vyhovují) -- první najde prvočíslo a pak testuje perfektnost, očekávaný počet testů je <math> O(\ln(4cn^2\ln N))\,\!</math>, celkem složitost algoritmu je pak <math> O(n\log n(\log n+\log\log N))\,\!</math>. Najde zhruba až <math> 2\times\,\!</math> větší prvočíslo než deterministický. Tuhle funkci použijeme ke konstrukci hash-funkcí -- nalezneme prvočíslo <math> q_0\,\!</math> aby <math> \phi_{q_0}(x)=x\mod q_0\,\!</math> byla perfektní pro <math> S\,\!</math>, položíme <math> S_1=\{\phi_{q_0}(s)|s\in S\}\,\!</math>, pak najdeme prvočíslo <math> q_1\in<n(n-1)+1,2n(n-1)+2>\,\!</math> a k němu existuje <math> l\in<1,q_0-1>\,\!</math> takové, že <math> h_l(x)=((lx\mod q_0)\mod q_1)\,\!</math> je perfektní pro <math> S_1\,\!</math>, položím <math> S_2=\{h_l(s)|s\in S_1\}\,\!</math> a najdu perfektní <math> g\,\!</math> pro <math> S_2\,\!</math> do tabulky s méně než <math> 3n\,\!</math> řádky. Pak <math> f(x)=g(h_l(\phi_{q_0}(x)))\,\!</math> je perfektní. Funkce <math> q_0\,\!</math> je určena 1 číslem o vel. <math> O(n^2\log N)\,\!</math>, <math> h_l\,\!</math> 2 čísly o velikosti <math> O(n^2)\,\!</math> a <math> O(q_0)\,\!</math>, <math> g\,\!</math> je určená <math> n+1\,\!</math> čísly o <math> O(q_1)\,\!</math>, tj. celkem zadání vyžaduje <math> O(n\log n+\log n+\log\log N)\,\!</math>.
