Algoritmy pre rozptyľové tabuľky s otvoreným rozptyľovaním
|
|
Rozptyľová funkcia quadratic residue
|
Popis |
|
Ďalší algoritmus sa snaží zamedziť javu primary clustering iným spôsobom. Je to voľbou inej sekvencie skúšania položiek. Od prvej skúšanej položky potom ďalšie kvadraticky rozmieta do oboch smerov. Najprv vyskúša položku o 1^2 vpred, potom o 1^2 vzad, potom o 2^2 vpred, 2^2 vzad, potom o 3^2 vpred a tak ďalej.
|
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) mod 23
h(k) = [f(k) + 1^2] mod 23
h(k) = [f(k) - 1^2] mod 23
h(k) = [f(k) + 2^2] mod 23
h(k) = [f(k) - 2^2] mod 23
...
2, 3, 1, 6, 21, 11, 16, 4, 0, 15, 12, 5, 22, 20, ...
|
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 |
|
|
