Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Lekce 10 - Hashovací tabulka

V minulé lekci, Srovnání jednoduchých vyhledávacích struktur, jsme si srovnali jednoduché vyhledávací struktury - algoritmy BST, binární vyhledávací strom, setříděné pole a nesetříděné pole.

Hashovací tabulka, nebo také tabulka s rozptýlenými hodnotami, popř. dokonce hašovací tabulka, je podobně jako binární vyhledávací strom datová struktura optimalizovaná pro potřeby rychlého vyhledávání. V tomto článku si vysvětlíme její princip a srovnáme její vlastnosti s jinými vyhledávacími strukturami.

Jak si tedy hashovací tabulku můžeme představit? V podstatě je to obyčejné pole, pro jednoduchost uvažujme, že je indexované klasicky celými čísly od 0 do N - 1, kde N je délka pole. Položkami pole jsou ukazatele na lineární seznamy, do nichž je možné uložit položky, které mají unikátní vyhledávací klíč (jako je tomu u každé vyhledávací datové struktury). Jako vyhledávací klíč předpokládejme třeba textový řetězec (např. jméno osoby). Vše snad nejlépe ilustruje obrázek tabulky, kde N = 10:

prázdná tabulka - Vyhledávací algoritmy

Prázdná tabulka

To je celá naše datová struktura. Ještě jsme ovšem nezmínili další, přinejmenším neméně důležitý fakt, a to že tato tabulka má k sobě ještě něco navíc, bez čeho by se neobešla - tzv. hashovací funkci. K čemu nám taková funkce slouží? Jednoduše řečeno nám říká, kam máme položky umisťovat a kde je máme hledat, a to na základě jejich vyhledávacího klíče.

Tato funkce je základem celého konceptu hashovací tabulky a proto si ji pojďme trochu více představit. Hashovací funkce by měla splňovat toto:

  • Jejím vstupem je vyhledávací klíč a výstupem tzv. hash, který použijeme jako index do pole. V našem případě je tedy vstup textový řetězec a výstup (hash) číslo v rozsahu 0N - 1.
  • Hash musí být pro dva odlišné vyhledávací klíče s co největší pravděpodobností odlišný. Je jasné, že musí existovat rozdílné vyhledávací klíče, pro něž dostaneme stejný hash, protože textových řetězců je nekonečně mnoho, zatímco počet indexů našeho pole je omezený. Musíme se ovšem snažit takové situace eliminovat, protože, jak uvidíme později, zpomalují fungování naší úžasné tabulky.
  • Měla by být rychlá, aby bylo rychlé i vkládání a vyhledávání.

Koncept hashovacích funkcí není omezen pouze na vyhledávání - využívají se velmi hojně např. v kryptografii, kde pro ně vyžadujeme další vlastnosti. My zde však pro jednoduchost předpokládejme pouze výše zmíněné.

Je třeba zmínit, že neexistuje žádná obecná ideální hashovací funkce. Způsob, jakým hash vypočítáme, musíme zvolit v závisloti na vyhledávacím klíči a na tom, co o něm víme. Pro náš případ si definujme hashovací funkci jako součin ASCII hodnot znaků v řetězci modulo N - tak dostaneme vždy číslo v rozsahu 0 až N - 1 (řekněme, že nepovolujeme prázdné řetězce). Uveďme si pár příkladů:

"hello" -> (104 * 101 * 108 * 108 * 111) mod 10 = 6
"ahoj" -> (97 * 104 * 111 * 106) mod 10 = 8
"kockopes" - > (107 * 111 * 99 * 107 * 111 * 112 * 101 * 115) mod 10 = 0

Vkládání a vyhledávání

Ukázali jsme si, co to hashovací tabulka je. Nyní si ilustrujeme její princip - jak jinak, než na příkladu. Pokusme se vložit do naší tabulky tři řetězce zmíněné výše - "hello", "ahoj" a "kockopes". Každý řetězec nejdřív předáme hashovací funkci a ta nám řekne, na který index je umístit. Skončíme tedy s tabulkou, která vypadá takto:

tabulka s vloženými položkami - Vyhledávací algoritmy

Tabulka s vloženými položkami

Teď se můžeme pokusit vyhledat některý řetězec, např. "hello". Vyhledávání probíhá tak, jak byste asi čekali - hashovací funkci předáme klíč, který chceme vyhledat, tedy řetězec "hello", a ta nám vrátí index, kde položku s tímto klíčem najdeme, tedy číslo 6. Podíváme se tedy do tabulky na index s číslem 6 a položku zde skutečně najdeme. Pokud bychom chtěli vyhledat neeistující řetězec, řekněme "abc", dostali bychom index 4, na němž bychom nenalezli nic a zjistili tak, že položka s klíčem "abc" se v tabulce nenachází.

Jak vidíme, tabulka pracuje extrémně rychle - protože nám stačí vždycky jenom zavolat hashovací funkci a přistoupit do pole nezávisle na velikosti tabulky, je časová složitost vyhledání konstantní! Bohužel ale jako u každé skvělé věci teď přijde na řadu nevyhnutelný zádrhel, jimž jsou možné kolize.

