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