Hashing Abierto
F u n cion es d e h ash in g p ara strin gs
static public int hash(String x,int y){...}
1 . S u m ar rep resen tacion es in tern as d e caracteres
int s=0;
for(int i=0; i<x.length(); ++i)
s += x.charAt(i);
return s % y;
2 . E valu ar p olin om io, u san d o caracteres com o coeficien tes
int s=0, p=1;
for(int i=x.length()-1; i>=0; --i){
s+=x.charAt(i)*p; p*=128;
}
return s % y;
3 . C on fu n ción p red efin id a d e clase S trin g
return x.hashCode() % y;
E jem p los (y= 100)
función
suma
polinomio
hashCode
rosa
37
69
53
Rosa
5
5
57
rosaura
65
29
23
roma
31
1
31
amor
31
22
83
B ú sq u ed a p or H ash in g : para arreglos no ordenados “grandes”
(“una com paración”)
Id ea : aplicar una función al argum ento de búsqueda que
produzca entero entre 0 y n-1
 L a función, f(x)  [0,n[, debe diseñarse de m odo que
distribuya sus argum entos en distintas posiciones
 S i se producen “colisiones”, es decir, si f(x)= f(y), entonces
una solución es ubicar x en la próxim a posición disponible
(rehashing lineal)
 E s im portante que el arreglo tenga m ás elem entos que los
valores posibles, y de preferencia que sea un N º prim o
int indice(String x,String[]y,int n){
int i = hash(x,n);
while( y[i] != null ){
if( y[i].equals(x) ) return i;
i = (i + 1) % n;
}
return –1;
}
o
int indice(String x,String[]y,int n){
for(int i=hash(x,n); y[i]!=null; i=(i+1)%n)
if( y[i].equals(x) ) return i;
return –1;
}
¿C on stru cción d el arreglo?
//contar número de elementos
BufferedReader A=new BufferedReader(...);
int n=0;
while(A.readLine()!=null)++n;
//arreglo 10% mas grande (con valores null)
String[]a=new String[(int)(1.1*n+0.9)];
//llenar arreglo usando función de hashing
A=new BufferedReader(...);
for(int j=1; j<=n; ++j){
String linea = A.readLine();
int i=hash(linea, a.length);
while(a[i]!=null && !a[i].equals(linea))
i=(i+1)%a.length;
a[i]=linea;
}
Descargar

Hashing Abierto