Kapitola 4.

Rozptylová tabuľka je abstraktná dátová štruktúra. Vyhľadávanie v rozptylových tabuľkách nie je v skutočnosti čisto problémom vyhľadávacím. Keďže pozícia, kam bude umiestnený prvok vkladaný do takejto tabuľky je vypočítaná už pri vkladaní, je aj pri vyhľadávaní potrebné použiť rovnaké pravidlo pre nájdenie tohto prvku. Preto sa aj my v tejto kapitole budeme zaoberať rozptylovými funkciami. Rozptylové funkcie sú vlastne pravidlá pre vkladanie prvkov do tabuľky a určujú adresu (pozíciu, položku, číslo riadku v tabuľke), kam bude prvok vložený. Ak je pozícia, ktorú prvku priradila rozptylová funkcia prázdna, potom je prvok vložený na toto miesto. V opačnom prípade nastáva kolízia a miesto, kam treba prvok vložiť je určené iným spôsobom. Poznáme dva základné typy rozptylových tabuliek. Tabuľky využívajúce zreťazené rozptyľovanie a tabuľky s otvoreným rozptyľovaním.

Vyhľadávanie prebieha nasledujúcim spôsobom. Vypočítame pomocou rozptylovej funkcie pozíciu, kde mal byť prvok vložený. Ak sa tam prvok nachádza, môžeme vyhľadávanie ukončiť. Ak sa tam hľadaný prvok nenachádza musíme zopakovať postup, ktorý sme robili aj pri vkladaní a získať tak ďalšie možné pozície, kam mohol byť prvok vložený. Keďže výber pozície vloženia prvku podlieha presným pravidlám, rekonštrukciou týchto pravidiel určite získame pozíciu, kam sme prvok nakoniec vložili. Ak nebol prvok do tabuľky vložený, nájdeme počas vyhľadávania prázdnu pozíciu v tabuľke.

Keďže pre každý druh tabuľky bola vytvorená samostatná trieda, nebude tu uvedená ich implementácia. Tú môžete nájsť priamo na stránke porovnaní konkrétneho algoritmu pri tabuľke s počtami rôznych štatistických premenných alebo pre tabuľky používajúce otvorené rozptyľovanie na úvodnej stránke tejto podkapitoly. V každom prípade nás bude ale najviac zaujímať počet pokusov pred nájdením hľadanej hodnoty, priemerný počet týchto pokusov na jedno nájdenie zadanej hodnoty a čas vyhľadávania. Algoritmy nebudú medzi sebou porovnávané na základe nameraných hodnôt priebežne, ale vždy až na koniec kapitoli.