Aktuálně: Postihly zákazy tvou profesi? Poptávka po ajťácích prudce roste, využij slevové akce 30% výuky zdarma!
Hledáme fulltime PHP programátora do ITnetwork týmu - 100% homeoffice, 100% časově flexibilní #bezdeadlinu Mám zájem!

Lekce 13 - Implementace hash tabulky v jazyce C

V minulé lekci, Implementace vektoru v jazyce C, jsme implementovali kolekci vektor, která funguje jako pole, ale není velikostně omezena.

Pokud si vezmeme reálný nesetříděný telefonní seznam, který má miliony položek, tak přidávání nových položek je velmi rychlé. Problém je ovšem efektivní vyhledávání.

V předchozích lekcích jsme měli implementovanou funkci search_at_name(), která nám vrátila index na hledanou položku tak, že procházela celý seznam od začátku až po žádanou položku. Sice jsme vyhledávání částečně zefektivnili seřazením seznamu podle abecedy, můžeme ovšem stále jen prohledávat seznam z jednoho konce na druhý. Při milionech položek je to časově náročné.

Pokud chceme vyhledávání urychlit, tak musíme změnit nejen algoritmus, ale i datovou strukturu, ve které je telefonní seznam uložen.

Struktura seznamů od a do z

Zkusme rozdělit seznam na části a tyto zpracovávat. Například bychom mohli vytvořit tolik seznamů, kolik je písmen abecedy a přidělovat položky do seznamů podle prvního znaku jména. Takto jsou provedeny telefonní seznamy v tiskové formě nebo i registry slov v knihách odborné literatury.

Hashovací tabulka

Datové struktuře, kde podle tzv. klíče položky, zde počátečního písmena, získáme index na místo, kde je položka uložena, říkáme hashovací tabulka a můžete si o ní přečíst obecně více na zmíněném odkazu. My se zde zaměříme zejména na implementační stránku v jazyce C.

Předpokládejme, že všechna jména v telefonním seznamu obsahují


 

...konec náhledu článku...
Pokračuj dál

Znalosti v hodnotě stovek tisíc získáš za pár korun

Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.

Omezená nabídka: Nauč se vše a ušetři

Koupit lekce a funkce postupně a po jednom 150 bodů
Koupit všechny aktuálně dostupné lekce s funkcí odevzdávání úloh za exkluzivní cenu 128 bodů (318 Kč)
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 17 lekcím s kontrolou a certifikací a ještě navíc ušetříš 57 Kč. Nabídka je omezená pouze pro první lekce z kurzu a obsahuje exkluzivní slevu 15%.
128 bodů získáš za přidání svého článku na síť nebo odpovídá 374 Kč 318 Kč

Pozor, pokud si koupíš pouze tuto lekci, ztratíš nárok na speciální slevu 15% na balíček všech lekcí.

Koupit jen lekci 10 bodů
Na svém účtu máš aktuálně 0 bodů
10 bodů získáš za přidání svého článku na síť nebo odpovídá 25 Kč

Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.

Co od nás v dalších lekcích dostaneš?
  • Neomezený a trvalý přístup k jednotlivým lekcím.
  • Kvalitní znalosti v oblasti IT.
  • Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.

Popis článku

Požadovaný článek má následující obsah:

Zjisti, jak v C implementovat vyhledávání v seznamech podle hash klíče a zefektivnit jej. Uvidíš, že generování hash klíče ovlivňuje efektivitu.

Body získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.

Článek pro vás napsal Daniel Martinko
Avatar
Aktivity (3)