Hashovací tabulka

Algoritmy Vyhledávání Hashovací tabulka

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

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

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

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

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í

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.


 

  Aktivity (1)

Článek pro vás napsal tastyfish
Avatar
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ě.

Jak se ti líbí článek?
Celkem (4 hlasů) :
55555


 



 

 

Komentáře

Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

K tomuto tématu jsem se již při psaní zdejších algoritmů nedostal, jsem moc rád, že jsi to zde tak hezky vysvětlil :)

Odpovědět 17.7.2013 12:39
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
tastyfish
Redaktor
Avatar
Odpovídá na David Čápka
tastyfish:

Díky, snad to někomu bude k užitku :)

Odpovědět  +1 17.7.2013 13:39
škoda mluvit
Avatar
Kit
Redaktor
Avatar
Kit:

Navazující lineární seznam je jen jednou z několika možností, jak se vypořádat s kolizemi. Často se podle druhé hashovací funkce vyhledává náhradní volná pozice v původním poli. Někdy dokonce i tak, že se původní klíč přesune na novou pozici.

Odpovědět 17.7.2013 13:56
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
tastyfish
Redaktor
Avatar
Odpovídá na Kit
tastyfish:

Díky za připomínku, kdyžtak tam o téhle možnosti něco dopíšu ;)

Odpovědět 17.7.2013 14:06
škoda mluvit
Avatar
Kit
Redaktor
Avatar
Odpovídá na tastyfish
Kit:

Možná by toho bylo na další díl :)

Odpovědět  +1 17.7.2013 14:35
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Kit
Redaktor
Avatar
Kit:

Zvládl bys i AVL a B-stromy? Nejsou sice tak výkonné, ale zato jsou udržovány seřazené.

Odpovědět 17.7.2013 15:25
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
tastyfish
Redaktor
Avatar
Odpovídá na Kit
tastyfish:

Dopsal jsem tam pár odstavců o těch dalších technikách řešení kolizí, už se to publikuje. No dívám se, že o AVL stromech už tady nějaký článek je, a B-stromy bych napsat mohl, ale musel bych si je trošku zopakovat ^^

Odpovědět 18.7.2013 9:46
škoda mluvit
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na tastyfish
David Čápka:

Já jsem tenkrát skončil u binárních stromů, ty by měly být dobře popsané. Co se týče AVL, mám dojem, že je to jen informační článek, není tam popis rotací atd.

Odpovědět 18.7.2013 9:57
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 8 zpráv z 8.