Najlepsza implementacja metody hashCode dla kolekcji

Jak decydujemy o najlepszej implementacji hashCode()metody dla kolekcji (zakładając, że metoda equals została poprawnie zastąpiona)?

Najlepsze wdrożenie? To trudne pytanie, ponieważ zależy od wzorca użytkowania.

A dla prawie wszystkich przypadkach rozsądnym dobrej realizacji został zaproponowany w Josh Bloch „s Effective Java w punkcie 8 (wydanie drugie). Najlepiej jest to sprawdzić, ponieważ autor wyjaśnia, dlaczego takie podejście jest dobre.

Krótka wersja

1. Utwórz a int resulti przypisz wartość niezerową .

2. Dla każdego pola f testowanego w equals()metodzie oblicz kod skrótu cpoprzez:

   • Jeśli pole f to boolean: oblicz (f ? 0 : 1);
   • Jeśli pole F jest byte, char, shorti int: oblicz (int)f;
   • Jeśli pole f to long: oblicz (int)(f ^ (f >>> 32));
   • Jeśli pole f to float: oblicz Float.floatToIntBits(f);
   • Jeśli pole f jest double: oblicz Double.doubleToLongBits(f)i zwróć wartość zwracaną jak każdą długą wartość;
   • Jeśli pole f jest obiektem : użyj wyniku hashCode()metody lub 0, jeślif == null ;
   • Jeśli pole f jest tablicą : zobacz każde pole jako osobny element i oblicz wartość skrótu w sposób rekurencyjny i połącz wartości w sposób opisany poniżej.

3. Połącz wartość skrótu cz result:

   result = 37 * result + c

4. Powrót result

Powinno to doprowadzić do właściwego rozkładu wartości skrótu w większości sytuacji użycia.

Jeśli jesteś zadowolony z efektywnej implementacji Java zalecanej przez dmeister, możesz użyć wywołania bibliotecznego zamiast tworzyć własne:

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

Wymaga to Guava ( com.google.common.base.Objects.hashCode) lub standardowej biblioteki Java 7 ( java.util.Objects.hash), ale działa w ten sam sposób.

Lepiej jest korzystać z funkcjonalności dostarczonej przez Eclipse, która wykonuje całkiem niezłą robotę, a Ty możesz włożyć wysiłek i energię w rozwój logiki biznesowej.

Chociaż jest to powiązane z Androiddokumentacją (Wayback Machine) i Moim własnym kodem na Github , ogólnie będzie działało w Javie. Moja odpowiedź jest rozszerzeniem Odpowiedzi dmeistera z samym kodem, który jest znacznie łatwiejszy do odczytania i zrozumienia.

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

}

EDYTOWAĆ

Zazwyczaj, gdy przesłonisz hashcode(...), chcesz również przesłonić equals(...). Więc dla tych, którzy wdrożą lub już wdrożyli equals, oto dobre referencje z mojego 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));
}

Najpierw upewnij się, że równość jest poprawnie zaimplementowana. Z artykułu IBM DeveloperWorks :

• Symetria: dla dwóch odniesień, aib, a. Równości (b) wtedy i tylko wtedy, gdy b. Równania (a)
• Refleksyjność: dla wszystkich wartości innych niż null, a.equals (a)
• Przejściowość: Jeśli a. Równe (b) i b. Równe (c), to a. Równe (c)

Następnie upewnij się, że ich związek z hashCode uwzględnia kontakt (z tego samego artykułu):

• Spójność z hashCode (): Dwa równe obiekty muszą mieć tę samą wartość hashCode ()

Wreszcie dobra funkcja skrótu powinna dążyć do zbliżenia się do idealnej funkcji skrótu .

about8.blogspot.com, powiedziałeś

jeśli equals () zwraca true dla dwóch obiektów, to hashCode () powinien zwrócić tę samą wartość. Jeśli equals () zwraca false, to hashCode () powinno zwracać różne wartości

Nie mogę się z tobą zgodzić. Jeśli dwa obiekty mają ten sam kod skrótu, nie musi to oznaczać, że są one równe.

Jeśli A jest równe B, to kod skrótu A. musi być równy kodowi skrótu B.

ale

jeśli A. skrót jest równy B. kod nie oznacza, że ​​A musi być równe B.

Jeśli używasz Eclipse, możesz wygenerować equals()i hashCode()użyć:

Źródło -> Wygeneruj hashCode () i equals ().

Za pomocą tej funkcji możesz zdecydować, które pola mają być używane do obliczania równości i kodu mieszania, a Eclipse generuje odpowiednie metody.

Jest to realizacja dobra Efektywna Java „s hashcode()i equals()logiki w Apache Commons Lang . Kasa HashCodeBuilder i EqualsBuilder .

Krótka uwaga na wypełnienie innej, bardziej szczegółowej odpowiedzi (w zakresie kodu):

Jeśli zastanowię się nad pytaniem, jak-i-utworzyć-tabelę-skrót-java, a zwłaszcza wpis FAQ jGuru , uważam, że inne kryteria, na podstawie których można oceniać kod skrótu, to:

• synchronizacja (czy algo obsługuje równoczesny dostęp, czy nie)?
• nie powiedzie się bezpieczna iteracja (czy algo wykrywa kolekcję, która zmienia się podczas iteracji)
• wartość null (czy kod skrótu obsługuje wartość null w kolekcji)

