Haš tabuľka

Hashovacie tabuľka, alebo tiež tabuľka s rozptýlenými hodnotami, popr. dokonca hašovacia tabuľka, je podobne ako binárny vyhľadávací strom dátová štruktúra optimalizovaná pre potreby rýchleho vyhľadávania. V tomto článku si vysvetlíme jej princíp a zrovnáme jej vlastnosti s inými vyhľadávacími štruktúrami.

Ako si teda hashovacie tabuľku môžeme predstaviť? V podstate je to obyčajné pole, pre jednoduchosť uvažujme, že je indexované klasicky celými číslami od 0 do N - 1, kde N je dĺžka poľa. Položkami polia sú ukazovatele na lineárne zoznamy, do ktorých je možné uložiť položky, ktoré majú unikátny vyhľadávací kľúč (ako je tomu u každej vyhľadávacie dátové štruktúry). Ako vyhľadávací kľúč predpokladajme treba textový reťazec (napr. Meno osoby). Všetko snáď najlepšie ilustruje obrázok tabuľky, kde N = 10:

prázdna tabuľka

To je celá naša dátová štruktúra. Ešte sme však nespomenuli ďalšie, prinajmenšom nemenej dôležitý fakt, a to že táto tabuľka má k sebe ešte niečo navyše, bez čoho by sa nezaobišla - tzv. Haš funkciu. Načo nám taká funkcia slúži? Jednoducho povedané nám hovorí, kam máme položky umiestňovať a kde ich máme hľadať, a to na základe ich vyhľadávacieho kľúča.

Táto funkcia je základom celého konceptu hashovacie tabuľky a preto si ju poďme trochu viac predstaviť. Hashovacie funkcie by mala spĺňať toto:

• Jej vstupom je vyhľadávací kľúč a výstupom tzv. Hash, ktorý použijeme ako index do poľa. V našom prípade je teda vstup textový reťazec a výstup (hash) číslo v rozsahu 0 až N - 1.
• Hash musí byť pre dva odlišné vyhľadávacie kľúče s čo najväčšou pravdepodobnosťou odlišný. Je jasné, že musí existovať rozdielne vyhľadávacie kľúče, pre ktoré dostaneme rovnaký hash, pretože textových reťazcov je nekonečne veľa, zatiaľ čo počet indexov nášho poľa je obmedzený. Musíme sa však snažiť také situácie eliminovať, pretože, ako uvidíme neskôr, spomaľujú fungovanie našej úžasnej tabuľky.
• Mala by byť rýchla, aby bolo rýchle aj vkladanie a vyhľadávanie.

Koncept hashovacie funkcií nie je obmedzený len na vyhľadávanie - využívajú sa veľmi hojne napr. V kryptografii, kde pre nich vyžadujeme ďalšie vlastnosti. My tu však pre jednoduchosť predpokladajme iba vyššie zmienené.

Je potrebné spomenúť, že neexistuje žiadna všeobecná ideálne haš funkcie. Spôsob, akým hash vypočítame, musíme zvoliť v závislosti na vyhľadávacom kľúči a na tom, čo o ňom vieme. Pre náš prípad si definujme hashovacie funkciu ako súčin ASCII hodnôt znakov v reťazci modulo N - tak dostaneme vždy číslo v rozsahu 0 až N - 1 (povedzme, že nedovoľujeme prázdne reťazca). Uveďme si pár príkladov:

"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

Vkladanie a vyhľadávanie

Ukázali sme si, čo to haš tabuľka je. Teraz si ilustrujeme jej princíp - ako inak, než na príklade. Pokúsme sa vložiť do našej tabuľky tri reťazca spomínané vyššie - "hello", "ahoj" a "kockopes". Každý reťazec najskôr odovzdáme hashovacie funkciu a tá nám povie, na ktorý index je umiestniť. Skončíme teda s tabuľkou, ktorá vyzerá takto:

Tabuľka s vloženými položkami

Teraz sa môžeme pokúsiť vyhľadať niektorý reťazec, napr. "Hello". Vyhľadávanie prebieha tak, ako by ste asi čakali - hashovacie funkciu odovzdáme kľúč, ktorý chceme vyhľadať, teda reťazec "hello", a tá nám vráti index, kde položku s týmto kľúčom nájdeme, teda číslo 6. Pozrieme sa teda do tabuľky na index s číslom 6 a položku tu skutočne nájdeme. Ak by sme chceli vyhľadať neeistující reťazec, povedzme "abc", dostali by sme index 4, na ktorom by sme nenašli nič a zistili tak, že položka s kľúčom "abc" sa v tabuľke nenachádza.

