LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> C++ - Hashování

V tomto článku se seznámíme s hashovacími tabulkami, vysvětlíme si, jak fungují, k čemu jsou dobré a kdy je vhodné je využít. Samozřejmě nebude chybět ani ukázka implementace, která bude provedena v jazyce C++. Článek si neklade za cíl vysvětlit, jak přesně fungují některé známé hashovací funkce, úkolem článku je seznámit čtenáře s tím, co to vlastně hashovací funkce je a k čemu se dá použít.

3.12.2010 00:00 | Petr Sklenička | Články autora | přečteno 12823×

Co je to hashovací tabulka

Hashovací tabulka je datová struktura, v níž můžeme velmi rychle vyhledávat. V této tabulce jsou vlastně hashovací klíče spojeny s patřičnými hodnotami. S trochou nadsázky by se o hashovací tabulce dalo hovořit jako o "vylepšeném poli". Máme-li pole, jednotlivé hodnoty jsou spojeny s indexem pole, čili 0n. V poli však nedokážeme předem určit, na kterém indexu je hodnota, kterou hledáme. V hashovací tabulce jsou hodnoty uloženy společně s jim odpovídajícím hashovacím klíčem, který získáme užitím hashovací funkce. Čím lépe je pak tato hashovací funkce navržena, tím lepší bude hashovací tabulka. Hashovací funkce se obvykle použivají pro rychlejší vyhledávání dat v databázích, odhalování duplicitních záznamů v obrovských souborech apodobně.

Asi nejlepším způsobem, jak osvětlit problematiku hashování, je uvedení krátkého příkladu. Mějme množinu nějakých čísel, například čísla 6, 12, 9, 16, 11, 61, 42. Tyto čísla pro nás budou hodnotami, které budeme chtít uložit do hashovací tabulky a následně mezi nimi pak vyhledávat. K tomu, abychom je do tabulky mohli uložit, potřebujeme hashovací funkci - ta nám pro každé číslo vrátí jeho hashovací klíč, který nám pak bude udávat místo v tabulce, kde je číslo uloženo. Navrhněme si zcela banální funkci - pro každé číslo nám vrátí zbytek po dělení číslem 8. Předem podotýkám, že tento příklad slouží pouze pro pochopení, nejedná se o žádnou skvělou hashovací funkci.

Jen pro upřesnění, pokud číslo 6 předáme do naší funkce, hashovací klíč bude 6, neboť 6 / 8 = 0, zb. 6. Pro číslo 12 bude klíč 4, atd. V obyčejném poli pak tedy na index 6 uložíme číslo 6, na index 4 uložíme číslo 12 apod. Kód, jak by to celé mohlo vypadat, je zde:

Naše hashovací tabulka pak vypadá následovně:
Index (Hashovací klíč)Hodnota
016
19
242
311
412
561
66

Chceme-li v této tabulce vyhledávat nějakou hodnotu, stačí zjistit odpovídající hashovací klíč a pak se podívat na patřičný index v poli. Budeme-li tedy zjišťovat, zda je v tabulce číslo 11, zjistíme, že hodnota hashovacího klíče je 3 a číslo 11 tedy může být pouze pod indexem 3, nikde jinde. Podíváme se tedy na index 3 a zjistíme, že číslo 11 v tabulce opravdu je. Stačilo nám jedno porovnání, abychom číslo našli. V kódu lze vyhledávání realizovat takto:

Je jistě vidět, že vyhledávat v hashovací tabulce není nic složitého. Samozřejmě mnohem lepší by bylo si na vyhledávání napsat jednoduchou funkci, která by vracela true nebo false. V této ukázce však šlo pouze o pochopení, jak hashování funguje.

Problémy při hashování

