Kapitola 4.2.

Vyhľadávanie v rozptyľových tabuľkách s otvoreným rozptyľovaním

 
 
Pri tejto metóde je vždy vkladaný prvok vložený do rozptylovej tabuľky. Uvedieme si 5 konkrétnych metód, ktoré riešia kolízie v tabuľkách tohto typu. Postupne si ich prejdeme od tej najjednoduchšej a najmenej efektívnej až k tým premyslenejším a efektívnejším. Položky tabuliek pri metóde otvoreného rozptyľovania nemusia mať priestor pre uchovanie polohy nasledujúceho prvku v reťazi prvkov. Vyplýva to zo spôsobu, akým sú riešené vzniknuté kolízie. Postup, ktorý je popísaný pre vkladanie prvku je následne sledovaný aj pri jeho vyhľadávaní. Ak pri vyhľadávaní nájdeme prázdnu položku, vyhľadávanie sa končí a hľadaný prvok sa v tabuľke nenachádza. Funkcie používané na rozptyľovanie sú zapísané v tvare h(k) = (f(k) + i*n) mod m, kde
  • h(k) - výsledná rozptylová funkcia pre hodnotu k
  • f(k) - rozptylová funkcia pre hodnotu k
  • i - poradie pokusu pri hľadaní voľnej položky v tabuľke
  • n - ľubovolná premenná, od ktorej závisí posunutie od predchádzajúcej skúšanej položky
  • m - počet položiek v tabuľke
    Viac o problematike otvoreného rozptyľovania a taktiež porovnanie nasledujúcich algoritmov je uvedené v [4].
    •  
    Vstupom pri vyhľadávaní je vždy vyhľadávacia tabuľka s implementovanou rozptylovou funkciou, zadaným počtom položiek a hľadaný prvok. Výstupom algoritmov je potom ukazovateľ na položku, v ktorej sa nachádza hľadaný prvok (nulový ukazovateľ v prípade neúspechu), index do tabuľky prvkov (v prípade neúspechu napr. -1) alebo iba logická premenná, ktorá dáva odpoveď na to, či bolo vyhľadávanie úspešne. Časová zložitosť vyhľadávania závisí pri rozptylových tabuľkách nielen od voľby rozptylovej funkcie, ale najmä od vkladaných prvkov. V nasledujúcich podkapitolách si nebudeme uvádzať predpoklady pre vstupy, výstupy a časovú zložitosť, pretože predchádzajúce tvrdenia platia pre všetkých 5 nasledujúcich metód.

    Zoznam stránok venujúcich sa rozptyľovým tabuľkám s otvoreným rozptyľovaním

    Porovnanie algoritmov pre rozptyľové tabuľky

    Trieda použitá na analýzu a testovanie vybraných algoritmov

    Ako môžeme vidieť, členskými premennými triedy sú počty pokusov a nájdení. Nás bude predovšetkým zaujímať ich pomer a taktiež čas trvania algoritmu. 
     
//riadok (riadok) rozptylovej tabulky pre otvorene rozptylovanie
class CRiadok_OR {
	int hodnota_;		//hodnota polozky
	bool prazdna_;		//priznak, ci je riadok prazdny
public:
.
.
.
};

//rozptylova tabulka s otvorenym rozptylovanim
class CTabulka_OR : public CRiadok_OR{
	//rozptylova tabulka
	CRiadok_OR tabulka_[POCET_POLOZIEK_V_TABULKE];
	//statisticke premenne na analyzu uspesnosti vkladania prvkov do tabulky
	int p_pokusov_;
	int p_najdeni_;
	//sposob riesenia kolizii
	int SRK_;
public:
.
.
.
};