Najlepsza implementacja metody hashCode dla zbioru

Jeśli jesteś zadowolony z efektywnej implementacji Javy zalecanej przez dmeister, możesz użyć wywołania biblioteki zamiast wywoływania własnej:

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

To wymaga albo guava (com.google.common.base.Objects.hashCode(...)) lub JDK7 (java.util.Objects.hash(...)), ale działa w ten sam sposób.

Lepiej jest skorzystać z funkcjonalności dostarczanej przez Eclipse, która robi całkiem dobrą robotę i można włożyć swój wysiłek i energię w rozwój logiki biznesowej.

Chociaż jest to związane z Android Dokumentacja (Wayback Machine) i mój własny kod na Github , będzie działał ogólnie w Javie. Moja odpowiedź jest rozszerzeniem odpowiedzi dmeistera z 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;

}

EDIT

Zazwyczaj, gdy nadpisujesz hashcode(...), chcesz również nadpisać equals(...). Więc dla tych, którzy będą lub już zaimplementowali equals, oto dobra Referencja 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 equals jest poprawnie zaimplementowane. Z artykułu IBM DeveloperWorks :

• symetria: dla dwóch odwołań, a i b, A. równa się (b) wtedy i tylko wtedy, gdy B. równa się (a)
• Refleksywność: dla wszystkich odniesień nie-null, A. równa się (a)
• przechodniość: Jeśli a. równa się (b) i b. równa się (c), to a. równa się(C)

Następnie upewnij się, że ich relacja z hashCode respektuje kontakt (z tego samego artykułu):

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

Wreszcie dobra funkcja hash powinna dążyć do osiągnięcia idealnej funkcji hash .

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 () zwróci false, wtedy hashCode () zwróci inne wartości

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

Jeśli a jest równe B, to A. hashcode musi być równe B. hascode

Ale

Jeśli A. hashcode równa się B. hascode to nie znaczy, że a musi równa się B

Jest dobra implementacja efektywnej Javy 'S hashcode() i equals() logiki w Apache Commons Lang . Checkout HashCodeBuilder i EqualsBuilder.

Jeśli używasz eclipse, możesz wygenerować equals() i hashCode() używając:

Source - > Generate hashCode () and equals ().

Używając tej funkcji możesz zdecydować które pola chcesz użyć do obliczenia równości i skrótu, a Eclipse generuje odpowiednie metody.

Tylko szybka notka do uzupełnienia innych bardziej szczegółowych odpowiedzi (w zakresie kodu):

Jeśli rozważę pytanie Jak-utworzyć-a-hash-table-w-Javie, a zwłaszcza wpis JGURU FAQ , uważam, że inne kryteria, według których można oceniać kod hashowy to:

• synchronizacja (czy algo obsługuje dostęp współbieżny, czy nie) ?
Czy algo wykrywa zbiór, który zmienia się podczas iteracji?]}
• wartość null (czy kod hash obsługuje wartość null w kolekcji)

Jeśli dobrze rozumiem twoje pytanie, masz własną klasę collection (tj. nową klasę, która rozciąga się z interfejsu Collection) i chcesz zaimplementować metodę hashCode ().

Jeśli twoja klasa collection rozszerza AbstractList, to nie musisz się o to martwić, istnieje już implementacja equals() i hashCode (), która działa poprzez iterację 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, czego chcesz, jest najlepszym sposobem na Oblicz kod hash dla konkretnej klasy, zwykle używam operatora ^ (bitowo exclusive or) do przetwarzania wszystkich pól, których używam w metodzie equals:

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

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

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

Ten sam hashcode

Prawdopodobnie chcesz coś takiego

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

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

Ponieważ prosiłeś o Kolekcje, chciałbym dodać aspekt, o którym inne odpowiedzi jeszcze nie wspominały: HashMap nie oczekuje, że ich klucze zmienią hashcode po dodaniu ich do kolekcji. Zniweczyłoby to cały cel...

Użyj metod refleksyjnych na Apache Commons EqualsBuilder i HashCodeBuilder .

Każda metoda mieszania, która równomiernie rozkłada wartość mieszania w możliwym zakresie, jest dobrą implementacją. Zobacz skuteczne 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), jest tam dobra wskazówka dla implementacji hashcode (chyba punkt 9...).

Wolę używać metod użytkowych fromm Google Collections lib z class Objects , które pomagają mi utrzymać mój kod w czystości. Bardzo czÄ ™ sto metody equals i hashcode sÄ ... wykonane z szablonu IDE, wiÄ ™ c nie sÄ ... czyste do odczytania.

Używam malutkiego opakowania wokół Arrays.deepHashCode(...) ponieważ obsługuje tablice dostarczane jako parametry poprawnie

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

Oto kolejna demonstracja podejścia JDK 1.7+ z uwzględnieniem logiki superklasycznej. Widzę to jako dość wygodne z klasą obiektową hashCode (), czystą zależnością od JDK i bez dodatkowej pracy ręcznej. Należy pamiętać, że {[1] } jest tolerancyjne.

Nie uwzględniłem żadnej equals() implementacji, ale w rzeczywistości będzie ona oczywiście potrzebna.

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 i korzystanie z niej prowadzi do niepotrzebnych kolizji. Imagine a

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ą ten sam hashCode, a mianowicie {[4] } jako mnożnik używany dla List.hashCode jest tutaj ponownie używany. Oczywiście kolizje są nieuniknione, ale wytwarzanie niepotrzebnych kolizji jest po prostu... niepotrzebnie.

Nie ma nic mądrego w używaniu 31. Mnożnik musi być nieparzysty, aby uniknąć utraty informacji (każdy mnożnik parzysty traci przynajmniej najbardziej znaczący bit, wielokrotność czterech traci dwa, itp.). Każdy nieparzysty mnożnik jest użyteczny. Małe mnożniki mogą prowadzić do szybszych obliczeń( JIT może używać przesunięć i uzupełnień), ale biorąc pod uwagę, że mnożenie ma opóźnienie tylko trzech cykli na nowoczesnych Intel / AMD, to nie ma znaczenia. Małe mnożniki prowadzą również do większej kolizji dla małych wejść, co czasami może być problemem.

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

Więc, ja zalecamy użycie losowo wybranej dużej liczby nieparzystej (możesz wziąć liczbę pierwszą). Ponieważ procesory i86/amd64 mogą używać krótszej instrukcji dla operandów pasujących do jednego podpisanego bajtu, istnieje niewielka przewaga prędkości dla mnożników takich jak 109. Aby zminimalizować kolizje, weź coś w stylu 0x58a54cf5.

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

Podczas łączenia wartości hash, zwykle używam metody łączenia, która jest używana w bibliotece boost c++, a mianowicie:

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

Jest to dość dobra praca, aby zapewnić równomierną dystrybucję. Aby dowiedzieć się, jak działa ta formuła, Zobacz post StackOverflow: Magiczna liczba w boost:: hash_combine

Jest dobre omówienie różnych funkcji hashowych na: http://burtleburtle.net/bob/hash/doobs.html

Dla prostej klasy często najłatwiej jest zaimplementować hashCode() w oparciu o pola klasy, które są sprawdzane 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 zachowanie spójności hashCode() i equals (): jeśli equals() zwraca true dla dwóch obiektów, to hashCode() powinien zwrócić tę samą wartość. Jeśli equals () zwróci false, wtedy hashCode() zwróci inne wartości.