Pouze tento týden sleva až 80 % na HTML & CSS a JavaScript
80 % bodů zdarma na online výuku díky naší Letní akci!

Lekce 12 - Implementace hash tabulky v jazyce C

V příští lekci, Binární vyhledávací stromy (BST) v jazyce C, si ukážeme použití volně dostupné knihovny GLib a univerzálních kolekcí, které poskytuje.

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

Prémiový článek

Prémiový článek

Na itnetwork.cz se nachází největší a nejucelenější česká databáze s výukovými články, jejímž cílem je umožnit kvalitní vzdělání v oblasti IT úplně každému. Měsíčně zobrazíme k milionu článků a sklidíme desítky děkovných emailů, kde nám sdělujete, že jsme vám pomohli k lepšímu zaměstnání nebo vzdělání.

Ačkoli se snažíme držet většinu obsahu úplně zadarmo, udržovat síť v provozu a aktuální stojí obrovské úsilí. Proto je nějaký obsah, jako cvičení nebo odbornější články, přístupný pouze za body. Nebojte, nestojí to skoro nic :)

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.

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

Koupit články a funkce postupně a po jednom 110 bodů
Koupit všechny aktuálně dostupné články v sekci se všemi funkcemi za exkluzivní cenu 94 bodů
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 13 článkům s kontrolou a certifikací a ještě navíc ušetříš 42 Kč. Nabídka je omezená pouze pro první články z kurzu a obsahuje exkluzivní slevu 15%.
94 bodů získáš za přidání svého článku na síť nebo odpovídá 275 Kč 234 Kč

Pozor, pokud si koupíš pouze tento článek, ztratíš nárok na speciální slevu 15% na balíček všech článků.

Pro přístup k článku potřebuješ 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č

Koupí článku k němu získáš neomezený přístup a to napořád. Posuneš své znalosti zas kousek dopředu a zároveň nám pomůžeš udržovat celý projekt při životě a pomáhat vám tak k lepší budoucnosti.

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

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

Dobít body můžeš okamžitě např.:

Kartou SMS Převodem
Kartou SMS Převodem
Článek pro vás napsal Daniel Martinko
Avatar
Aktivity (2)