Hašovacia tabuľka

Hašovacia tabuľka alebo hašovacia mapa alebo tabuľka výpočtu adresy transformáciou (kľúča) je v informatike údajová štruktúra, ktorá asociuje kľúče s hodnotami. Primárna efektívne podporovaná operácia je vyhľadávanie: pri zadaní kľúča (napr. meno osoby) nájsť zodpovedajúcu hodnotu (napr. telefónne číslo tejto osoby). Pracuje vďaka transformácii kľúča hašovacou funkciou na haš, číslo, ktoré tabuľka používa na nájdenie požadovanej hodnoty.
Hašovacie tabuľky sa často používajú na implementáciu asociatívnych polí, množín a rýchlych vyrovnávacích pamätí (cache). Rovnako ako polia, hašovacie tabuľky poskytujú vyhľadávanie s konštantným časom O(1) v priemernom prípade, nezávisle od počtu položiek v tabuľke. Ale zriedkavý najhorší prípad môže byť až O (n). V porovnaní s inými údajovými štruktúrami asociatívnych polí sú hašovacie tabuľky najužitočnejšie pre uloženie veľkého množstva údajov.
Hašovacie tabuľky ukladajú údaje na pseudonáhodných miestach, preto prístup k údajom utriedeným spôsobom je veľmi časovo náročná operácia. Iné údajové štruktúry ako samovyvažovacie binárne vyhľadávacie stromy sú vo všeobecnosti oveľa pomalšie (keďže zložitosť vyhľadávania majú O (log n)) a sú skôr zložitejšie na implementáciu ako hašovacie tabuľky, ale udržiavajú si neustále utriedenú štruktúru položiek. Pozri porovnanie hašovacích tabuliek a samovyvažovacích binárnych vyhľadávacích stromov.

Bežné využitie hašovacích tabuliek

Hašovacie tabuľky sa bežne využívajú pre tabuľky symbolov, rýchle vyrovnávacie pamäte a množiny.
Hašovacie tabuľky nie sú vo všeobecnosti perzistentnými údajovými štruktúrami v tom zmysle, že neexistuje jednoduchý a vzhľadom na úložný priestor efektívny spôsob, ako aktualizovať hašovaciu tabuľku a zároveň si udržať prístup k jej predchádzajúcej kópii. Je to však možné implementovaním VListu, čím sa stane perzistentnou, ale nepriaznivo to ovplyvní výkon. hašovacie tabuľky môžu byť „perzistentné“ v inom zmysle – môžu byť uložené na disku. Databázové indexy bežne používajú diskové údajové štruktúry založené na hašovacích tabuľkách.
V počítačovom šachu sa hašovacia tabuľka bežne používa na implementáciu transpozičnej tabuľky.

Riešenie kolízií

Ak hašovacia funkcia vráti pre dva rôzne kľúče rovnaký index, zodpovedajúce záznamy nemožno uložiť na to isté miesto. Keďže je už obsadené, musíme nájsť iné miesto pre uloženie záznamu a zabezpečiť, aby sme ho našli, keď ho neskôr vyhľadáme.
Pre predstavu dobrej stratégie riešenia kolízií si predstavte nasledovný výsledok odvodený použitím narodeninového paradoxu. Aj za predpokladu, že naša hašovacia funkcia vracia indexy rovnomerne rozložené v poli aj pre pole s 1 miliónom záznamov, existuje 95% pravdepodobnosť aspoň jednej kolízie predtým, ako bude obsahovať 2 500 záznamov.
Existuje niekoľko techník riešenia kolízií, ale najpoužívanejšími sú reťazenie a otvorené adresovanie. Súhrnný prehľad vypracoval Morris v roku 1968.
Na rozptyľovanie záznamov v tabuľke, aby sa zabránilo kolíziám, môže slúžiť generátor krížových odkazov.

Reťazenie