Jeśli dobrze rozumiem twoje pytanie, masz niestandardową klasę kolekcji (tj. Nową klasę, która rozszerza się z interfejsu Collection) i chcesz zaimplementować metodę hashCode ().

Jeśli twoja klasa kolekcji rozszerza AbstractList, nie musisz się tym martwić, istnieje już implementacja equals () i hashCode (), która działa poprzez iterowanie wszystkich obiektów i dodawanie ich hashCodes () razem.

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

Teraz, jeśli to, co chcesz, jest najlepszym sposobem obliczenia kodu skrótu dla określonej klasy, zwykle używam operatora ^ (wyłączanie bitowe lub) do przetwarzania wszystkich pól, których używam w metodzie równości:

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

@ about8: jest tam dość poważny błąd.

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

ten sam kod skrótu

prawdopodobnie chcesz coś takiego

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

(czy w dzisiejszych czasach możesz uzyskać hashCode bezpośrednio z int w Javie? Myślę, że robi to autocasting .. jeśli tak jest, pomiń toString, to jest brzydkie.)

Jak konkretnie poprosiłeś o kolekcje, chciałbym dodać aspekt, o którym inne odpowiedzi jeszcze nie wspomniały: HashMap nie oczekuje, że ich klucze zmienią kod skrótu po dodaniu do kolekcji. Pokonałby cały cel ...

Użyj metod refleksji w Apache Commons EqualsBuilder i HashCodeBuilder .

Używam małego opakowania, Arrays.deepHashCode(...)ponieważ poprawnie obsługuje tablice dostarczone jako parametry

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

każda metoda mieszająca, która równomiernie rozkłada wartość skrótu w możliwym zakresie, jest dobrą implementacją. Zobacz skuteczną Java ( 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 ), istnieje wskazówka dobry tam do implementacji hashcode (myślę, że pozycja 9 ...).

Wolę używać metod narzędziowych z biblioteki Google Kolekcje z klas Obiektów, które pomagają mi utrzymać kod w czystości. Bardzo często equalsi hashcodemetody są wykonane z szablonu IDE, więc ich nie są czyste czytać.

Oto kolejna demonstracja podejścia JDK 1.7+ z uwzględnieniem logiki nadklasy. Widzę to jako całkiem wygodne z uwzględnioną hashCode () klasy Object, czystą zależnością JDK i bez dodatkowej pracy ręcznej. Uwaga: Objects.hash()tolerancja zerowa.

Nie wdrożyłem żadnej equals()implementacji, ale w rzeczywistości będzie to oczywiście potrzebne.

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

}

Standardowa implementacja jest słaba, a korzystanie z niej prowadzi do niepotrzebnych kolizji. Wyobraź sobie

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

    ...
}

Teraz,

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

i

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

mają to samo hashCode, mianowicie 31*(a+b) + cjako mnożnik zastosowany dlaList.hashCode zostaje ponownie użyty tutaj. Oczywiście kolizji nie da się uniknąć, ale tworzenie zbędnych kolizji jest po prostu ... niepotrzebne.

W użyciu nie ma nic mądrego 31. Mnożnik musi być nieparzysty, aby uniknąć utraty informacji (każdy parzysty mnożnik traci co najmniej najbardziej znaczący bit, wielokrotności czterech tracą dwa itd.). Można zastosować dowolny nieparzysty mnożnik. Małe mnożniki mogą prowadzić do szybszych obliczeń (JIT może używać przesunięć i dodatków), ale biorąc pod uwagę, że mnożenie ma opóźnienie tylko trzech cykli we współczesnym Intel / AMD, nie ma to większego znaczenia. Małe mnożniki prowadzą również do większej kolizji przy małych nakładach, co może czasem stanowić problem.

Używanie liczby pierwszej jest bezcelowe, ponieważ liczby pierwsze nie mają znaczenia w pierścieniu Z / (2 ** 32).

Tak więc polecam użycie losowo wybranej dużej liczby nieparzystej (nie krępuj się wziąć liczby pierwsze). Ponieważ procesory i86 / amd64 mogą używać krótszej instrukcji dla argumentów pasujących do pojedynczego podpisanego bajtu, istnieje niewielka przewaga szybkości dla multiplikatorów takich jak 109. Aby zminimalizować kolizje, weź coś takiego jak 0x58a54cf5.

Używanie różnych mnożników w różnych miejscach jest pomocne, ale prawdopodobnie niewystarczające, aby uzasadnić dodatkową pracę.

Podczas łączenia wartości skrótu zwykle używam metody łączenia stosowanej w bibliotece boost c ++, a mianowicie:

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

Zapewnia to dość dobrą pracę, zapewniając równomierną dystrybucję. Aby uzyskać omówienie działania tej formuły, zobacz wpis StackOverflow: Magiczna liczba w boost :: hash_combine

Dobra dyskusja na temat różnych funkcji skrótu znajduje się na stronie : http://burtleburtle.net/bob/hash/doobs.html

W przypadku prostej klasy często najłatwiej jest zaimplementować hashCode () na podstawie pól klasy sprawdzanych przez implementację 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;
    }
}

Najważniejszą rzeczą jest utrzymanie spójności hashCode () i equals (): jeśli equals () zwraca true dla dwóch obiektów, to hashCode () powinno zwrócić tę samą wartość. Jeśli equals () zwraca false, to hashCode () powinno zwracać różne wartości.