Datová struktura, která umožňuje reprezentovat dynamickou podmnožinu prvků s klíči $K \subseteq \mathcal{U}$, kde $|K| \ll |\mathbb{U}|$ a efektivně podporuje operace:
Find ($k$): zjisti, zda prvek $k \in K$ (případně vrať hodnotu prvku)
Insert ($k$): pokud $k(x) \notin K$, vlož $x$ do slovníku
Delete ($k$): pokud $k(x) \in K$, vymaž $x$ ze slovníku
Prvky slovníku jsou dvojice (klíč, hodnota).
Klíč prvku $x$ značíme $k(x)$ a jsou unikátní
Množinu všech možných klíčů, které se mohou ve slovníku vyskytnout nazýváme univerzum $\mathcal{U}$
Pro menší rozsahy univerza $\mathcal{U}$ lze použít například bitové pole. Potom časová složitost operací bude zjevně $O(1)$. Nicméně paměťové nároky budou $\Theta(|\mathcal{U}|)$. Podobně na tom bude tabulka s přímým adresováním podle klíčů.
V praxi ale bývá velikost univerza $|\mathcal{U}|$ obrovské číslo.
Klasické slovníky (překladové, výkladové) používají (abecedně) seřazená pole: hledání je logaritmické, vkládání či mazání je lineární.
Zde se budeme věnovat hešovacím tabulkám (hash tables, alternativně se jim říká rozptylovací tabulky). Cílem hešování je skloubit nízké paměťové nároky operací, tzn. $O(|K|)$, a přitom zachovat konstantní složitost operací, i když pouze v průměrném případě
Pro nějaké univerzum klíčů $\mathcal{U}$, zvolme konečné pole přihrádek $P = \{0, . . . , m-1\}$ (hešovací tabulku) a hešovací funkci $h : \mathcal{U} \rightarrow \mathcal{P}$, která každému klíči univerza přidělí jednu přihrádku.
Chceme-li uložit množinu prvků s klíči $K \subseteq \mathcal{U}$, rozmístíme její prvky do přihrádek: prvek s klíčem $k \in K$ umístíme do přihrádky $h(k)$. Budeme-li hledat nějaký prvek s klíčem $k \in \mathcal{U}$, víme, že nemůže být jinde než v přihrádce $h(k)$.
Díky poměru $m$ a $|\mathcal{U}|$ ($m \ll |\mathcal{U}|$) se bude stávat, že několik prvků padne do stejné přihrádky. Tomu se říká kolize. Cílem je volit $m$ a $h$ tak, aby se počet kolizí minimalizoval.
Složitost operací Find ($k$) a Insert ($x$) zjevně závisí na složitosti
výpočtu hešovací funkce a na tom, jak rozmísťuje ukládané prvky do přihrádek.
Ideální hešovací funkce $h : \mathcal{U} \rightarrow \mathcal{P}$ vypočte číslo přihrádky v konstantním čase a zadanou $n$-prvkovou množinu vstupních klíčů $K$ rozprostře mezi m přihrádek $\mathcal{P}$ dokonale rovnoměrně, tzn. všechny přihrádky budou mít nejvýše $⌈n/m⌉$ prvků.
Ideální hešovací funkce je obvykle nemožné sestrojit, proto se používají funkce, které se chovají „prakticky náhodně“.
Ukážeme několik příkladů hešovacích funkcí, pro které bylo experimentálně ověřeno, že dobře hešují nejrůznější typy dat.
Zde $m$ je typicky prvočíslo a $a$ je nějaká dostatečně velká konstanta nesoudělná s $m$.
Často se a nastavuje blízko celé části $0.618m$.
Pokud hešujeme $w$-bitové klíče do $m = 2l$ přihrádek, vybereme $w$-bitovou lichou konstantu a (nesoudělnou s $2w$).
Pak pro každé $k$ spočítáme $ak$, ořízneme ho na $w$ bitů a z nich vezmeme nejvyšších $l$.
Vzhledem k tomu, že přetečení ve většině programovacích jazyků automaticky ořezává výsledek, stačí k výpočtu hešovací funkce jedno násobení a bitový posun.
Posloupnost klíčů zahešujeme tak, že zahešujeme každý klíč zvlášť a výsledky sečteme.
Pokud $i$-tý klíč $k_i$ zahešujeme lineární kongruencí $k_i \rightarrow a_i k_i \mod m$, je heš celé posloupnosti její skalární součin s vektorem konstant ($a_0, a_1, . . . , a_{d−1}$) modulo $m$.
Podobně lze heš počítat v dvojkové soustavě pomocí operace XOR místo součtu.
Zvolíme jednu konstantu $a$ a počítáme skalární součin zadané posloupnosti s vektorem mocnin ($a_0, a_1, . . . , a_{d−1}$) a opět modulo $m$
Přestože jsou vlastnosti hešovacích funkcí často postaveny na experimentálních výsledcích, pro některé případy hešování lze provést i exaktní analýzu.Požadované vlastnosti hešovací funkce:
Výpočet $h(k)$ je rychlý ($O(1)$) a funkce $h$ neukládá žádná data do paměti. Speciálně je tedy její výpočet nezávislý na historii předchozích volání.
Hešovací funkce $h$ rozděluje univerzum $\mathcal{U}$ do přihrádek rovnoměrně, například takto:
Uvažujme hešovací tabulku velikosti $m$ s $n$ prvky a s hešovací funkcí $h$ a nechť jsou splněny předpoklady 1. a 2. z předchozího
pozorování.
Nechť navíc platí, že vstupní data jsou z univerza $\mathcal{U}$ vybírána nezávisle rovnoměrně náhodně.
Potom
průměr počtu prvků v přihrádce je $n/m$,
počet prvků v přihrádce je $O(n/m)$ pro skoro všechny přihrádky
průměrný počet operací vykonaných při hledání, vkládání i mazání je $O(n/m)$