Najlepsza implementacja metody hashCode dla kolekcji

299

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

Wszechmocny
źródło
2
z Javą 7+ chyba Objects.hashCode(collection)powinno być idealnym rozwiązaniem!
Diablo,
3
@Diablo Nie wydaje mi się, żeby w ogóle odpowiadało na to pytanie - ta metoda po prostu zwraca collection.hashCode()( hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/… )
cbreezier 19.04.16

Odpowiedzi:

438

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.

dmeister
źródło
45
Tak, jestem szczególnie ciekawy, skąd pochodzi liczba 37.
Kip
17
Użyłem pozycji 8 książki „Effective Java” Josha Blocha.
dmeister
39
@dma_k Powodem używania liczb pierwszych i metody opisanej w tej odpowiedzi jest zapewnienie unikalności obliczonego kodu skrótu . Korzystając z liczb niepierwszych, nie możesz tego zagwarantować. Nie ma znaczenia, którą liczbę pierwszą wybierzesz, nie ma nic magicznego w liczbie 37 (szkoda, że ​​42 nie jest liczbą pierwszą, co?)
Simon Forsberg
34
@ SimonAndréForsberg Cóż, obliczony kod skrótu nie zawsze może być unikalny :) To kod skrótu. Wpadłem jednak na pomysł: liczba pierwsza ma tylko jeden mnożnik, podczas gdy liczba pierwsza nie ma co najmniej dwóch. To tworzy dodatkową kombinację dla operatora mnożenia, aby uzyskać ten sam skrót, tzn. Spowodować kolizję.
dma_k,
140

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.

Bacar
źródło
8
O ile nie ma dobrego powodu, aby z nich nie korzystać, zdecydowanie należy ich używać w każdym przypadku. (Formułowanie go mocniej, ponieważ należy go sformułować.) Obowiązują typowe argumenty przemawiające za użyciem standardowych implementacji / bibliotek (najlepsze praktyki, dobrze przetestowane, mniej podatne na błędy itp.).
Kissaki
7
@ justin.hughey wydaje się, że jesteś zdezorientowany. Jedynym przypadkiem, który powinieneś zastąpić, hashCodejest posiadanie własnego equalsi właśnie do tego służą te biblioteki. Dokumentacja jest dość jasna na temat ich zachowania w stosunku do equals. Implementacja biblioteki nie twierdzi, że zwalnia cię z wiedzy o tym, jakie są cechy poprawnej hashCodeimplementacji - te biblioteki to robią ułatwiają implementację takiej zgodnej implementacji w większości przypadków, gdy equalsjest ona nadpisywana.
Bacar
6
Dla wszystkich programistów Androida, którzy patrzą na klasę java.util.Objects, została ona wprowadzona tylko w API 19, więc upewnij się, że korzystasz z KitKat lub nowszej wersji, w przeciwnym razie otrzymasz NoClassDefFoundError.
Andrew Kelly,
3
Najlepsza odpowiedź IMO, chociaż jako przykład wolałbym raczej java.util.Objects.hash(...)metodę JDK7 niż guawacom.google.common.base.Objects.hashCode(...) metodę . Myślę, że większość ludzi wybrałaby standardową bibliotekę zamiast dodatkowej zależności.
Malte Skoruppa
2
Jeśli są dwa lub więcej argumentów i jeśli którykolwiek z nich jest tablicą, wynik może być inny niż oczekiwany, ponieważ hashCode()dla tablicy jest tylko jej java.lang.System.identityHashCode(...).
starikoff
59

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.

Wojownik
źródło
4
+1 Dobre praktyczne rozwiązanie. Rozwiązanie dmeistera jest bardziej kompleksowe, ale zwykle próbuję zapamiętywać wartości zerowe, kiedy sam próbuję pisać kody skrótu.
Quantum7
1
+1 Zgadzam się z Quantum7, ale powiedziałbym, że naprawdę dobrze jest zrozumieć, co robi implementacja wygenerowana przez Eclipse i skąd czerpie szczegóły dotyczące jej implementacji.
jwir3
15
Przepraszamy, ale odpowiedzi dotyczące „funkcjonalności dostarczonej przez [niektóre IDE]” nie są tak naprawdę istotne w kontekście języka programowania w ogóle. Istnieją dziesiątki IDE, a to nie odpowiada na pytanie ... a mianowicie dlatego, że chodzi tu bardziej o algorytmiczne określenie i bezpośrednio związane z implementacją equals () - coś, o czym IDE nic nie będzie wiedział.
Darrell Teague,
57

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));
}
Krzysztof Ruciński
źródło
1
Dokumentacja Androida nie zawiera już powyższego kodu, więc oto wersja podręczna z Wayback Machine - Dokumentacja Androida (07 lutego 2015)
Christopher Rucinski
17

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 .

