Algoritmy pre rozptyľové tabuľky s otvoreným rozptyľovaním
|
|
Rozptyľová funkcia linear probing
|
Popis |
|
Pri kolízii pri tejto metóde jednoducho prehľadávame nasledujúce položky tabuľky a do prvej voľnej položky potom vkladaný prvok umiestnime. Pri vyhľadávaní potom skontrolujeme pozíciu vypočítanú rozptylovou funkciou a ak sa na nej hľadaný prvok nenachádza, prehľadávame nasledujúce položky v tabuľke. Ak nájdeme hľadaný prvok, potom algoritmus skončí úspechom. Ak ale pri prehľadávaní narazíme na prázdnu položku v tabuľke, vieme s určitosťou povedať, že sa v tabuľke hľadaná hodnota nenachádza.
Pri tejto metóde často dochádza k javu nazvanému primary clustering. Je to jav, pri ktorom sa vytvára veľká množina po sebe idúcich obsadených položiek v tabuľke. Keď veľa prvkom priradí rozptylová funkcia rovnakú položku v tabuľke, začne sa za touto položkou tvoriť množina obsadených položiek. Ak potom rozptylová funkcia vypočíta nejakému prvku adresu do tejto množiny, vloží sa tento prvok za koniec tejto množiny a takto sa táto ďalej zväčšuje a znižuje tak efektivitu ako vkladania, tak aj neskoršieho vyhľadávania.
|
Vstupy algoritmu |
|
Vstupmi sú rozptyľová tabuľka so zadaným počtom riadkov a vyhľadávaná hodnota v tabuľke.
|
Príklad rozptylovej funkcie a sekvencia skúšaných položiek |
|
h(k) = (f(k) + i) mod 13
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 1, 2, ...
|
Výstupy algoritmu |
|
V prípade úspešného vyhľadávania je výstupom index riadku v tabuľke, kde bola vyhľadávaná hodnota nájdená. V prípade že pri hľadaní nájdeme prázdnu položku alebo počet vykonaných pokusov je rovný veľkosti tabuľky, algoritmus sa končí neúspechom a návratová hodnota je -1.
|
Vývojový diagram |
 |
Implementácia |
| | //najdenie zadanej hodnoty "hodnota" v rozptylovej tabulke "tabulka"
//s otvorenym rozptylovanim s poctom riadkov "p_riadkov"
//funkcia vracia index polozky v ktorej bola hodnota najdena (v pripade neuspechu vracia -1)
int najdi_OR(Criadok_OR* tabulka, int p_riadkov, int hodnota, int sposob) {
int pokus=0;
while (pokus < p_riadkov) {
int riadok = funkcia_OR(p_riadkov, hodnota, pokus, sposob);
if (tabulka[riadok].prazdna()) return -1;
else if (tabulka[riadok].hodnota()==hodnota) return riadok;
else pokus++;
}
return -1;
} |
| Úplná implementácia |
Vizualizácie |
| Príklad úspechu |
|
| Príklad neúspechu |
|
|
