Algoritmy pre rozptyľové tabuľky s otvoreným rozptyľovaním
|
|
Rozptyľová funkcia displaced linear probing
|
Popis |
|
Druhá metóda pracuje podobne ako prvá. Pri kolízii sa však nepozerá na obsadenosť nasledujúcej položky, ale na obsadenie položky posunutej o nejakú konštantu inú ako 1. Takto sa netvoria súvislé zaplnené množiny položiek v tabuľke. Keď si ale uvedomíme, že takéto množiny ďalej vznikajú, iba ich nevidíme ako súvislé, určite prídeme na to, že treba hľadať iné, optimálnejšie riešenie.
|
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*5) mod 13
2, 7, 12, 4, 9, 1, 6, 11, 3, 8, 0, 5, 10, 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 |
|
|
