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