Laboratorio nº3: hashing, exploracion lineal y cuadratica

LABORATORIO Nº3: HASHING, EXPLORACION LINEAL Y CUADRATICA

FELIX DIAZ GALVAN

Trabajo válido para la asignatura ESTRCUTURA DE DATOS 2, presentado al ING LUCY GARCIA

UNIVERIDAD DEL NORTE
MAYODE 2009, BARRANQUILLA

1. ALGORITMOS:

2.1 EXPLORACION LINEAL:
public int Busqueda_ExploracionLineal(int k){ Recibe como parámetro una llave a buscar k
intcont=1,dir=k%101,j; dir recibe la direccion para la llave k, a través de la función Hash mod n
if(v.get(dir)==null || Integer.parseInt(v.get(dir).toString())==k){
return 1; Si en la direcciónobtenida esta vacia o si la encontro
}else{
j=(dir+1)%101;
while( v.get(j)!=null && Integer.parseInt(v.get(j).toString())!=k && dir!=j){
cont++;j=(j+1)%101; Va cambiado la dirección de uno en uno;
}
}
return cont; Retorna el número de veces que indago por la clave
}

2.2 EXPLORACIONCUADRATICA:
public int Busqueda_ExploracionCuadratica(int k){ Recibe como parámetro una llave a buscar k
int cont=1,dir=k%101,j,col; dir recibe la direccion para la llave k, a travésde la función Hash mod n
if(v.get(dir)==null || Integer.parseInt(v.get(dir).toString())==k){
return 1;
}else{
col=1;
j=(dir+col*col)%101;while( v.get(j)!=null && Integer.parseInt(v.get(j).toString())!=k && dir!=j){
cont++;
col++; Va aumentando el numero de colisionesj=(dir+col*col)%101;
}
}
return cont;

}
}

2. RESULTADOS
2.1 Salida del programa
1 Intento:
BUSQUEDA LINEAL:
Promedio para 30% = 1.100000023841858Promedio para 50% = 1.899999976158142
Promedio para 70% = 3.4000000953674316
Promedio para 90% = 13.100000381469727
BUSQUEDA CUADRATICA:
Promedio para 30% = 1.100000023841858
Promedio para 50%...