Ako vidíme, tabuľka pracuje extrémne rýchlo - pretože nám stačí vždy len zavolať hashovacie funkciu a pristúpiť do poľa nezávisle na veľkosti tabuľky, je časová zložitosť vyhľadanie konštantná! Bohužiaľ ale ako u každej skvelé veci teraz príde na rad neodvratný zádrhel, ktorým sú možné kolízie.

Asi už vás napadlo, čo sa stane, ak hashovacie funkcia umiestni niektorú položku do poľa na index, ktorý už je obsadený. Nie, našťastie nedôjde k zrúteniu počítača. Ak si spomínate, na začiatku sme spomínali, že položky polia sú ukazovatele na lineárny zoznam a preto je možné na jeden index pole umiestniť ľubovoľné množstvo položiek, tzv. Synoným. Ak vložíme do našej tabuľky napr. Reťazec "starwars", dostaneme pre neho hash 0 a výsledok bude vyzerať takto:

konflikt

V podobnom duchu prebieha vyhľadávanie. Nájdenie reťazca "starwars" bude vyzerať tak, že ho odovzdáme hashovacie funkciu, dostaneme index 0, na tento index pristúpime do poľa a teraz musíme lineárne prejsť celý zoznam, ktorý tu nájdeme, a každý reťazec porovnať, ako položku (ne) nájdeme. Tým sa znižuje efektivita tabuľky v najhoršom možnom prípade až na lineárny zložitosť. Takáto situácia nastane, ak nám hashovacie funkcia vracia neustále rovnaký hash - vtedy skončíme v podstate s lineárnym zoznamom:

Najhorší možný prípad

Kvôli tomu je nesmierne dôležité mať dobre navrhnutú hashovacie funkciu vytvárajúce minimum kolízií. To možno však dosiahnuť iba s dobrou znalosťou našich dát.

Existuje ďalšia možnosť riešenia kolízií, ktorá sa nazýva otvorené adresovanie. Tento spôsob nevyužíva lineárnych zoznamov - každá položka pole môže držať klasicky iba jeden záznam dát. Pokiaľ dôjde pri vkladaní ku kolízii, hľadá sa pre vkladaná dáta vopred daným spôsobom ďalšie voľné miesto tak dlho, kým sa nenájde alebo kým sa neprejde celá tabuľka a miesto sa nenájde (vidíme, že kapacita tabuľky je v tomto prípade obmedzená veľkosťou poľa). Keď vieme, ako sme pre položky hľadali voľné miesto, môžeme ich rovnakým spôsobom v prípade kolízie vyhľadávať - vyhľadávame tak dlho, kým záznam nenájdeme, alebo kým neprejdeme celé pole (čo samozrejme opäť znižuje rýchlosť našej tabuľky, takže sa kolíziám musíme stále snažiť zabraňovať) .

Spôsob hľadania voľného miesta možno zvoliť rôzne. Často sa jednoducho postupuje o položku ďalej, než narazíme na voľné miesto - pokiaľ dôjdeme na koniec poľa, ideme znovu od začiatku. Keby sme pre náš príklad použili túto alternatívu, vyzeralo by vkladanie reťazca "starwars" takto:

otvorené adresovanie

Krok posunu môže byť dlhšie ako jedna (v takom prípade by však veľkosť poľa mala byť zvolená ako prvočíslo, aby sa zaručil priechod všetkými položkami, napr. Pri priechode poľa veľkosti 6 s krokom 2 by sme chodili donekonečna len po párnych indexoch). Ďalšie, o niečo modernejšie spôsob je použiť pri kolízii na dáta druhú hashovacie funkciu a jej výstup použiť ako krok posunu, čo opäť opakujeme, kým nenájdeme voľné miesto. Táto technika je výhodnejšie v tom, že dĺžka kroku závisí na dátach a preto dochádza menej k viacnásobným kolíziám (tzn. Kolíziám v druhom a vyššom kroku) - pre rôzne reťazce sa skrátka voľné miesto bude hľadať inde a teda sa pravdepodobne rýchlejšie nájde.

Záverom

Hashovacie tabuľka je veľmi efektívna vyhľadávací metóda, avšak musíme vedieť, kedy a ako ju použiť. Ak vyhľadávame len striedmo a potrebujeme ušetriť pamäť a réžiu, iste zvolíme radšej bežné sekvenčné vyhľadávanie v poli. V iných prípadoch musíme zvážiť alternatívy ako napríklad binárny vyhľadávací strom. Ten je v porovnaní s hashovacie tabuľkou o niečo pomalší, ak uvažujeme ideálny prípad, na druhú stranu pre prípad najhoršie strom víťazí. Hashovacie tabuľka nám navyše neumožňuje vyhľadávať kľúče v určitom intervale alebo len čiastočne špecifikované kľúče - napr. Všetky reťazce s určitou predponou. Dobre môžeme hashovacie tabuľku využiť napríklad na implementáciu tabuľky symbolov v prekladači nejakého jazyka.