Migliore implementazione per il metodo hashCode per una raccolta

Question

Come possiamo decidere la migliore implementazione del metodo hashCode () per una raccolta (supponendo che il metodo equals sia stato sovrascritto correttamente)? ??

Answer 1

La migliore implementazione? Questa è una domanda difficile perché dipende dal modello di utilizzo.

Per quasi tutti i casi è stata proposta una buona implementazione ragionevole in Java efficace di Josh Bloch nell'articolo 8 (seconda edizione). La cosa migliore è guardarlo lassù perché l'autore spiega lì perché l'approccio è buono.

Una versione breve

1. Crea un int risultato e assegna un diverso da zero .

2. Per ogni campo f testato nel metodo equals () , calcola un codice hash c di:

   • Se il campo f è un booleano : calcola (f? 0: 1) ;
   • Se il campo f è un byte , char , short o int : calcola ( int) f ;
   • Se il campo f è un long : calcola (int) (f ^ (f > > > 32)) ;
   • Se il campo f è un float : calcola Float.floatToIntBits (f) ;
   • Se il campo f è un doppio : calcola Double.doubleToLongBits (f) e gestisci il valore restituito come ogni valore lungo;
   • Se il campo f è un oggetto : utilizzare il risultato del metodo hashCode () o 0 se f == null ;
   • Se il campo f è un array : vedere ogni campo come elemento separato e calcolare il valore di hash in modo ricorsivo e combinare i valori come descritto di seguito.

3. Combina il valore hash c con risultato :

   result = 37 * result + c
   

4. Restituisce result

Ciò dovrebbe comportare una corretta distribuzione dei valori hash per la maggior parte delle situazioni d'uso.

Answer 2

Se sei soddisfatto dell'implementazione effettiva di Java consigliata da dmeister, puoi usare una chiamata in libreria invece di lanciare la tua:

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

Ciò richiede Guava ( com.google.common.base.Objects.hashCode ) o la libreria standard in Java 7 ( java.util.Objects.hash ) ma funziona allo stesso modo.

Answer 3

È meglio usare la funzionalità fornita da Eclipse che fa un ottimo lavoro e puoi mettere i tuoi sforzi ed energie nello sviluppo della logica di business.

Answer 4

Anche se questo è collegato a Android (Wayback Machine) e Il mio codice su Github , funzionerà per Java in generale. La mia risposta è un'estensione di Risposta di dmeister con solo un codice che è molto più facile da leggere e comprendere.

@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;

}

Modifica

In genere, quando si sovrascrive hashcode (...) , si desidera sovrascrivere anche uguale a (...) . Quindi, per coloro che implementeranno o hanno già uguale a , ecco un buon riferimento dal mio 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

Per prima cosa assicurati che equals sia implementato correttamente. Da un articolo IBM DeveloperWorks :

  

  
• Simmetria: per due riferimenti, aeb, a.equals (b) if e only if b.equals (a)
  
• Riflessività: per tutti i riferimenti non nulli, a.equals (a)
  
• Transitività: se a.equals (b) e b.equals (c), quindi a.equals (c)
  

Quindi assicurati che la loro relazione con hashCode rispetti il ??contatto (dallo stesso articolo):

  

  
• Coerenza con hashCode (): due oggetti uguali devono avere lo stesso valore hashCode ()
  

Infine, una buona funzione hash dovrebbe sforzarsi di avvicinarsi alla funzione hash ideale .

Answer 6

about8.blogspot.com, hai detto

  

se equals () restituisce true per due oggetti, hashCode () dovrebbe restituire lo stesso valore. Se equals () restituisce false, allora hashCode () dovrebbe restituire valori diversi

Non posso essere d'accordo con te. Se due oggetti hanno lo stesso hashcode non significa che siano uguali.

Se A è uguale a B, allora A.hashcode deve essere uguale a B.hascode

ma

se A.hashcode è uguale a B.hascode, ciò non significa che A deve essere uguale a B

Answer 7

Se usi eclipse, puoi generare equals () e hashCode () usando:

  

Fonte - > Genera hashCode () ed equals ().

Usando questa funzione puoi decidere quali campi vuoi usare per il calcolo dell'uguaglianza e del codice hash, ed Eclipse genera i metodi corrispondenti.

Answer 8

Esiste una buona implementazione della hashcode () e equals () di Java effettiva in Apache Commons Lang . Acquista HashCodeBuilder e EqualsBuilder .

Answer 9

Solo una breve nota per completare un'altra risposta più dettagliata (in termini di codice):

Se considero la domanda how-do-i- create-a-hash-table-in-java e in particolare Voce FAQ di jGuru , credo che alcuni altri criteri in base ai quali un codice hash possa essere valutato siano:

• sincronizzazione (l'algo supporta l'accesso simultaneo o no)?
• fallisce iterazione sicura (l'algo rileva una raccolta che cambia durante l'iterazione)
• valore null (il codice hash supporta il valore null nella raccolta)

Answer 10

Se capisco correttamente la tua domanda, hai una classe di raccolta personalizzata (ovvero una nuova classe che si estende dall'interfaccia di Raccolta) e vuoi implementare il metodo hashCode ().

Se la tua classe di raccolta estende AbstractList, allora non devi preoccuparti, esiste già un'implementazione di equals () e hashCode () che funziona iterando attraverso tutti gli oggetti e sommando i loro hashCodes () insieme.

   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;
   }

