07.2 Hashovací tabulka
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# Hashovací tabulka
- Pro univerzum $\mathcal{U}$ zvolíme konečnou množinu přihrádek $\mathcal{P}$ (hash table),
- hashovací funkci $h: \mathcal{U} \rightarrow \mathcal{P}$, která každému klíči přidělí jednu přihrádku
- Mohou vznikat kolize
- Vhodné jako její velikost volit prvočíslo
- Ideálně volit kapacitu klidně dvoj/trojnásobnou než počet prvků
# Časová složitost ideálního hashování
- Průměr počtů 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)$
# Příklady dobrých hash. funkcí
# Lineární kongruence
- $k \mapsto ak \bmod{m}$
- $m$ - typicky prvočíslo
- $a$ - dostatečně velká konstanta nesoudělná s $m$ (často se nastavuje blízko celé části $0.618m$)
# Vyšší bity součinu
- $k \mapsto \floor{(ak \bmod{2^{w}}) / 2^{w-\ell}}$
- Pokud hashujeme $w$-bitové klíče do $m = 2^{\ell}$ přihrádek, vybereme $w$-bitovou lichou konstantu $a$ (nesoudělnou s $2^{w}$)
- Pro každé $k$ spočítáme $ak$, ořízneme ho na $w$ bitů a z nich vezmeme nejvyšších $\ell$
- Vzhledem k tomu, že ve většině jazycích přetečení automaticky ořezává výsledek, stačí k výpočtu jedno násobení a bitový posun
# Skalární součin
- $k_{0}, \dots, k_{d-1} \mapsto \left(\sum^{d-1}{i=0} a{i}k_{i}\right) \bmod{m} \enspace$ (pozor, $a_i$)
- Posloupnost klíčů zahashujeme tak, že zahashujeme každý klíč zvlášť a výsledky sečteme
- Pokud $i$-tý klíč $k_i$ zahashujeme [lineární kongruencí](notes/bi-ag1/07-2-hashovaci-tabulka.md#Lineární kongruence), je hashem celé posloupnosti její skalární součin s vektorem konstant $(a_{0}, a_{1}, \dots, a_{d-1}) \bmod{m}$
- Podobně lze hash počítat ve dvojkové soustavě pomocí XORu místo součtu
# Polynom
- $k_{0}, \dots, k_{d-1} \mapsto \left(\sum^{d-1}{i=0} a^{i}k{i}\right) \bmod{m} \enspace$ (pozor, $a^i$)
- Zvolíme jednu konstantu $a$ a počítáme skalární součin zadané posloupnosti s vektorem mocnin $(a^{0}, a^{1}, \dots, a^{d-1}) \bmod{m}$
# Nafukovací hash tabulka a přehashování
- Faktor naplnění $\alpha = n/m$
- Zvětšujeme zhruba 2x velikost, k nejbližšímu prvočíslu
- Znovu přehashovat prvky z původní tabulky a vložit do nové
# Řešení kolizí
- Řetězení (chaining) - otevřené hashování (open hashing)
- Otevřené adresování (open addressing) - uzavřené hashování (closed hashing)