Asi už vás napadlo, co se stane, pokud hashovací funkce umístí některou položku do pole na index, který už je obsazený. Ne, naštěstí nedojde ke zhroucení počítače. Pokud si vzpomínáte, na začátku jsme zmiňovali, že položky pole jsou ukazatele na lineární seznam a proto je možné na jeden index pole umístit libovolné množství položek, tzv. synonym. Pokud vložíme do naší tabulky např. řetězec "starwars", dostaneme pro něj hash 0 a výsledek bude vypadat takto:

konflikt - Vyhledávací algoritmy

Konflikt

V podobném duchu probíhá vyhledávání. Nalezení řetězce "starwars" bude vypadat tak, že jej předáme hashovací funkci, dostaneme index 0, na tento index přistoupíme do pole a nyní musíme lineárně projít celý seznam, který zde najdeme, a každý řetězec porovnat, než položku (ne)nalezneme. Tím se snižuje efektivita tabulky v nejhorším možném případě až na lineární složitost. Taková situace nastane, pokud nám hashovací funkce vrací neustále stejný hash - tehdy skončíme v podstatě s lineárním seznamem:

nejhorší možný případ - Vyhledávací algoritmy

Nejhorší možný případ

Kvůli tomu je nesmírně důležité mít dobře navrženou hashovací funkci vytvářející minimum kolizí. Toho lze ovšem dosáhnout pouze s dobrou znalostí našich dat.

Existuje další možnost řešení kolizí, která se nazývá otevřené adresování. Tento způsob nevyužívá lineárních seznamů - každá položka pole může držet klasicky pouze jeden záznam dat. Pokud dojde při vkládání ke kolizi, hledá se pro vkládaná data předem daným způsobem další volné místo tak dlouho, dokud se nenalezne nebo dokud se neprojde celá tabulka a místo se nenajde (vidíme, že kapacita tabulky je v tomto případě omezená velikostí pole). Když víme, jak jsme pro položky hledali volné místo, můžeme je stejným způsobem v případě kolize vyhledávat - vyhledáváme tak dlouho, dokud záznam nenalezneme, nebo dokud neprojdeme celé pole (což samozřejmě opět snižuje rychlost naší tabulky, takže se kolizím musíme stále snažit zabraňovat).

Způsob hledání volného místa lze zvolit různě. Často se prostě postupuje o položku dál, než narazíme na volné místo - pokud dojdeme na konec pole, jdeme znovu od začátku. Kdybychom pro náš příklad použili tuto alternativu, vypadalo by vkládání řetězce "starwars" takto:

otevřené adresování - Vyhledávací algoritmy

Otevřené adresování

Krok posunu může být delší než jedna (v takovém případě by však velikost pole měla být zvolena jako prvočíslo, aby se zaručil průchod všemi položkami, např. při průchodu pole o velikosti 6 s krokem 2 bychom chodili donekonečna jen po sudých indexech). Další, o něco promyšlenější způsob je použít při kolizi na data druhou hashovací funkci a její výstup použít jako krok posunu, což opět opakujeme, dokud nenajdeme volné místo. Tato technika je výhodnější v tom, že délka kroku závisí na datech a proto dochází méně k vícenásobným kolizím (tzn. kolizím v druhém a vyšším kroku) - pro různé řetězce se zkrátka volné místo bude hledat jinde a tudíž se pravděpodobně rychleji najde.

Závěrem

Hashovací tabulka je velmi efektivní vyhledávací metoda, avšak musíme vědět, kdy a jak ji použít. Pokud vyhledáváme jenom střídmě a potřebujeme ušetřit paměť a režii, jistě zvolíme radši běžné sekvenční vyhledávání v poli. V jiných případech musíme zvážit alternativy jako třeba binární vyhledávací strom. Ten je v porovnání s hashovací tabulkou o něco pomalejší, pokud uvažujeme ideální případ, na druhou stranu pro případ nejhorší strom vítězí. Hashovací tabulka nám navíc neumožňuje vyhledávat klíče v určitém intervalu nebo jenom částečně specifikované klíče - např. všechny řetězce s určitou předponou. Dobře můžeme hashovací tabulku využít třeba k implementaci tabulky symbolů v překladači nějakého jazyka.

V další lekci, Optimalizované vyhledávání v poli - princip děr, si uděláme ukázku optimalizovaného vyhledávání v poli na příkladu Slovníku.


 

Předchozí článek
Srovnání jednoduchých vyhledávacích struktur
Všechny články v sekci
Vyhledávací algoritmy
Přeskočit článek
(nedoporučujeme)
Optimalizované vyhledávání v poli - princip děr
Článek pro vás napsal tastyfish
Avatar
Uživatelské hodnocení:
16 hlasů
Autor studuje informatiku na FIT VUT v Brně, věnuje se tvorbě svých stránek a vlastního softwaru. Má rád logické hádanky a odpočívá při sportu a hudbě.
Aktivity