Cómo implementar correctamente el método hashCode en Java
Igualdad y códigos hash
La equivalencia es en un sentido general, mientras que los códigos hash son más técnicos. Si tenemos dificultades para comprender el código hash, entonces podemos decir que el código hash es solo un detalle de implementación y, por lo tanto, mejora el rendimiento.
La mayoría de las estructuras de datos utilizan métodos equivalentes para determinar si contienen un elemento, por ejemplo:
List
booleano contiene = list.contains("b");
La variable contiene es verdadera porque aunque "b" no es la misma instancia (excepto ignorando cadenas) , pero son iguales.
Comparar cada elemento en la instancia y luego asignar el resultado de la comparación a contiene sería un desperdicio, aunque toda la estructura de datos de la clase esté optimizada para el rendimiento.
En lugar de comparar cada elemento contenido en una instancia, se utiliza un atajo (reduce la posible igualdad de instancias). La comparación de accesos directos solo necesita comparar el siguiente contenido:
La comparación de accesos directos compara el código hash, y el código hash puede reemplazar una instancia con un valor entero. Las instancias con el mismo código hash no son necesariamente iguales, pero las instancias iguales deben tener el mismo valor hash. (Estas estructuras de datos suelen recibir nombres mediante esta técnica y pueden identificarse por sus valores hash, de los cuales HashMap es uno de los representantes más conocidos.
Así es como suelen funcionar
Cuando se agrega un elemento, su código hash se usará para calcular el índice en la matriz interna (llamada "depósito")
Si es así, los elementos desiguales tienen los mismos códigos hash, entonces son eventualmente se colocan en el mismo depósito y se unen, por ejemplo, se agregan a una lista.
Cuando la instancia ingresa a la operación de inclusión, su código hash se usa en el cálculo del valor del depósito (valor de índice), la instancia será. se compara solo si hay un elemento en el valor de índice correspondiente
Por lo tanto, es equivalente a definir el hashCode en la clase de objeto
Pensamientos sobre hashCode
. Si hashCode se usa como atajo para determinar la igualdad, entonces solo hay una cosa que debería importarnos: los objetos iguales deben tener el mismo hashCode, es por eso que si anulamos el método de igualdad, ¡debes crear una implementación de hashCode que coincida! >
De lo contrario, es posible que objetos iguales no tengan el mismo código hash, porque llamarán a la implementación predeterminada del objeto
directrices de HashCode
Citado de la documentación oficial
* Al llamar al mismo objeto en una aplicación Java en ejecución, el método hashCode siempre debe devolver el mismo número entero. No es necesario que el número entero sea coherente en todas las aplicaciones Java.
* Según el método de comparación igual a (Objeto), dos llamadas de objeto al método hashCode deben producir el mismo resultado si los dos objetos son iguales
* Comparar según el método igual a (Objeto). Si los dos objetos no son iguales, los resultados de llamar al método hashCode en los dos objetos no son necesariamente enteros diferentes. Sin embargo, los programadores deben tener en cuenta que producir resultados enteros diferentes para objetos desiguales probablemente mejore el rendimiento de la tabla hash. /p>
El primer punto refleja la propiedad de consistencia de la igualdad, y el segundo punto es el requisito que hicimos anteriormente. Tres puntos ilustran un detalle importante que discutiremos más adelante.
Implementación de HashCode
La siguiente es una implementación muy simple de Person.hashCode
@Override
public int hashCode() {
return Objects.hash(firstName, lastName);
}
La persona se calcula combinando varios campos para calcular el código hash. Todos los cálculos se realizan a través de la función hash del objeto.
Seleccionar campos
¿Pero qué campos son relevantes? El requisito nos ayudará a responder esta pregunta: si los objetos iguales deben tener el mismo código hash, entonces el cálculo del código hash no debe incluir ningún campo que no se utilice en la verificación de igualdad. (De lo contrario, dos objetos con campos diferentes pueden seguir siendo iguales, pero no tendrán el mismo código hash).
Por lo tanto, el subconjunto de campos utilizados para los campos del grupo hash debe ser igual. Se utilizan los mismos campos de forma predeterminada, pero hay algunos detalles a considerar.
Coherencia
El primero es el requisito de coherencia. Esto debería ser bastante estricto. Aunque si algunos campos cambian, el código hash correspondiente también cambiará (lo cual es inevitable para las clases mutables), la estructura de datos hash no está diseñada para esta situación.
Como se mencionó anteriormente, el código hash se utiliza para determinar el depósito de elementos. Sin embargo, si los campos relacionados con el hash cambian, el código hash no se vuelve a calcular y la matriz interna no se actualiza.
Esto significa que las consultas posteriores para objetos equivalentes, incluso las consultas para la misma instancia, fallarán porque la estructura de datos calculará el código hash actual que es diferente del código hash calculado por la instancia almacenada anterior. y en el cubo equivocado.
Conclusión: ¡Es mejor no utilizar campos variables para calcular códigos hash!
Rendimiento
El código hash termina calculándose con tanta frecuencia como es probable que se llame la ecuación, por lo que será una parte crítica del impacto en el rendimiento, por lo que es razonable Considere esta parte de la actuación. Y las ventajas de optimizar ecuaciones son mayores que las de las ecuaciones.
A menos que se utilice un algoritmo muy complejo o haya una gran cantidad de campos involucrados, el costo computacional de calcular un código hash es insignificante e inevitable. Sin embargo, también debemos considerar si es necesario incluir todos los campos para el cálculo. Hay que estar especialmente atento a las reuniones. Por ejemplo, las listas y conjuntos incluyen todos los elementos del conjunto al calcular el código hash. La necesidad de llamarlos debe analizarse caso por caso.
Si el rendimiento es crítico, usar Objects.hash (debido a la necesidad de crear una matriz para los varargs) puede no ser la mejor opción. Pero las reglas generales de optimización también se aplican: no utilice un algoritmo de código hash universal demasiado pronto y solo abandone el conjunto si el análisis de optimización muestra mejoras potenciales.
Colisión
Céntrese siempre en el rendimiento, entonces, ¿qué tal esta implementación?
@Override
public int hashCode() {
return 0;
}
Debe ser muy rapido rapido. Los objetos equivalentes tendrán el mismo código hash. Además, ¡no hay campos mutables!
Pero ¿qué pasa con el cubo del que hablamos antes? ¡De esta manera todas las instancias tendrán el mismo depósito! Esto dará como resultado una lista vinculada que contendrá todos los elementos, lo que dará como resultado un rendimiento extremadamente pobre. Cada llamada a contiene activa un escaneo lineal de toda la lista.
¡Esperamos que cuantos menos elementos haya en el mismo depósito de datos, mejor! Incluso para objetos muy similares, los algoritmos que devuelven códigos hash variables son un buen comienzo.
La forma de lograr lo anterior depende en parte de los campos elegidos; cuantos más detalles se incluyan en el cálculo, más probabilidades tendremos de obtener códigos hash diferentes. Tenga en cuenta: esto es exactamente lo contrario de lo que entendemos por rendimiento. Por lo tanto, es interesante observar que usar demasiados o muy pocos campos puede provocar un rendimiento deficiente.
Otra forma de evitar colisiones es utilizar el algoritmo que realmente calcula los hashes.
Calcular Hash
La forma más sencilla de calcular el hash de un campo es llamar a hashCode directamente, lo que se hará automáticamente si se usa en combinación. Un algoritmo común consiste en realizar primero operaciones de multiplicación repetidas con cualquier número de valores (generalmente tipos de datos primitivos) antes de agregarlos al código hash del campo
int prime = 31;
p>int resultado = 1;
resultado = principal * resultado + ((firstName == null) ?0 : firstName.hashCode());
resultado = principal * resultado + ((lastName == null) ?0 : lastName.hashCode());
devuelve resultado;
Esto puede causar desbordamiento, pero no es un gran problema porque no hay Java Se genera una excepción.
Tenga en cuenta que incluso los algoritmos hash muy buenos pueden provocar colisiones frecuentes debido a patrones específicos en los datos de entrada. Como ejemplo simple, digamos que vamos a calcular el hash de un punto sumando sus coordenadas xey. Cuando tratamos con puntos en la línea f (x) = -x, todos los puntos en la línea satisfacen: x + y == 0, por lo que habrá muchas colisiones.
Sin embargo: podemos usar un algoritmo general y solo necesitamos modificar el algoritmo hash si el análisis muestra que el algoritmo hash es incorrecto.
Resumen
Aprendimos que el propósito de calcular códigos hash es comprimir valores enteros iguales: los objetos iguales deben tener el mismo código hash y, por razones de rendimiento: el máximo Para que como El menor número posible de objetos desiguales comparten el mismo código hash.
Esto significa que si se anula el método equivalente, el método hashCode también debe anularse
Cuando se usa el mismo campo que se usa en el equivalente (o al implementar hashCode
como un subconjunto de campos), es mejor no incluir campos mutables.
No consideres llamar a hashCode para una colección.
Si no hay un patrón de entrada especial, intenta usar un algoritmo hash general.
Recuerda que hashCode está implementado. así que no desperdicies demasiada energía a menos que tu análisis muestre que es necesario.