Vraťme se ješte na chvíli k předešlému příkladu. Naše hashovací funkce vracela zbytek po dělení osmi, což znamená, že hashovací klíč byl vždy v intervalu <0, 7>. To může být docela problém, neboť rozsah klíčů není velký a může proto velmi snadno dojít ke kolizi. Kolizí rozumíme to, jestliže dvě hodnoty získají stejný hashovací klíč - například čísla 27 a 11 mají obě hashovací klíč roven 3 (u naší hashovací funkce). To je problém, neboť v našem poli je u hashovacího klíče vždy jen jedno místo. Proto je snad již zcela zřejmé, že předchozí příklad neměl reálné využití. Jak tedy kolize řešit?

Asi nejlepším způsobem by bylo navrhnout hashovací funkci tak, aby každé hodnotě přiřadila různý klíč. Toho by šlo dosáhnout tak, že by se hashovací funkce chovala náhodně. V tom je však skryt další problém. Hashovací funkce musí být navržena tak, aby vždy pro danou hodnotu vypočítala stejný hashovací klíč - proto se hashovací funkce nemůže chovat náhodně. Kolize lze tedy řešit například separátním řetězením.

Separátní řetězení

Princip separátního řetězení je takový, že každé hodnotě hashovacího klíče je přiřazena datová struktura seznam, do kterého se ukládají hodnoty. Jinak řečeno, hodnoty se stejným hashovacím klíčem se ukladájí do stejného seznamu. Tím se však zvyšuje časová složitost vyhledání hodnoty v hashovací tabulce. Časová složitost je úměrná délce seznamu, který je asociován s patřičným hashovacím klíčem. V absolutně nejhorším případě by se mohlo stát, že by se všechny hodnoty hashovaly na stejný hashovací klíč, tudíž by se ukládaly do stejného seznamu. V tomto případě by pak časová složitost na vyhledání hodnoty byla přímo děsivá. Je tedy nutné dobře navrhnout hashovací funkci, aby ke kolizím docházelo co možná nejméně často.

Ukázku, jakým způsobem je možno separátní řetězení naimplementovat, naleznete zde. Je to trochu delší kód, proto jsem ho zde dal ke stažení. Program slouží k uložení různě dlouhých řetězců do hashovací tabulky. Pokud si kód budete chtít vylepšit, můžete si několik řetězců uložit do textového souboru, ty pak v programu načíst a uložit do hashovací tabulky. Pak je můžete zkusit vyhledávat. Udělal jsem hashovací tabulku na 50 hashovacích klíčů, není však problém tuto tabulku zvětšit - stačí v kódu změnit hodnotu konstanty n. Každý prvek hashovací tabulky představuje datovou strukturu seznam, čili při výskytu stejných hashovacích klíčů se data ukládájí do stejného seznamu. Ještě podotýkám, že jsem implementoval pouze metody pro přidávání a hledaní prvků, metoda, která bude prvky mazat, není nikterak složitá.

Známé hashovací funkce

Jistě jste se někdy setkali například s pojmem CRC (Cyclic Redundancy Check, cyklický redundantní součet). Není to nic jiného, než hashovací funkce, která se používá při přenosu nebo při ukládání dat, čili slouží k detekci chyb v datech. To, jak přesně CRC funguje, je myslím zbytečné psát, neboť o tom se určitě najde článků dost. Mezi další hashovací funkce patří například MD-5 nebo SHA-1.

Verze pro tisk

pridej.cz

 

DISKUZE

Hashovaci funkce 7.12.2010 00:03 Aleš Hakl




Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

15.5.2017 23:50 /František Kučera

Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 18. května od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).


Přidat komentář

12.5.2017 16:42 /Honza Javorek
PyCon CZ, česká konference o programovacím jazyce Python, se po dvou úspěšných ročnících v Brně bude letos konat v Praze, a to 8. až 10. června. Na konferenci letos zavítá např. i Armin Ronacher, známý především jako autor frameworku Flask, šablon Jinja2/Twig, a dalších projektů. Těšit se můžete na přednášky o datové analytice, tvorbě webu, testování, tvorbě API, učení a mentorování programování, přednášky o rozvoji komunity, o použití Pythonu ve vědě nebo k ovládání nejrůznějších zařízení (MicroPython). Na vlastní prsty si můžete na workshopech vyzkoušet postavit Pythonem ovládaného robota, naučit se učit šestileté děti programovat, efektivně testovat nebo si v Pythonu pohrát s kartografickým materiálem. Kupujte lístky, dokud jsou.
Přidat komentář