Szara Pantera
źródło
11

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.

Attila
źródło
3
Jeśli (A != B) and (A.hashcode() == B.hashcode())to nazywamy kolizją funkcji skrótu. Dzieje się tak, ponieważ kodomaina funkcji skrótu jest zawsze skończona, podczas gdy jej domena zwykle nie jest. Im większa jest domena, tym rzadziej powinna wystąpić kolizja. Dobra funkcja skrótu powinna zwracać różne skróty dla różnych obiektów z największą możliwą możliwą do osiągnięcia przy danym rozmiarze domeny kodowej. Jednak rzadko można to w pełni zagwarantować.
Krzysztof Jabłoński
To powinien być tylko komentarz do powyższego postu dla Graya. Dobra informacja, ale tak naprawdę nie odpowiada na pytanie
Christopher Rucinski
Dobre komentarze, ale uważaj na użycie terminu „różne obiekty” ... ponieważ equals (), a tym samym implementacja hashCode () niekoniecznie dotyczą różnych obiektów w kontekście OO, ale zwykle bardziej reprezentują ich reprezentacje modelu domeny (np. Dwa ludzie mogą być traktowani tak samo, jeśli mają wspólny kod kraju i identyfikator kraju - chociaż mogą to być dwa różne „obiekty” w JVM - są uważani za „równych” i posiadających dany kod hash) ...
Darrell Teague
7

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.

Johannes K. Lehnert
źródło
7

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

Rudi Adianto
źródło
1
Minusem tego interfejsu API jest to, że ponosisz koszty budowy obiektu za każdym razem, gdy wywołujesz equals i hashcode (chyba że twój obiekt jest niezmienny i nie obliczasz skrótu wcześniej), co w niektórych przypadkach może być dużo.
James McMahon
to było moje ulubione podejście do niedawna. Natknąłem się na StackOverFlowError, używając kryteriów dla skojarzenia SharedKey OneToOne. Co więcej, Objectsklasa zapewnia hash(Object ..args)i equals()metody od Java7. Zalecane są do wszystkich aplikacji korzystających z jdk 1.7+
Diablo
@Diablo Myślę, że twoim problemem był cykl na wykresie obiektowym, a potem nie masz szczęścia z większością implementacji, ponieważ musisz zignorować jakieś odniesienie lub przerwać cykl (nakazanie IdentityHashMap). FWIW Używam hashCode na podstawie identyfikatora i jest równy dla wszystkich jednostek.
maaartinus,
6

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)
VonC
źródło
4

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);
}
Mario Ortegón
źródło
2

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

SquareCog
źródło
3
błąd znajduje się w długiej odpowiedzi about8.blogspot.com - pobranie kodu mieszającego z połączenia łańcuchów pozostawia funkcję haszującą, która jest taka sama dla dowolnej kombinacji ciągów, które składają się na ten sam ciąg.
SquareCog,
1
Więc to jest meta-dyskusja i wcale nie związana z pytaniem? ;-)
Huppie
1
Jest to poprawka do proponowanej odpowiedzi, która ma dość znaczącą wadę.
SquareCog
Jest to bardzo ograniczone wdrożenie
Christopher Rucinski
Twoje wdrożenie pozwala uniknąć problemu i wprowadza inny; Zamiana fooi barprowadzi do tego samego hashCode. Twój toStringAFAIK nie kompiluje się, a jeśli tak, to jest okropnie nieefektywny. Coś takiego 109 * getFoo().hashCode() + 57 * getBar().hashCode()jest szybsze, prostsze i nie powoduje zbędnych kolizji.
maaartinus,
2

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

Olaf Kock
źródło
2

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

Vihung
źródło
1
Jeśli zamierzasz to wykorzystać, pamiętaj, że odbicie jest drogie. Szczerze mówiąc, nie użyłbym tego do niczego poza wyrzucaniem kodu.
James McMahon
2

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);
}
starikoff
źródło
1

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ć.

nbro
źródło
1

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

}
Roman Nikitchenko
źródło
1

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ę.

maaartinus
źródło
0

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

Edward Loper
źródło
1
To pytanie dotyczy Javy, a nie C ++.
dano,
-1

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.

Chris Carruthers
źródło
1
Jak zauważyli już SquareCog. Jeśli kod skrótu jest generowany raz z połączenia dwóch łańcuchów, niezwykle łatwo jest wygenerować masę kolizji:("abc"+""=="ab"+"c"=="a"+"bc"==""+"abc") . To poważna wada. Lepiej byłoby ocenić hashcode dla obu pól, a następnie obliczyć ich kombinację liniową (najlepiej używając liczb pierwszych jako współczynników).
Krzysztof Jabłoński
@ KrzysztofJabłoński Racja. Co więcej, zamiana fooi barwywołuje niepotrzebnych kolizji, too.
maaartinus,