La mejor implementación para el método hashCode para una colección

¿Cómo decidimos la mejor implementación del hashCode()método para una colección (suponiendo que el método igual se haya anulado correctamente)?

¿La mejor implementación? Esa es una pregunta difícil porque depende del patrón de uso.

A casi todos los casos, se propuso la aplicación razonable en buena Josh Bloch 's Effective Java en el punto 8 (segunda edición). Lo mejor es buscarlo allí porque el autor explica por qué el enfoque es bueno.

Una versión corta

1. Cree int resultay asigne un valor distinto de cero .

2. Para cada campo f probado en el equals()método, calcule un código hash cde la siguiente manera:

   • Si el campo f es a boolean: calcular (f ? 0 : 1);
   • Si el campo de f es una byte, char, shorto int: Calcular (int)f;
   • Si el campo f es a long: calcular (int)(f ^ (f >>> 32));
   • Si el campo f es a float: calcular Float.floatToIntBits(f);
   • Si el campo f es a double: calcule Double.doubleToLongBits(f)y maneje el valor de retorno como cada valor largo;
   • Si el campo f es un objeto : utilice el resultado del hashCode()método o 0 si f == null;
   • Si el campo f es una matriz : vea cada campo como elemento separado y calcule el valor hash de forma recursiva y combine los valores como se describe a continuación.

3. Combine el valor hash ccon result:

   result = 37 * result + c

4. Regreso result

Esto debería dar como resultado una distribución adecuada de los valores hash para la mayoría de las situaciones de uso.

Si está satisfecho con la implementación efectiva de Java recomendada por dmeister, puede usar una llamada a la biblioteca en lugar de lanzar la suya propia:

@Override
public int hashCode() {
    return Objects.hashCode(this.firstName, this.lastName);
}

Esto requiere Guava ( 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 poner sus esfuerzos y energía en el desarrollo de la lógica empresarial.

Aunque esto está vinculado a la Androiddocumentación (Wayback Machine) y a Mi propio código en Github , funcionará para Java en general. Mi respuesta es una extensión de la respuesta de dmeister con un 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 anula hashcode(...), también desea anular equals(...). Entonces, para aquellos que lo implementarán o ya lo implementaron equals, aquí hay una buena referencia de 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 igual se implementa correctamente. De un artículo de IBM DeveloperWorks :

• Simetría: para dos referencias, a y b, a.equals (b) si y solo si b.equals (a)
• Reflexividad: para todas las referencias no nulas, a.equals (a)
• Transitividad: si a.equals (b) y b.equals (c), entonces a.equals (c)

Luego, asegúrese de que su relación con hashCode respete el contacto (del mismo artículo):

• Consistencia 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 equals () devuelve verdadero para dos objetos, entonces hashCode () debería devolver el mismo valor. Si equals () 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 que 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 debe ser igual a B

Si usa eclipse, puede generar equals()y hashCode()usar:

Fuente -> Generar hashCode () y equals ().

Con esta función, puede decidir qué campos desea utilizar para la igualdad y el cálculo del código hash, y Eclipse genera los métodos correspondientes.

Hay una aplicación bien de la Effective Java 's hashcode()y equals()la lógica en Apache Commons Lang . Checkout HashCodeBuilder y EqualsBuilder .

Solo una nota rápida para completar otra respuesta más detallada (en términos de código):

Si considero la pregunta cómo-do-i-create-a-hash-table-in-java y especialmente la 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 (¿admite algo el 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 de la 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 desea es la mejor manera de calcular el código hash para una clase específica, normalmente uso el operador ^ (exclusivo a nivel de bit o) para procesar todos los campos que uso en el método igual:

public int hashCode(){
   return intMember ^ (stringField != null ? stringField.hashCode() : 0);
}

@ about8: 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 en estos días? Creo que hace algo de autocasting ... si ese es el caso, omite toString, es feo).

Como solicitó específicamente colecciones, 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 ...

Utilizar los métodos de reflexión sobre Apache Commons EqualsBuilder y HashCodeBuilder .

Utilizo un pequeño contenedor Arrays.deepHashCode(...)porque maneja las matrices suministradas como parámetros correctamente

public static int hash(final Object... objects) {
    return Arrays.deepHashCode(objects);
}

cualquier método de hash que distribuya uniformemente el valor de 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=res_resultante = a1& ulti =1 allí para la implementación de hashcode (elemento 9, creo ...).

Prefiero usar métodos de utilidad de la biblioteca de Google Collections de la clase Objects que me ayuda a mantener mi código limpio. Muy a menudo equalsy los hashcodemétodos se realizan a partir de la plantilla de IDE, por lo que no están limpios para leer.

Aquí hay otra demostración del enfoque JDK 1.7+ con lógicas de superclase. Lo veo bastante convincente con la clase de objeto hashCode () contada, dependencia pura de JDK y sin trabajo manual adicional. Tenga en cuenta que Objects.hash()es nulo tolerante.

No he incluido ninguna equals()implementación, pero en realidad la necesitarás.

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 conduce a 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))

tienen lo mismo hashCode, es decir, 31*(a+b) + ccomo el multiplicador utilizado para List.hashCodese reutiliza aquí. Obviamente, las colisiones son inevitables, pero producir colisiones innecesarias es simplemente ... innecesario.

No hay nada sustancialmente inteligente sobre el uso 31. El multiplicador debe ser impar para evitar perder información (cualquier multiplicador par pierde al menos el bit más significativo, los múltiplos de cuatro pierden dos, etc.). Cualquier multiplicador impar es utilizable. Los pequeños multiplicadores pueden conducir a un cálculo más rápido (el JIT puede usar cambios y adiciones), pero dado que la multiplicación tiene una latencia de solo tres ciclos en Intel / AMD moderno, esto apenas importa. Los multiplicadores pequeños también conducen a una mayor colisión para entradas pequeñas, lo que a veces puede ser un problema.

Usar un primo no tiene sentido ya que los 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 primo). Como las CPU i86 / amd64 pueden usar una instrucción más corta para los operandos que se ajustan en un solo byte firmado, 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, generalmente 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 para garantizar una distribución uniforme. Para una discusión sobre cómo funciona esta fórmula, vea la publicación de StackOverflow: Número mágico en boost :: hash_combine

Hay una buena discusión sobre las diferentes funciones hash en: http://burtleburtle.net/bob/hash/doobs.html

Para una clase simple, a menudo es más fácil implementar hashCode () en función de los campos de clase que son verificados por la implementación 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 hashCode () y equals () consistentes: si equals () devuelve verdadero para dos objetos, entonces hashCode () debería devolver el mismo valor. Si equals () devuelve falso, entonces hashCode () debería devolver valores diferentes.