Ora, se quello che vuoi è il modo migliore per calcolare il codice hash per una classe specifica, di solito uso l'operatore ^ (bitwise exclusive o) per elaborare tutti i campi che utilizzo nel metodo equals:

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

Answer 11

@ about8: c'è un bug piuttosto grave lì.

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

stesso hashcode

probabilmente vuoi qualcosa del genere

public int hashCode() {
    return (getFoo().hashCode() + getBar().hashCode()).toString().hashCode();

(puoi ottenere hashCode direttamente da int in Java in questi giorni? Penso che faccia un po 'di autocasting .. in questo caso, salta il toString, è brutto.)

Answer 12

Come hai richiesto specificamente le raccolte, vorrei aggiungere un aspetto che le altre risposte non hanno ancora menzionato: una HashMap non si aspetta che le loro chiavi cambino il loro codice hash una volta aggiunte alla raccolta. Sconfiggerebbe l'intero scopo ...

Answer 13

Usa i metodi di riflessione su Apache Commons EqualsBuilder e HashCodeBuilder .

Answer 14

qualsiasi metodo di hashing che distribuisce uniformemente il valore di hash nell'intervallo possibile è una buona implementazione. Vedere java efficace ( http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq=effective+java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn-Dx=Z;; X & amp; oi = book_result & amp; resnum = 1 & amp; ct = risultato ), c'è un buon suggerimento per l'implementazione dell'hashcode (elemento 9 penso ...).

Answer 15

Preferisco usare metodi di utilità da lib di Google Collections dalla classe Objects che mi aiutano a mantenere pulito il mio codice. Molto spesso i metodi equivalgono e hashcode sono realizzati dal modello IDE, quindi non sono puliti da leggere.

Answer 16

Uso un piccolo wrapper attorno a Arrays.deepHashCode (...) perché gestisce correttamente le matrici fornite come parametri

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

Answer 17

Ecco un'altra dimostrazione di approccio JDK 1.7+ con logiche di superclasse prese in considerazione. Lo vedo abbastanza comodo con la classe Object hashCode () spiegata, pura dipendenza JDK e nessun lavoro manuale aggiuntivo. Nota Objects.hash () è null tollerante.

Non ho incluso alcuna implementazione equals () ma in realtà ovviamente ne avrai bisogno.

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 18

L'implementazione standard è debole e il suo utilizzo porta a collisioni non necessarie. Immagina 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);
    }

    ...
}

Ora,

new ListPair(List.of(a), List.of(b, c))

e

new ListPair(List.of(b), List.of(a, c))

hanno lo stesso hashCode , ovvero 31 * (a + b) + c del moltiplicatore utilizzato per List.hashCode viene riutilizzato qui . Ovviamente, le collisioni sono inevitabili, ma produrre collisioni inutili è solo ... inutile.

Non c'è nulla di sostanzialmente intelligente nell'uso di 31 . Il moltiplicatore deve essere dispari per evitare la perdita di informazioni (qualsiasi moltiplicatore pari perde almeno il bit più significativo, i multipli di quattro ne perdono due, ecc.). È possibile utilizzare qualsiasi moltiplicatore dispari. I piccoli moltiplicatori possono portare a un calcolo più rapido (la JIT può utilizzare turni e aggiunte), ma dato che la moltiplicazione ha una latenza di soli tre cicli sui moderni Intel / AMD, questo non ha importanza. I piccoli moltiplicatori portano anche a una maggiore collisione per piccoli input, che a volte può essere un problema.

L'uso di un numero primo non ha senso poiché i numeri primi non hanno alcun significato nell'anello Z / (2 ** 32).

Quindi, consiglierei di usare un grande numero dispari scelto casualmente (sentiti libero di prendere un numero primo). Poiché le CPU i86 / amd64 possono utilizzare un'istruzione più breve per gli operandi che si adattano a un singolo byte con segno, esiste un vantaggio di velocità minuscola per moltiplicatori come 109. Per ridurre al minimo le collisioni, prendere qualcosa come 0x58a54cf5.

L'uso di moltiplicatori diversi in luoghi diversi è utile, ma probabilmente non abbastanza per giustificare il lavoro aggiuntivo.

Answer 19

Quando combino i valori di hash, di solito uso il metodo di combinazione utilizzato nella libreria boost c ++, vale a dire:

seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

Questo fa un buon lavoro nel garantire una distribuzione uniforme. Per alcune discussioni sul funzionamento di questa formula, vedere il post StackOverflow: Numero magico in boost :: hash_combine

C'è una buona discussione sulle diverse funzioni hash su: http://burtleburtle.net/bob /hash/doobs.html

Answer 20

Per una classe semplice è spesso più semplice implementare hashCode () in base ai campi della classe che sono controllati dall'implementazione 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;
    }
}

La cosa più importante è mantenere coerente hashCode () ed equals (): se equals () restituisce true per due oggetti, allora hashCode () dovrebbe restituire lo stesso valore. Se equals () restituisce false, allora hashCode () dovrebbe restituire valori diversi.