Hashovací tabulka

Hašovací tabulka (popřípadě hashovací tabulka nebo hešovací tabulka) je vyhledávací datová struktura, která asociuje hašovací klíče s odpovídajícími hodnotami. Hodnota klíče je spočtena z obsahu položky pomocí nějaké hašovací funkce. Obvykle požadujeme nebo se alespoň snažíme, aby výpočet funkce byl rychlý, vypočítané klíče byly náhodné a rovnoměrně rozdělené mezi indexy tabulky a aby podobné hodnoty měly vzdálené klíče.^[zdroj?!]

Využití je např. pro rychlé vyhledávání položky v poli nebo v jiném homogenním datovém typu. Pomocí hašovací funkce přiřazujeme hodnotě klíče index (ukazatel) do homogenní datové struktury. Při zápisu obsahu položky zapíšeme položku na odpovídající místo. Pokud je obsazeno, pak pomocí vhodného algoritmu přiřadíme pro položku další volný index. Při vyhledávání položky spočteme s pomocí klíče index hledané položky. Pokud již bylo odpovídající místo přepsáno položkou s jiným klíčem, opět podle stejného algoritmu prohledáváme další položky. Při správně zvolené velikosti (počtu položek) homogenní datové struktury a vhodně zvolené hašovací funkci má tento algoritmus složitost v průměrném (tj. očekávaném) případě shora omezenou na O(1).

Kolize

Kolize obecně vznikají, protože potenciálních klíčů je typicky víc, než je velikost tabulky. Kolize je situace, kdy se záznamy s různými klíči hašují zvolenou funkcí na stejné místo.

Na rozdíl od indexování v klasickém poli, při hašování možnost vzniku kolizí taky vyžaduje, abychom v tabulce testovali, zdali je na místě určeném hašovací funkcí prvek s hledaným klíčem.

Řešení kolizí

Podle způsobu řešení kolizí se hašovací tabulky dělí na dva základní druhy:

Řešení kolizí zřetězením
Otevřená adresace

Za speciální varianty pak lze považovat situace, kdy kolize nevznikají (tzv. perfektní hašování), nebo se ignorují a řeší prostým přepisováním (např. v transpozičních tabulkách). V posledním případě není zaručeno, že data vložená do tabulky tam najdeme, proto toto řešení není vhodné pro klasickou hašovací tabulku. Ale tuto strukturu lze použít například jako softwarovou cache.

Zřetězení záznamů

Každá položka tabulky obsahuje (ukazatel na) seznam prvků zahašovaných na stejné místo. Při hledání projdeme celý seznam prvků. Výhodou je, že faktor naplnění může být větší než 1.

Otevřená adresace

Tento druh tabulek je obvyklá implementace. Protože neobsahuje ukazatele na zřetězené prvky, je paměťově úspornější, neboli ve stejné paměti lze reprezentovat větší tabulku. Tabulka obsahuje všechny prvky ve svých položkách. Kolize se řeší způsobem popsaným výše, tj. pokud je při vkládání pozice již obsazena, je nějakým algoritmem určeno náhradní místo, případně opakovaně, dokud se nepodaří vkládaný prvek umístit na volné místo. Při vyhledávání je nutno projít stejnou posloupnost míst, dokud není prvek nalezen, anebo dokud se nenarazí na volné místo, což znamená, že hledaný prvek v tabulce není. Protože při otevřené adresaci jsou všechny prvky v tabulce, je faktor naplnění nutně menší než 1.

Metody používané pro určení náhradních míst jsou např. lineární pokusy a druhotné hašování.

Podle metody se tabulky naplňují nejvýše přibližně na 70–90 %, protože pak se doby operací výrazně prodlužují. Při naplnění je nutno přehašovat do nové tabulky.

Perfektní hašování

Příkladem perfektního hašování je Cormackovo hašování.

Rostoucí tabulky a přehašování

Jedna z nevýhod hašovacích tabulek je, že potřebujeme určit velikost tabulky založenou na odhadovaném počtu vkládaných prvků. Tato nevýhoda se týká ve větší míře tabulek s otevřenou adresací, protože mají faktor naplnění vždy menší než 1.

