Hašovací tabulka

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Malý telefonní seznam jako 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 podle takového pravidla (viz hašovací funkce), aby klíč byl co nejjednoznačněji určen, tj. aby pravděpodobnost přiřazení stejného klíče dvěma a více rozdílným položkám byla co nejnižší a aby rozptyl hodnot klíčů pro dvě obsahově blízké položky byl co nejvyšší.

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 vhodné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[editovat | editovat zdroj]

Protože potenciálních klíčů je typicky víc než je velikost tabulky, vznikají v obecnosti kolize, tj. 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í[editovat | editovat zdroj]

Podle způsobu řešení kolizí se hašovací tabulky dělí na dva základní druhy, a to 1) Řešení kolizí zřetězením a 2) 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ů[editovat | editovat zdroj]

Každá položka tabulky obsahuje (pointr 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[editovat | editovat zdroj]

Tento druh tabulek je obvyklá implementace. Protože neobsahuje pointry 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 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í zkoušení 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í[editovat | editovat zdroj]

Hlavní článek: Perfektní hašování

Příklad je Cormackovo hašování.

Rostoucí tabulky a přehašování[editovat | editovat zdroj]

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í.

Distribuované tabulky[editovat | editovat zdroj]

Univerzální hašování[editovat | editovat zdroj]

Metoda založená na randomizaci hašovací funkce, tj. náhodném výběru funkce z vhodné množiny funkcí.

Výhody a nevýhody[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]