V najjednoduchšej technike zreťazenej hašovacej tabuľky každé miesto v poli odkazuje na zreťazený zoznam vložených záznamov, pre ktoré hašovanie kľúča koliduje na rovnakú hodnotu. Pre vloženie je potrebné nájsť správne miesto a pridať ho na jeden koniec; pre mazanie je potrebné prehľadávanie zoznamu a odstránenie.
Zreťazené hašovacie tabuľky majú výhodu v porovnaní s tabuľkami s otvorenou adresáciou, že operácia odstránenia je jednoduchá a zmenu veľkosti tabuľky je možné odkladať oveľa dlhšie, pretože výkon sa znižuje oveľa pomalšie aj ak je miesto obsadené. Vlastne mnohé zreťazené hašovacie tabuľky nepotrebujú zmenu veľkosti vôbec, pretože degradácia výkonu je lineárna so zapĺňaním tabuľky. Napríklad zreťazená hašovacia tabuľka obsahujúca dvojnásobok odporúčanej dátovej kapacity by bola priemerne iba asi dvakrát pomalšia ako rovnaká tabuľka s odporúčanou kapacitou (za podmienky dobrej distribúcie kľúčov).
Zreťazené hašovacie tabuľky dedia nevýhody spojových zoznamov. Ak sa ukladajú malé záznamy, režijné náklady spojového zoznamu môžu byť významné. Ďalšou nevýhodou je, že prechádzanie spojovým zoznamom má nízky cache výkon.
Namiesto zoznamov je možné pre reťazenie použiť alternatívne údajové štruktúry. Napríklad použitím samovyvažovacieho stromu je možné znížiť teoretický čas najhoršieho prípadu z O(n) na O(log n). Ale preto, že každý zoznam by mal byť krátky, tento prístup zvyčajne nevedie k zvýšeniu výkonu, iba ak by bola tabuľka navrhnutá na fungovanie pri plnej kapacite alebo vykazovala nezvyčajne vysoké množsto kolízií. Je tiež možné použiť dynamické polia pre zníženie režijných nákladov a zvýšenie výkonnosti cache pri malých záznamoch.
Niektoré implementácie reťazenia používajú optimalizáciu pri uložení prvého záznamu každej reťaze v tabuľke. Hoci to môže zvýšiť výkon, vo všeobecnosti sa to neodporúča: zreťazené tabuľky s rozumnými hodnotami zaťaženia obsahujú veľký pomer voľného miesta a viac miesta spôsobuje väčšie mrhanie pamäťou.

Pravdepodobnostné hašovanie

Snáď najjednoduchším riešením kolízie je vymeniť hodnotu, ktorá sa už na danom mieste nachádza za novú hodnotu, alebo o niečo menej bežne, vyhodiť záznam, ktorý sa má vložiť. V neskorších vyhľadávaniach to môže viesť k nenájdenému záznamu. Táto metóda je obzvlášť užitočná pre implementáciu cacheovania.
Ešte efektívnejším (vzhľadom na úložný priestor) je podobné riešenie, ktoré si necháva zakaždým iba jeden bit indikujúci, či na toto miesto bola alebo nebola vložená hodnota. False negatives cannot occur, but false positives can, pretože keď sa pri hľadaní nájde bit nastavený na jednotku, tvrdí iba, že hodnota bola nájdená, aj keď je to iba ďalšia hodnota náhodou hašovaná na rovnaké miesto. V skutočnosti je takáto hašovacia tabuľka špecifickým typom Bloomovho filtra.

Problémy hašovacích tabuliek

Hoci hašovacie tabuľky potrebujú na vyhľadanie v priemere konštantný čas, skutočne strávený čas môže byť významný. Vyhodnotenie dobrej hašovacej funkcie môže byť pomalá operácia. Obzvlášť v prípadoch, kde je možné použiť jednoduché indexované pole, je to zvyčajne rýchlejšie.
Hašovacie tabuľky vo všeobecnosti vykazujú zlú lokalitu referencie –- t. j. údaje, ku ktorým pristupujeme sú zdanlivo náhodne rozložené v pamäti. Pretože hašovacie tabuľky používajú prístupové vzory, ktoré skáču z miesta na miesto, môže to spôsobovať cache misses procesora a tým veľmi zdržovať (pozri cache CPU). Kompaktné údajové štruktúry ako polia, ktoré sa prehľadávajú lineárne, môžu byť rýchlejšie, ak je tabuľka pomerne malá a porovnanie kľúčov je lacná operácia ako pri celých číslach. Podľa Moorovho zákona sa veľkosti cache zväčšujú exponenciálne, takže veľkosť „malej tabuľky“ sa môže časom zväčšovať. Hranica optimálneho výkonu sa mení od systému k systému; napríklad test na Parrote ukazuje, že jeho hašovacie tabuľky sú výkonnejšie ako lineárne pokusy vo všetkých okrem najtriviálnejších prípadov (jeden až tri záznamy).
Významnejšie je, že hašovacie tabuľky sú náročnejšie na implementáciu a používanie. Hašovacie tabuľky závisia na návrhu efektívnej hašovacej funkcie pre každý typ kľúča, ktorú je zvyčajne ťažšie navrhnúť a zdĺhavejšie testovať ako čistú funkciu porovnania, ktorú vyžadujú samovyvažovacie binárne vyhľadávacie stromy. V tabuľkách s otvoreným adresovaním je ešte jednoduchšie navrhnúť zlú hašovaciu funkciu.
Navyše v niektorých aplikáciách môže útočník, ktorý pozná hašovaciu funkciu, zámerne dodávať informácie, ktoré spôsobujú najhorší prípad kvôli nadmerným kolíziám, čo sa odrazí na slabom výkone (napr. DoS útok). V kritických aplikáciách môže byť výhodnejšia štruktúra s lepšou zárukou pre najhorší prípad. Pozri aj Crosby a Wallach: Denial of Service via Algorithmic Complexity Attacks.

Poznámky pod čiarou

  Morris, R.: Scatter Storage Techniques. , Comm. ACM 1968, s. 38-34