Pokud budeme při přetečení zvětšovat tabulku geometrickou řadou (např. vždy na dvojnásobek), bude celková očekávaná amortizovaná složitost operací konstantní (tj. O(1)), i když započítáme čas všech přehašování. To znamená, že pokud rozpočítáme čas přehašování na jednotlivé prvky, bude příspěvek jednoho prvku konstantní, tj. čas nezávisí na počtu prvků ve struktuře (ani na počtu postupných přehašování).

Podobným způsobem lze tabulku zmenšovat na polovinu, pokud počet prvků podteče 1/8 velikosti tabulky. Po přehašování má tabulka 1/4 - 1/2 prvků a do dalšího přehašování se nutně vykoná dost operací, které ho amortizovaně zaplatí.

Implementačně je jednodušší přehašování realizovat dávkově, kdy pozastavíme program, který tabulku využívá a vše naráz přehašujeme. Druhá metoda je postupné přehašování bez zastavení programu, kdy současně nějakou dobu používáme starou i novou tabulku. Při každé operaci přehašujeme několik prvků a až jsou všechny prvky přemístěny, starou tabulku dealokujeme.

Distribuované tabulky

Univerzální hašování

Metoda založená na randomizaci hašovací funkce, tj. náhodném výběru funkce z vhodné množiny funkcí. Výhodou je, že průměrný případ nastává pro každá konkrétní data, protože se uvažuje průměr přes všechny hašovací funkce. Důsledkem je, že univerzální hašování nepožaduje rovnoměrné rozdělení dat a vyhledávaných klíčů. Ale podobně jako u jiných metod založených na randomizaci, pro konkrétní data může být konkrétní volba funkce (s malou pravděpodobností) nevhodná a následně doba běhu dlouhá.

Výhody a nevýhody

Hašování je v porovnání s jinými vyhledávacími metodami (např. vyhledávacími stromy (nejen binárními)) v průměrném případě asymptoticky rychlejší. Neposkytuje ale záruky pro nejhorší případ.

Hašování potřebuje úplný klíč, tj. neumožňuje dobré vyhledávání pro částečně známý klíč pro strukturované klíče nebo klíče ve vícerozměrném prostoru. Taktéž neposkytuje intervalové dotazy, tj. vyhledání všech klíčů v daném intervalu, a s tím související sekvenční průchod reprezentovanou množinou prvků, resp. elementárnější operace následníka a předchůdce. Pro tyto typy dotazů se používají vyhledávací stromy. Hašovací tabulka umožňuje pouze dotazy na jednotlivé klíče.

Pojem úplný klíč neznamená, že musíme hašovat celá data (např. celý obsah objektu v OOP), ale že ta část dat, kterou používáme jako klíč, musí být celá určená.

Při otevřené adresaci metody kromě lineárního zkoušení neposkytují operaci vypuštění prvku (Delete), pouze tzv. pseudodelete, tj. zneplatnění prvku. Tyto zneplatněné prvky se vypustí při přehašování.

Implementace

Protože hašovací tabulka obvykle obsahuje mnoho neobsazených položek, jsou v tabulce uloženy pouze pointry na skutečná data. Tím se šetří paměť (pointry jsou obvykle značně menší než data) za cenu zpomalení kvůli jednomu nepřímému přístupu navíc.

Jedna položka v tabulce může pojmout i víc záznamů (má víc slotů), například když hašujeme do stránek disku.

Tabulky jako datové struktury nemusí mít velikost mocniny 2, která se typicky používá při kryptografických hašovacích funkcích. Lze použít například tabulky prvočíselné velikosti. Pro závěrečný výpočet klíče se obvykle používá modulární aritmetika, kde modul je velikost tabulky.

Pokud se k datům přistupuje nerovnoměrně, lze při vyhledávání a vkládání prvky v tabulce přesouvat, aby se příště našly rychleji. Dvě základní metody úprav jsou přesun prvku na začátek řetízku a výměna s předcházejícím prvkem v řetízku. Myšlenka je podobná, jako u Splay stromů.

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu rozptylová tabulka na Wikimedia Commons