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í.

13. diel - Implementácia hash tabuľky v jazyku C

V minulej lekcii, Implementácia vektora v jazyku C , sme implementovali kolekciu vektor, ktorá funguje ako pole, ale nie je veľkostne obmedzená.

Ak si vezmeme reálny Hlavička telefónny zoznam, ktorý má milióny položiek, tak pridávanie nových položiek je veľmi rýchle. Problém je však efektívne vyhľadávanie.

V predchádzajúcich lekciách sme mali implementovanú funkciu search_at_name(), ktorá nám vrátila index na hľadanú položku tak, že prechádzala celý zoznam od začiatku až po žiadanú položku. Síce sme vyhľadávanie čiastočne zefektívnili zoradením zoznamu podľa abecedy, môžeme však stále len prehľadávať zoznam z jedného konca na druhý. Pri miliónoch položiek je to časovo náročné.

Ak chceme vyhľadávanie urýchliť, tak musíme zmeniť nielen algoritmus, ale aj dátovú štruktúru, v ktorej je telefónny zoznam uložený.

Štruktúra zoznamov od a do z

Skúsme rozdeliť zoznam na časti a tieto spracovávať. Napríklad by sme mohli vytvoriť toľko zoznamov, koľko je písmen abecedy a prideľovať položky do zoznamov podľa prvého znaku mena. Takto sú vykonané telefónne zoznamy v tlačovej forme alebo aj registre slov v knihách odbornej literatúry.

Haš tabuľka

Dátové štruktúre, kde podľa tzv. Kľúča položky, tu začiatočného písmena, získame index na miesto, kde je položka uložená, hovoríme hashovacie tabuľka a môžete si o nej prečítať všeobecne viac na spomínanom odkazu. My sa tu zameriame najmä na implementačné stránku v jazyku C.

Predpokladajme, že všetky mená v telefónnom zozname obsahujú


 

...koniec náhľadu článku...
Pokračuj ďalej

Vedomosti v hodnote stoviek tisíc získaš za pár korún

Minul si až sem a to je super! Veríme, že ti prvé lekcie ukázali niečo nového a užitočného.
Chceš v kurze pokračovať? Prejdi do prémiové sekcie.

Kúpiť tento kurz

Kúpiť všetky aktuálne dostupné lekcie s funkciou odovzdávanie úloh iba za 375 kreditov
Aktuálny stav konta 0 kreditov
Kúpou tohoto balíčku získaš prístup ku všetkým 17 článkom (17 lekcií) tohoto kurzu.

Obsah článku spadá pod licenciu Premium, kúpou článku súhlasíš so zmluvnými podmienkami.

Čo od nás v ďalších lekciách dostaneš?
  • Neobmedzený a trvalý prístup k jednotlivým lekciím.
  • Kvalitné znalosti v oblasti IT.
  • Zručnosti, ktoré ti pomôžu získať vysnívanú a dobre platenú prácu.

Popis článku

Požadovaný článok má nasledujúci obsah:

Zisti, ako v C implementovať vyhľadávanie v zoznamoch podľa hash kľúča a zefektívniť ho. Uvidíš, že generovanie hash kľúča ovplyvňuje efektivitu.

Kredity získaš, keď podporíš našu sieť. To môžeš urobiť buď zaslaním symbolickej sumy na podporu prevádzky alebo pridaním obsahu na sieť.

Článok pre vás napísal Daniel Martinko
Avatar
Aktivity