Hoy quiero hablaros de dos métodos que pasan desapercibidos la mayoría de las ocasiones, pero que pueden optimizar nuestras colecciones y mapas basadas en Hash, como HashMap, HashSet o HashTable de forma sorprendente.
Estos objetos (HashMap, HashSet, etc...) se basan en el hash para almacenar la información, y en equals para determinar colisiones (dos claves iguales), de manera que si necesitamos sobreescribir estos métodos en nuestras clases y usamos éstas como clave de alguno de estos objetos, debemos ser cuidadosos con la estrategia y el diseño que elegimos, ya que veremos con un ejemplo que aún cumpliendo el contrato de 'Object' en cuanto a equals y hashCode, podemos empobrecer el rendimineto de nuestro sistema enormemente.
Veamos un poco de teoria, según la API de java (http://docs.oracle.com/javase/6/docsapi/index.html), el método equals debe ser:
- Reflexivo: Para cualquier valor de x que no son nulos de referencia, x.equals (x) debe devolver true.
- Simétrico: Para cualquier no nulo de referencia, los valores x e y, x.equals (y) debe devolver true si y sólo si y.Equals (x) devuelve true.
- Transitivo: Para los valores de referencia que no son nulos x, y, z, si x.equals (y) devuelve true y y.Equals (z) devuelve true, x.Equals (z) debe devolver true.
- Consistente: Para cualquier no nulo de referencia los valores x e y, varias invocaciones de x.Equals (y) siempre devuelven verdadero o falso de vuelta constantemente, siempre que no es igual a la información utilizada en las comparaciones de los objetos se ha modificado.
- Para cualquier valor de x que no son nulos de referencia, x.equals (null) debe devolver false.
El método hashCode debe cumplir:
- Cada vez que se invoca en el mismo objeto más de una vez durante una ejecución de una aplicación Java, el método hashCode siempre debe devolver el mismo entero, siempre que no es igual a la información utilizada en las comparaciones sobre el objeto se ha modificado. Este entero no tiene por qué mantener la consistencia de una ejecución de una aplicación a otra ejecución de la misma aplicación.
- Si dos objetos son iguales de acuerdo con el método equals (Object), y luego llamar al método hashCode de cada uno de los dos objetos tiene que producir el resultado mismo entero.
- Si dos objetos NO son iguales de acuerdo al método 'equals' (java.lang.Object), entonces la llamada al método hashCode de cada uno de los dos objetos que puede producir diferentes resultados enteros. Sin embargo, el programador debe ser consciente de que la producción de distintos resultados desiguales para los objetos enteros puede mejorar el rendimiento de tablas hash.
La propia API nos está indicando que se puede mejorar las hash, pero, veamos un ejemplo. Imaginemos esta clase:
public class MiObjeto {
int x;
int y;
public MiObjeto(int i) {
x = i;
y = i;
}
@Override
public int hashCode(){
return 0;
}
@Override
public boolean equals(Object o){
if (o instanceof MiObjeto) {
MiObjeto aux = (MiObjeto) o;
if (this.x == aux.x && this.y == aux.y){
return true;
}
}
return false;
}
}
Esta clase define objetos del tipo 'MiObjeto', tiene dos miembros enteros (x e y) y un constructor publico que recibe un entero y los asigna tanto a x como a y. Se ha redefinido el método equals y el método hashCode de forma que:
Dos objetos serán iguales si sus miembro x e y son iguales. El hashCode es 0.
¿Cumplimos el contrato de hashCode?
Si, si dos objetos son iguales su hashCode será igual, si son distintos será igual también (el contrato dice que si dos objetos son distintos segun equals, su hashCode puede ser igual o no). Luego cumplimos el contrato.
Ahora imaginemos esta clase:
public class HashTest {
public static void main (String[] args) {
HashMap<MiObjeto, MiObjeto> hm = new HashMap<MiObjeto, MiObjeto>();
long ini = System.currentTimeMillis();
for (int i=0; i<100000; i++) {
MiObjeto a = new MiObjeto(i);
MiObjeto b = new MiObjeto(i+1);
hm.put(a, b);
}
System.out.println(hm.size());
long fin = System.currentTimeMillis();
System.out.println("tiempo: " + (fin-ini));
}
}
Creamos en el main 100.000 objetos 'MiObjeto' y los usamos tanto como clave como valor dentro de un HashMap, cada objeto tendrá un valor en x e y distintos para evitar colisiones. Medimos el tiempo que tarda en almacenar estos objetos.
El resultado de esta ejecucion es:
100000
tiempo: 42754
Como vemos, ha empleado en ejecutar el bucle 42,75 segundos.
Vamos a realizar un pequeño ajuste, y a lanzar otra vez el mismo programa, vamos a cambiar el método hashCode para que quede de esta forma:
@Override
public int hashCode(){
return x;
}
Seguimos cumpliendo el contrato con esta implementación, ejecutamos:
100000
time: 31
Ahora, nuestro programa ha tardado 31 milisegundos en hacer lo mismo. Una mejora de rendimiento del 137.916%... y no, no hablamos de astronomía :). Ha tardado 1379 veces menos.
¿A que se debe esto?
Los objetos basados en Hash determinan, a partir de hashCode, el 'bucket' donde almacenar la pareja clave-valor. Dentro de cada bucket en el caso de HashMap hay una linked-list que va almacenando los objetos, si el hashcode es siempre igual, o cambia poco, el bucket será siempre o casi siempre el mismo por lo que las operaciones de almacenamiento cada vez serán mas pesadas.
Lo visto demuestra que debemos tender a elegir una implementación de hashCode, junto con equals, que repitan valores lo menos posible.
Como aporte, la implementación por defecto heredada de hashCode, devuelve la representación numérica del puntero del objeto en memoria.
Hasta la próxima!! :)
