Java Language metodo hashCode ()

Esempio

Quando una classe Java sovrascrive il metodo equals , dovrebbe sovrascrivere anche il metodo hashCode . Come definito nel contratto del metodo :

  • Ogni volta che viene invocato sullo stesso oggetto più di una volta durante l'esecuzione di un'applicazione Java, il metodo hashCode deve restituire costantemente lo stesso numero intero, a condizione che non vengano modificate le informazioni utilizzate nei confronti degli uguali sull'oggetto. Questo numero intero non deve rimanere coerente da un'esecuzione di un'applicazione a un'altra esecuzione della stessa applicazione.
  • Se due oggetti sono uguali secondo il metodo equals(Object) , quindi chiamare il metodo hashCode su ciascuno dei due oggetti deve produrre lo stesso risultato intero.
  • Non è necessario che se due oggetti non sono uguali secondo il metodo equals(Object) , quindi chiamare il metodo hashCode su ciascuno dei due oggetti deve produrre risultati interi distinti. Tuttavia, il programmatore dovrebbe essere consapevole del fatto che la produzione di risultati interi distinti per oggetti non uguali può migliorare le prestazioni delle tabelle hash.

I codici hash vengono utilizzati nelle implementazioni hash come HashMap , HashTable e HashSet . Il risultato della funzione hashCode determina il bucket in cui verrà inserito un oggetto. Queste implementazioni di hash sono più efficienti se l'implementazione hashCode fornita è buona. Una proprietà importante di una buona implementazione di hashCode è che la distribuzione dei valori hashCode è uniforme. In altre parole, esiste una piccola probabilità che numerose istanze vengano archiviate nello stesso bucket.

Un algoritmo per calcolare un valore di codice hash potrebbe essere simile al seguente:

public class Foo {
    private int field1, field2;
    private String field3;

    public Foo(int field1, int field2, String field3) {
        this.field1 = field1;
        this.field2 = field2;
        this.field3 = field3;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }

        Foo f = (Foo) obj;
        return field1 == f.field1 &&
               field2 == f.field2 &&
               (field3 == null ? f.field3 == null : field3.equals(f.field3);
    }

    @Override
    public int hashCode() {
        int hash = 1;
        hash = 31 * hash + field1;
        hash = 31 * hash + field2;
        hash = 31 * hash + (field3 == null ? 0 : field3.hashCode());
        return hash;
    }
}

Utilizzo di Arrays.hashCode () come scorciatoia

Java SE 1.2

In Java 1.2 e versioni successive, invece di sviluppare un algoritmo per calcolare un codice hash, è possibile generare uno utilizzando java.util.Arrays#hashCode fornendo una matrice Object o primitive contenente i valori del campo:

@Override
public int hashCode() {
    return Arrays.hashCode(new Object[] {field1, field2, field3});
}
Java SE 7

Java 1.7 ha introdotto la classe java.util.Objects che fornisce un metodo di convenienza, hash(Object... objects) , che calcola un codice hash basato sui valori degli oggetti forniti. Questo metodo funziona proprio come java.util.Arrays#hashCode .

@Override
public int hashCode() {
    return Objects.hash(field1, field2, field3);
}

Nota: questo approccio è inefficiente e produce oggetti spazzatura ogni volta che viene chiamato il metodo hashCode() personalizzato:

  • Viene creato un Object[] temporaneo Object[] . (Nella versione Objects.hash() , la matrice viene creata dal meccanismo "varargs".)
  • Se uno dei campi è di tipo primitivo, deve essere inserito in una scatola e ciò può creare più oggetti temporanei.
  • La matrice deve essere popolata.
  • L'array deve essere ripetuto dal metodo Arrays.hashCode o Objects.hash .
  • Le chiamate a Object.hashCode() che Arrays.hashCode o Objects.hash devono rendere (probabilmente) non possono essere inline.

Memorizzazione nella cache interna dei codici hash

Poiché il calcolo del codice hash di un oggetto può essere costoso, può essere interessante memorizzare nella cache il valore del codice hash all'interno dell'oggetto la prima volta che viene calcolato. Per esempio

public final class ImmutableArray {
    private int[] array;
    private volatile int hash = 0;

    public ImmutableArray(int[] initial) {
        array = initial.clone();
    }

    // Other methods

    @Override
    public boolean equals(Object obj) {
         // ...
    }

    @Override
    public int hashCode() {
        int h = hash;
        if (h == 0) {
            h = Arrays.hashCode(array);
            hash = h;
        }
        return h;
    }
}

Questo approccio elimina il costo di (ripetutamente) il calcolo del codice hash contro il sovraccarico di un campo aggiuntivo per memorizzare il codice hash. Se ciò si ripaga, l'ottimizzazione delle prestazioni dipenderà dalla frequenza con cui un determinato oggetto viene sottoposto a hashing (cercato) e da altri fattori.

Noterete anche che se il vero codice hash di un ImmutableArray sembra essere pari a zero (una possibilità su 2 32), la cache è inefficace.

Infine, questo approccio è molto più difficile da implementare correttamente se l'oggetto che stiamo tritando è mutabile. Tuttavia, vi sono maggiori preoccupazioni se i codici hash cambiano; vedi il contratto di cui sopra.