java - metodo - Mejor implementación para el método hashCode para una colección

override hashcode java

Question

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

Answer 1

¿La mejor implementación? Esa 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 la Eficaz Java de Josh Bloch 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

1. Cree un int result y asigne un valor distinto de cero .

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

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

3. Combina el valor hash c con el result :

   result = 37 * result + c

4. result retorno

Esto debería resultar en una distribución adecuada de valores hash para la mayoría de las situaciones de uso.

Answer 2

@ about8: hay un error bastante serio allí.

Zam obj1 = new Zam("foo", "bar", "baz");
Zam obj2 = new Zam("fo", "obar", "baz");

mismo hashcode

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 una autocasting ... si ese es el caso, omite la cadena de caracteres, es feo).

Answer 3

Aquí hay otra demostración de aproximación JDK 1.7+ con las lógicas de superclase contabilizadas. Lo considero bastante conveniente con la clase de objeto hashCode () contabilizada, dependencia JDK pura y sin trabajo manual adicional. Tenga en cuenta que Objects.hash() es nulo tolerante.

No he incluido ninguna implementación equals() pero en realidad, por supuesto, 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());
    }

}

Answer 4

Aunque está vinculado a la documentación de Android (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 un código que es mucho más fácil de leer y entender.

@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

Por lo general, cuando reemplaza el hashcode(...) , también desea anular los equals(...) . Así que para aquellos que ya han implementado o han 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));
}

Answer 5

Como solicitó específicamente las colecciones, me gustaría agregar un aspecto que las otras respuestas no hayan mencionado aún: A HashMap no se espera que sus claves cambien su código hash una vez que se agreguen a la colección. Derrotaría a todo el propósito ...

Answer 6

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=book_result&resnum=1&ct=result ) a continuación. allí para la implementación del código hash (artículo 9, creo ...).

Answer 7

Cuando combino 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 para asegurar una distribución uniforme. Para obtener información sobre cómo funciona esta fórmula, consulte la publicación de : Número mágico en boost :: hash_combine

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

Answer 8

Es mejor usar la funcionalidad proporcionada por Eclipse, que hace un buen trabajo y puede poner su esfuerzo y energía en el desarrollo de la lógica empresarial.

Answer 9

Hay una buena implementación de la lógica de hashcode() y equals() Java en Apache Commons Lang . Checkout HashCodeBuilder y EqualsBuilder .

Answer 10

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

tiene el mismo hashCode , a saber 31*(a+b) + c como el 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 sobre el uso de 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 llevar a un cálculo más rápido (el JIT puede usar turnos y adiciones), pero dado que la multiplicación tiene una latencia de solo tres ciclos en Intel / AMD moderno, esto no importa. Los pequeños multiplicadores también conducen a una mayor colisión para pequeños insumos, 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, recomiendo usar un número impar grande elegido al azar (siéntase libre de tomar un número primo). Como las CPUs i86 / amd64 pueden usar una instrucción más corta para los operandos que se adaptan a un solo byte con signo, hay una pequeña ventaja de velocidad para los multiplicadores como 109. Para minimizar colisiones, tome algo como 0x58a54cf5.

El uso de diferentes multiplicadores en diferentes lugares es útil, pero probablemente no sea suficiente para justificar el trabajo adicional.

Answer 11

Para una clase simple, a menudo es más fácil implementar hashCode () basado en los campos de clase que están 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 true para dos objetos, entonces hashCode () debe devolver el mismo valor. Si equals () devuelve false, entonces hashCode () debe devolver valores diferentes.

Answer 12

Prefiero usar los métodos de utilidad fromm Google Collections lib de la clase Objects que me ayudan a mantener mi código limpio. Muy a menudo, los métodos de hashcode se hacen a partir de la plantilla del IDE, por lo que no son fáciles de leer.

Answer 13

Primero asegúrese de que es igual a implementado 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):

• Coherencia con hashCode (): dos objetos iguales deben tener el mismo valor de hashCode ()

Finalmente, una buena función hash debe esforzarse por acercarse a la función hash ideal .

Answer 14

Si entiendo su pregunta correctamente, tiene una clase de colección personalizada (es decir, una clase nueva que se extiende desde la interfaz de Colección) y desea implementar el método hashCode ().

Si su clase de colección amplía AbstractList, entonces no tiene que preocuparse por eso, ya existe una implementación de equals () y hashCode () que funciona mediante la iteración de todos los objetos y la adición de 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 bits o) para procesar todos los campos que uso en el método de iguales:

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

Answer 15

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

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

Esto requiere ya sea guava ( com.google.common.base.Objects.hashCode(...) ) o JDK7 ( java.util.Objects.hash(...) ) pero funciona de la misma manera.

Answer 16

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

Fuente -> Generar código hash () y es igual a ().

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

Answer 17

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

Si considero que la pregunta how-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 (¿el algo soporta el acceso concurrente o no)?
• iteración segura (falla la detección de una colección que cambia durante la iteración)
• valor nulo (el código hash admite el valor nulo en la colección)

Answer 18

Utilice los métodos de reflexión en Apache Commons EqualsBuilder y HashCodeBuilder .

Answer 19

Utilizo un pequeño envoltorio alrededor de Arrays.deepHashCode(...) porque maneja los arreglos suministrados como parámetros correctamente

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

Answer 20

about8.blogspot.com, dijiste

Si equals () devuelve true para dos objetos, entonces hashCode () debe devolver el mismo valor. Si equals () devuelve falso, entonces hashCode () debe devolver valores diferentes

No puedo estar de acuerdo contigo. Si dos objetos tienen el mismo código hash, no significa 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 sea igual a B