2.5.2017 9:20 /Eva Rázgová
Putovní konference československé Drupal komunity "DrupalCamp Československo" se tentokrát koná 27. 5.2017 na VUT FIT v Brně. Můžete načerpat a vyměnit si zkušenosti z oblasti Drupalu 7 a 8, UX, SEO, managementu týmového vývoje, využití Dockeru pro Drupal a dalších. Vítáni jsou nováčci i experti. Akci pořádají Slovenská Drupal Asociácia a česká Asociace pro Drupal. Registrace na webu .
Přidat komentář

1.5.2017 20:31 /Pavel `Goldenfish' Kysilka
PR: 25.5.2017 proběhne v Praze konference na téma Firemní informační systémy. Hlavními tématy jsou: Informační systémy s vlastní inteligencí, efektivní práce s dokumenty, mobilní přístup k datům nebo využívání cloudu.
Přidat komentář

15.4.2017 15:20 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě IoT a radiokomunikace? Přijď na sraz spolku OpenAlt, který se bude konat ve středu 19. dubna od 18:30 v Šenkovně (Sokolská 60, Praha 2).
Přidat komentář

5.3.2017 19:12 /Redakce Linuxsoft.cz
PR: 23. března proběhne v Praze konferenci na téma Cloud computing v praxi. Hlavními tématy jsou: Nejžhavější trendy v oblasti cloudu a cloudových řešení, Moderní cloudové služby, Infrastruktura současných cloudů, Efektivní využití cloudu, Nástrahy cloudových řešení a jak se jim vyhnout.
Přidat komentář

27.2.2017 22:12 /František Kučera
Pozvánka na 137. sraz OpenAlt – Praha: Tentokrát jsme si pro vás připravili neobvyklou akci. Ve středu 1.3. v 17:30 nás přivítá sdružení CZ.NIC ve svých prostorách v Milešovské ulici číslo 5 na Praze 3, kde si pro nás připravili krátkou prezentaci jejich činnosti. Následně navštívíme jejich datacentrum pod Žižkovskou věží. Provedou nás prostory, které jsou běžnému smrtelníkovi nedostupné!
Po ukončení prohlídky se všchni odebereme do hostince U vodoucha, Jagelonská 21, Praha 3 pochutnat si na některém z vybraných piv či dát si něco na zub. Rezervaci máme od 19:30, heslo je OpenAlt.
Ale pozor! Do prostor datového centra máme omezený přístup, dostane se tam pouze 10 lidí! Takže kdo přijde dříve, ten má přednost, a občanky s sebou! Kdo nebude chtít na prohlídku datového centra, může se pomalu přesunout do hostince U vodoucha a u nepřeberné nabídky piv počkat na ostatní.
Přidat komentář

18.1.2017 0:49 /František Kučera
Členové a příznivci spolku OpenAlt se pravidelně schází v Praze a Brně. Fotky z pražských srazů za uplynulý rok si můžete prohlédnout na stránkách spolku. Příští sraz se koná už 19. ledna – tentokrát je tématem ergonomie ovládání počítače – tzn. klávesnice, myši a další zařízení. Také budete mít příležitost si prohlédnout pražský hackerspace Brmlab.
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

15.6.2017 9:34 / Ondřej Havlas
php,

10.6.2017 10:39 / Temple
sell home for cash

11.5.2017 23:32 / lelo
Re: Problém se správcem balíčků

11.5.2017 5:45 / davd mašek
Re: Problém se správcem balíčků

10.5.2017 22:54 / lelo
Re: Problém se správcem balíčků

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2017) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze