Hashovací tabulka je datová struktura, která umožňuje rychlé vyhledávání, vkládání a odstraňování prvků. Jedná se o implementaci asociačního pole, kde klíče jsou mapovány na hodnoty pomocí hashovací funkce.
Hashovací funkce přijímá klíč a vrací index do pole, kde je uložena hodnota. Pokud dojde k tzv. kolizi, kdy různým klíčům je přiřazena stejná hodnota, hashovací tabulka používá nějakou formu řešení kolizí, například otevřené hašování nebo řetězení.
Výhodou hashovací tabulky je rychlost vyhledávání, vkládání a odstraňování prvků, která závisí na kvalitě hashovací funkce. Pokud je funkce dobře navržena, operace s hashovací tabulkou mají časovou složitost O(1). Nevýhodou může být náročnost řešení kolizí, které mohou snižovat efektivitu hashovací tabulky.
Hashovací funkce je matematická funkce, která převádí vstupní data libovolné délky (např. textový řetězec) na výstup fixní délky (typicky číselný identifikátor), který se nazývá hash. Tato funkce musí splňovat následující podmínky:
Hashovací funkce jsou důležité pro využití hashovací tabulky, protože umožňují rychlé a efektivní vyhledávání v tabulce. Vyhledávání v hashovací tabulce probíhá tak, že se aplikuje hashovací funkce na klíč, podle kterého se má vyhledat hodnota, a vypočtený hash se použije jako index do pole, kde je hodnota uložena.
Existuje mnoho různých hashovacích funkcí, které se liší svými vlastnostmi a vhodností pro různé účely. Mezi nejpoužívanější patří například MD5, SHA-1, SHA-256.
Kolize jsou problémem při použití hashovacích funkcí a hashovacích tabulek, protože dvě různé vstupní hodnoty mohou mít stejný hash. Existuje několik způsobů, jak řešit kolize:
Výběr řešení závisí na konkrétní aplikaci, velikosti hashovací tabulky, počtu uložených hodnot a způsobu použití hashovací tabulky.
Při použití otevřeného hashování (také známého jako lineární nebo sekvenciální sondování) se při vkládání nové hodnoty do hashovací tabulky v případě kolize pokračuje ve vyhledávání dalšího volného místa v tabulce a hodnota se uloží na toto místo. Pro vyhledání hodnoty se nejprve použije hashovací funkce k určení indexu v tabulce, na kterém se očekává, že se hodnota nachází. Pokud je toto místo již obsazené, použije se sondování, tedy prohledání následujících indexů v tabulce, dokud se nenajde první volné místo.
Existují různé metody sondování, například lineární sondování, kde se hledají volná místa postupně za sebou, kvadratické sondování, které se snaží najít volné místo pomocí kvadratické funkce, nebo dvojité hashování, kdy se použije druhá hashovací funkce pro určení nového indexu v případě kolize.
Otevřené hashování je jednoduché na implementaci a má relativně malou paměťovou náročnost, ale může být náchylné k tzv. shlukování, kdy se v tabulce vytvoří shluk obsazených indexů, což snižuje efektivitu vyhledávání a zvyšuje počet kolizí.
Lineární sondování je metoda řešení kolizí v otevřeném hashování, kde pokud je cílový slot v hashovací tabulce již obsazen, vyhledávací algoritmus pokračuje procházením následujících slotů v tabulce, dokud nenajde první prázdný slot, kam může vložit danou hodnotu.
Kvadratické sondování je metoda řešení kolizí v otevřeném hashování, která řeší shlukování kolizí a výrazné zpomalování přístupu při častých kolizích při použití lineárního sondování. Metoda kvadratického sondování používá pro hledání nového volného slotu v hashovací tabulce kvadratickou posloupnost kroků, kde se nový slot vyhledává podle vzorce:
nový_index = (první_hashování(klíč) + c1*i + c2*i^2) % velikost_tabulky
kde první_hashování(klíč) je index určený první hashovací funkcí, i je počet průchodů tabulkou, c1 a c2 jsou konstanty volené tak, aby zajistily, aby každý slot byl pokryt.
Tato metoda zahrnuje použití kvadratické posloupnosti kroků pro výpočet následujícího indexu v hashovací tabulce, což umožňuje, aby byly záznamy s různými klíči rovnoměrně rozmístěny v tabulce.
Dvojité hashování je metoda sondování používaná při řešení kolizí v otevřeném hashování, kdy se použije druhá hashovací funkce pro určení dalšího indexu v tabulce, pokud je první index již obsazen.
Řešení kolizí pomocí řetězení (anglicky "chaining") je metoda používaná v otevřeném hashování, kdy každý slot v hashovací tabulce obsahuje odkaz na seznam záznamů s klíči, které se hashují na tento slot. Pokud se nějaké dva klíče hashují na stejný slot, vkládají se do seznamu na tomto slotu. Pokud poté aplikace vyhledává hodnotu podle klíče, nejprve se aplikuje hashovací funkce na klíč, aby se určil index v hashovací tabulce, a poté se prohledají všechny záznamy v seznamu, který se nachází na tomto indexu.
Při použití této metody může být hashovací tabulka méně hustá, než je kapacita tabulky, což umožňuje úsporu paměti. Nevýhodou je, že pro vyhledání hodnoty může být nutné procházet více záznamů v seznamu, což může vést k pomalejšímu vyhledávání.