Grafy a tabuľky

Priemerné počty porovnaní vybraných implementácií

//najdenie zadanej hodnoty "hodnota" v rozptylovej tabulke s otvorenym rozptylovanim 
//funkcia vracia index polozky v ktorej bola hodnota najdena (v pripade neuspechu vracia -1)
int CTabulka_OR::najdi(int hodnota) {
	int pokus=0;
	while (++p_pokusov_ && pokus < POCET_POLOZIEK_V_TABULKE) {
		int riadok = funkcia_1(hodnota, pokus);
		if (tabulka_[riadok].prazdna()) return -1;
		else if (tabulka_[riadok].hodnota()==hodnota) {
			p_vlozeni_++;
			return riadok;
		}
		else pokus++;
	}
	return -1;
}

//volanie funkcie na zaklade zadaneho sposobu riesenia kolizii (uchovavaneho v clenskej
//premennej SRK_), ktora vypocita na zaklade zadanej vkladanej hodnoty "hodnota" a
//poctu predchadzajucich neuspesnych pokusov "pokus", kam bude zadana hodnota vlozena
//funkcia vracia index polozky, do ktorej ma byt zadana hodnota ulozena
int CTabulka_OR::funkcia_1(int hodnota, int pokus) {
	switch (SRK_) {
		case 1 :	return linear_probing(hodnota, pokus);
		case 2 :	return displaced_linear_probing(hodnota, pokus);
		case 3 :	return secondary_clustering(hodnota, pokus);
		case 4 :	return quadratic_residue(hodnota, pokus);
		case 5 :	return double_hashing(hodnota, pokus);
	}
}

//vypocitanie polozky do ktorej bude zadana hodnota "hodnota" 
//vlozena metodou quadratic residue vzhladom na predchadzajuce
//mnozstvo neuspesnych pokusov "pokus" vlozenia tohto prvku
//a pocet riadkov "p_riadkov" v rozptylovej tabulke
//funkcia vracia index polozky do ktorej ma byt zadana hodnota vlozena
int quadratic_residue(int hodnota, int pokus, int p_riadkov) {
	int riadok;
	if (pokus==0) riadok = hodnota % p_riadkov;
	else {
		int odskok = (pokus + 1) / 2;
		if (pokus%2==0) {
			riadok = (hodnota - odskok*odskok) % p_riadkov;
			while (riadok < 0) riadok+=p_riadkov;
		}
		else riadok = (hodnota + odskok*odskok) % p_riadkov;
	}
	return riadok;

}

Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola