La mejor implementación del método hashCode para una colección
https://stackoverflow.com/questions/113511
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cómo decidimos cuál es la mejor implementación de hashCode() método para una colección (suponiendo que el método igual se haya anulado correctamente)?
Solución
¿La mejor implementación?Ésta es una pregunta difícil porque depende del patrón de uso.
En casi todos los casos se propuso una buena implementación razonable en jose bloch's Java efectivo en el punto 8 (segunda edición).Lo mejor es buscarlo allí porque el autor explica allí por qué el enfoque es bueno.
una versión corta
Crear un
int resulty asignar un distinto de cero valor.Para cada campo
fprobado en elequals()método, calcular un código hashcpor:- Si el campo f es un
boolean:calcular(f ? 0 : 1); - Si el campo f es un
byte,char,shortoint:calcular(int)f; - Si el campo f es un
long:calcular(int)(f ^ (f >>> 32)); - Si el campo f es un
float:calcularFloat.floatToIntBits(f); - Si el campo f es un
double:calcularDouble.doubleToLongBits(f)y manejar el valor de retorno como cada valor largo; - Si el campo f es un objeto:Utilice el resultado de la
hashCode()método o 0 sif == null; - Si el campo f es un formación:ver cada campo como elemento separado y calcular el valor hash en un moda recursiva y combine los valores como se describe a continuación.
- Si el campo f es un
Combina el valor hash
cconresult:result = 37 * result + cDevolver
result
Esto debería dar como resultado una distribución adecuada de los valores hash para la mayoría de situaciones de uso.
Otros consejos
Si está satisfecho con la implementación efectiva de Java recomendada por dmeister, puede usar una llamada a la biblioteca en lugar de implementar la suya propia:
@Override
public int hashCode() {
return Objects.hashCode(this.firstName, this.lastName);
}
Esto requiere guayaba (com.google.common.base.Objects.hashCode) o la biblioteca estándar en Java 7 (java.util.Objects.hash) pero funciona de la misma manera.
Es mejor utilizar la funcionalidad proporcionada por Eclipse, que hace un trabajo bastante bueno y puede dedicar sus esfuerzos y energía a desarrollar la lógica empresarial.
Aunque esto está relacionado con Android documentación (Wayback Machine) y Mi propio código en Github, funcionará para Java en general.Mi respuesta es una extensión de La respuesta de dmeister con solo código que es mucho más fácil de leer y comprender.
@Override
public int hashCode() {
// Start with a non-zero constant. Prime is preferred
int result = 17;
// Include a hash for each field.
// Primatives
result = 31 * result + (booleanField ? 1 : 0); // 1 bit » 32-bit
result = 31 * result + byteField; // 8 bits » 32-bit
result = 31 * result + charField; // 16 bits » 32-bit
result = 31 * result + shortField; // 16 bits » 32-bit
result = 31 * result + intField; // 32 bits » 32-bit
result = 31 * result + (int)(longField ^ (longField >>> 32)); // 64 bits » 32-bit
result = 31 * result + Float.floatToIntBits(floatField); // 32 bits » 32-bit
long doubleFieldBits = Double.doubleToLongBits(doubleField); // 64 bits (double) » 64-bit (long) » 32-bit (int)
result = 31 * result + (int)(doubleFieldBits ^ (doubleFieldBits >>> 32));
// Objects
result = 31 * result + Arrays.hashCode(arrayField); // var bits » 32-bit
result = 31 * result + referenceField.hashCode(); // var bits » 32-bit (non-nullable)
result = 31 * result + // var bits » 32-bit (nullable)
(nullableReferenceField == null
? 0
: nullableReferenceField.hashCode());
return result;
}
EDITAR
Normalmente, cuando anulas hashcode(...), también desea anular equals(...).Entonces, para aquellos que implementarán o ya han implementado equals, aquí hay una buena referencia. desde mi Github...
@Override
public boolean equals(Object o) {
// Optimization (not required).
if (this == o) {
return true;
}
// Return false if the other object has the wrong type, interface, or is null.
if (!(o instanceof MyType)) {
return false;
}
MyType lhs = (MyType) o; // lhs means "left hand side"
// Primitive fields
return booleanField == lhs.booleanField
&& byteField == lhs.byteField
&& charField == lhs.charField
&& shortField == lhs.shortField
&& intField == lhs.intField
&& longField == lhs.longField
&& floatField == lhs.floatField
&& doubleField == lhs.doubleField
// Arrays
&& Arrays.equals(arrayField, lhs.arrayField)
// Objects
&& referenceField.equals(lhs.referenceField)
&& (nullableReferenceField == null
? lhs.nullableReferenceField == null
: nullableReferenceField.equals(lhs.nullableReferenceField));
}
Primero asegúrese de que la igualdad esté implementada correctamente.De un artículo de IBM DeveloperWorks:
- Simetría:Para dos referencias, a y b, a.equals(b) si y sólo si b.equals(a)
- Reflexividad:Para todas las referencias no nulas, a.equals(a)
- Transitividad:Si a.es igual a (b) y b.es igual a (c), entonces a.es igual a (c)
Luego asegúrese de que su relación con hashCode respete el contacto (del mismo artículo):
- Coherencia con hashCode():Dos objetos iguales deben tener el mismo valor hashCode()
Finalmente, una buena función hash debería esforzarse por acercarse a la función hash ideal.
about8.blogspot.com, dijiste
Si es igual () devuelve verdadero para dos objetos, entonces hashCode () debería devolver el mismo valor.Si es igual () devuelve falso, entonces hashCode () debería devolver valores diferentes
No puedo estar de acuerdo contigo.Si dos objetos tienen el mismo código hash, no tiene por qué significar que sean iguales.
Si A es igual a B, entonces A.hashcode debe ser igual a B.hascode
pero
si A.hashcode es igual a B.hascode no significa que A deba ser igual a B
Si usas eclipse, puedes generar equals() y hashCode() usando:
Fuente -> Generar hashCode() y es igual a().
Usando esta función puedes decidir que campos desea utilizar para la igualdad y el cálculo del código hash, y Eclipse genera los métodos correspondientes.
Hay una buena implementación del Java efectivo's hashcode() y equals() lógica en Idioma Apache Commons.Verificar Generador de códigos hash y IgualesConstructor.
Solo una nota rápida para completar otra respuesta más detallada (en términos de código):
Si considero la pregunta ¿Cómo-creo-una-tabla-hash-en-java? y especialmente el Entrada de preguntas frecuentes de jGuru, creo que algunos otros criterios sobre los cuales se podría juzgar un código hash son:
- sincronización (¿el algo admite acceso concurrente o no)?
- Iteración a prueba de fallos (¿el algoritmo detecta una colección que cambia durante la iteración)?
- valor nulo (el código hash admite valores nulos en la colección)
Si entiendo su pregunta correctamente, tiene una clase de colección personalizada (es decir,una nueva clase que se extiende desde la interfaz Colección) y desea implementar el método hashCode().
Si su clase de colección extiende AbstractList, entonces no tiene que preocuparse por eso, ya existe una implementación de equals() y hashCode() que funciona iterando a través de todos los objetos y agregando sus hashCodes() juntos.
public int hashCode() {
int hashCode = 1;
Iterator i = iterator();
while (i.hasNext()) {
Object obj = i.next();
hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}
return hashCode;
}
Ahora si lo que quieres es la mejor manera de calcular el código hash para una clase específica, normalmente uso el operador ^ (bit a bit exclusivo o) para procesar todos los campos que uso en el método igual:
public int hashCode(){
return intMember ^ (stringField != null ? stringField.hashCode() : 0);
}
@sobre8:Hay un error bastante grave allí.
Zam obj1 = new Zam("foo", "bar", "baz");
Zam obj2 = new Zam("fo", "obar", "baz");
mismo código hash
probablemente quieras algo como
public int hashCode() {
return (getFoo().hashCode() + getBar().hashCode()).toString().hashCode();
(¿Puedes obtener hashCode directamente desde int en Java hoy en día?Creo que hace algo de transmisión automática.si ese es el caso, omita toString, es feo).
Como solicitó colecciones específicamente, me gustaría agregar un aspecto que las otras respuestas aún no han mencionado:Un HashMap no espera que sus claves cambien su código hash una vez que se agregan a la colección.Derrotaría todo el propósito...
Utilice los métodos de reflexión en Apache Commons IgualesConstructor y Generador de códigos hash.
cualquier método hash que distribuya uniformemente el valor hash en el rango posible es una buena implementación.Ver java efectivo ( http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq= Effective+java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn-D77qGj0wOxAxiZw&hl=en&sa=X&oi=book_result&resnum=1&ct=result ), hay un buen consejo para la implementación del código hash (elemento 9, creo...).
Prefiero usar métodos de utilidad de m Biblioteca de colecciones de Google de la clase Objetos eso me ayuda a mantener mi código limpio.Muy a menudo equals y hashcode Los métodos se crean a partir de la plantilla del IDE, por lo que no son fáciles de leer.
Utilizo un pequeño envoltorio alrededor Arrays.deepHashCode(...) porque maneja correctamente las matrices proporcionadas como parámetros
public static int hash(final Object... objects) {
return Arrays.deepHashCode(objects);
}
Aquí hay otra demostración del enfoque JDK 1.7+ con lógicas de superclase explicadas.Lo veo bastante conveniente con la clase de objeto hashCode() contabilizada, dependencia pura de JDK y sin trabajo manual adicional.tenga en cuenta Objects.hash() es tolerante a nulos.
No he incluido ninguno equals() implementación, pero en realidad, por supuesto, la necesitará.
import java.util.Objects;
public class Demo {
public static class A {
private final String param1;
public A(final String param1) {
this.param1 = param1;
}
@Override
public int hashCode() {
return Objects.hash(
super.hashCode(),
this.param1);
}
}
public static class B extends A {
private final String param2;
private final String param3;
public B(
final String param1,
final String param2,
final String param3) {
super(param1);
this.param2 = param2;
this.param3 = param3;
}
@Override
public final int hashCode() {
return Objects.hash(
super.hashCode(),
this.param2,
this.param3);
}
}
public static void main(String [] args) {
A a = new A("A");
B b = new B("A", "B", "C");
System.out.println("A: " + a.hashCode());
System.out.println("B: " + b.hashCode());
}
}
La implementación estándar es débil y su uso genera colisiones innecesarias.Imagina un
class ListPair {
List<Integer> first;
List<Integer> second;
ListPair(List<Integer> first, List<Integer> second) {
this.first = first;
this.second = second;
}
public int hashCode() {
return Objects.hashCode(first, second);
}
...
}
Ahora,
new ListPair(List.of(a), List.of(b, c))
y
new ListPair(List.of(b), List.of(a, c))
tener lo mismo hashCode, es decir 31*(a+b) + c como multiplicador utilizado para List.hashCode se reutiliza aquí.Obviamente, las colisiones son inevitables, pero producir colisiones innecesarias es simplemente...innecesario.
No hay nada sustancialmente inteligente en usar 31.El multiplicador debe ser impar para no perder información (cualquier multiplicador par pierde al menos el bit más significativo, los múltiplos de cuatro pierden dos, etc.).Se puede utilizar cualquier multiplicador impar.Los multiplicadores pequeños pueden llevar a un cálculo más rápido (el JIT puede usar cambios y sumas), pero dado que la multiplicación tiene una latencia de sólo tres ciclos en los Intel/AMD modernos, esto apenas importa.Los multiplicadores pequeños también generan más colisiones para insumos pequeños, lo que a veces puede ser un problema.
Usar un número primo no tiene sentido ya que los números primos no tienen significado en el anillo Z/(2**32).
Por lo tanto, recomendaría usar un número impar grande elegido al azar (siéntase libre de tomar un número primo).Como las CPU i86/amd64 pueden usar una instrucción más corta para operandos que caben en un solo byte con signo, existe una pequeña ventaja de velocidad para multiplicadores como 109.Para minimizar las colisiones, tome algo como 0x58a54cf5.
Usar diferentes multiplicadores en diferentes lugares es útil, pero probablemente no sea suficiente para justificar el trabajo adicional.
Al combinar valores hash, normalmente uso el método de combinación que se usa en la biblioteca boost c++, a saber:
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
Esto hace un trabajo bastante bueno al garantizar una distribución uniforme.Para obtener información sobre cómo funciona esta fórmula, consulte la publicación de StackOverflow: Número mágico en impulso::hash_combine
Hay una buena discusión sobre diferentes funciones hash en: http://burtleburtle.net/bob/hash/doobs.html
Para una clase simple, suele ser más fácil implementar hashCode() en función de los campos de clase que se verifican mediante la implementación de equals().
public class Zam {
private String foo;
private String bar;
private String somethingElse;
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
Zam otherObj = (Zam)obj;
if ((getFoo() == null && otherObj.getFoo() == null) || (getFoo() != null && getFoo().equals(otherObj.getFoo()))) {
if ((getBar() == null && otherObj. getBar() == null) || (getBar() != null && getBar().equals(otherObj. getBar()))) {
return true;
}
}
return false;
}
public int hashCode() {
return (getFoo() + getBar()).hashCode();
}
public String getFoo() {
return foo;
}
public String getBar() {
return bar;
}
}
Lo más importante es mantener la coherencia entre hashCode() y equals():Si es igual () devuelve verdadero para dos objetos, entonces hashCode () debería devolver el mismo valor.Si es igual () devuelve falso, entonces hashCode () debería devolver valores diferentes.
