Java Academy · Lekcja

Implementowanie hashCode

Pisanie poprawnych funkcji haszujących

Implementowanie hashCode to bezpłatna lekcja Java Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Java Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Java Academy zawiera 4 lekcji w sumie.

Cele dobrego hashCode

Dobry hashCode() powinien:

Zwracać tę samą wartość dla równych obiektów (zgodnie z kontraktem).
Rozpraszać nierówne obiekty na wiele różnych wartości.
Być tani w obliczeniu.

Słaby hashCode zwracający stałą wartość nadal spełnia kontrakt, ale zamienia mapę w powolną listę wiązaną.

public class Main {
    public static void main(String[] args) {
        // Legal but terrible: every object collides
        System.out.println("constant hashCode is legal but kills performance");
    }
}

Objects.hash w typowym przypadku

Najprostszym poprawnym podejściem jest Objects.hash(field1, field2, ...).

Metoda obsługuje wartości null i łączy pola za pomocą standardowego algorytmu. Należy użyć tych samych pól, które są porównywane w equals.

import java.util.Objects;

public class Main {
    static class User {
        final String name; final int age;
        User(String name, int age) { this.name = name; this.age = age; }
        @Override public int hashCode() { return Objects.hash(name, age); }
    }
    public static void main(String[] args) {
        User a = new User("Ada", 36);
        User b = new User("Ada", 36);
        System.out.println(a.hashCode() == b.hashCode());
    }
}

Klasyczny mnożnik 31

W przypadku ręcznie pisanego hasha standardowy schemat polega na pomnożeniu bieżącego wyniku przez 31 i dodaniu kodu skrótu każdego pola.

31 jest nieparzystą liczbą pierwszą, a 31 * x odpowiada (x << 5) - x, dzięki czemu JVM może to zoptymalizować.

public class Main {
    static class User {
        final String name; final int age;
        User(String name, int age) { this.name = name; this.age = age; }
        @Override public int hashCode() {
            int result = 17;
            result = 31 * result + (name == null ? 0 : name.hashCode());
            result = 31 * result + age;
            return result;
        }
    }
    public static void main(String[] args) {
        System.out.println(new User("Ada", 36).hashCode());
    }
}

Haszowanie typów pierwotnych

Każdy typ pierwotny ma zalecany sposób haszowania:

int: należy użyć samej wartości.
long: (int)(value ^ (value >>> 32)).
boolean: 1 lub 0.
double: Double.hashCode(value).

public class Main {
    public static void main(String[] args) {
        long id = 4_000_000_000L;
        int longHash = (int) (id ^ (id >>> 32));
        System.out.println("long hash: " + longHash);
        System.out.println("double hash: " + Double.hashCode(3.14));
        System.out.println("bool hash: " + Boolean.hashCode(true));
    }
}

Haszowanie tablic

Nie należy bezpośrednio wywoływać hashCode() na tablicy, ponieważ metoda używa tożsamości, a nie zawartości.

Dla płaskiej tablicy należy użyć Arrays.hashCode(arr), a dla tablic zagnieżdżonych — Arrays.deepHashCode(arr).

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        int[] b = {1, 2, 3};
        System.out.println("identity equal: " + (a.hashCode() == b.hashCode()));
        System.out.println("content equal: " + (Arrays.hashCode(a) == Arrays.hashCode(b)));
    }
}

Zachowanie spójności equals i hashCode

Pola używane w hashCode() muszą być podzbiorem pól używanych w equals() — najlepiej dokładnie tym samym zbiorem.

Jeśli equals porównuje więcej pól niż hashCode, dwa równe obiekty nadal mają ten sam kod skrótu. Jest to dozwolone. Jeśli jednak hashCode używa pola ignorowanego przez equals, kontrakt zostaje złamany.

import java.util.Objects;

public class Main {
    static class Coord {
        final int x, y;
        Coord(int x, int y) { this.x = x; this.y = y; }
        @Override public boolean equals(Object o) {
            return o instanceof Coord c && c.x == x && c.y == y;
        }
        @Override public int hashCode() { return Objects.hash(x, y); }
    }
    public static void main(String[] args) {
        Coord a = new Coord(3, 4), b = new Coord(3, 4);
        System.out.println(a.equals(b) && a.hashCode() == b.hashCode());
    }
}

Buforowanie kodu skrótu

W przypadku niezmiennych obiektów, dla których haszowanie jest kosztowne, można zapisać wynik w polu.

String robi dokładnie to samo wewnętrznie. Należy stosować tę technikę tylko wtedy, gdy obiekt jest rzeczywiście niezmienny, aby zapisana wartość nigdy się nie zdezaktualizowała.

import java.util.Objects;

public class Main {
    static final class Key {
        final String a, b;
        private int hash; // 0 until computed
        Key(String a, String b) { this.a = a; this.b = b; }
        @Override public int hashCode() {
            int h = hash;
            if (h == 0) { h = Objects.hash(a, b); hash = h; }
            return h;
        }
    }
    public static void main(String[] args) {
        Key k = new Key("x", "y");
        System.out.println(k.hashCode());
        System.out.println(k.hashCode());
    }
}

Rozkład ma znaczenie

HashCode o dobrym rozkładzie równomiernie rozprasza klucze między kubełkami. Warto policzyć liczbę różnych kodów skrótu dla zestawu obiektów.

Im więcej różnych wartości, tym mniej kolizji i tym szybsza mapa.

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class Main {
    record Pair(int a, int b) {}
    public static void main(String[] args) {
        Set<Integer> hashes = new HashSet<>();
        for (int i = 0; i < 100; i++) {
            hashes.add(Objects.hash(i, i * 7));
        }
        System.out.println("distinct hashes: " + hashes.size());
    }
}

Przykład złego rozkładu

Sumowanie pól bez mnożenia powoduje kolizje: (1,2) i (2,1) dają kod skrótu równy 3.

Mnożnik 31 przełamuje tę symetrię, ponieważ kolejność zaczyna mieć znaczenie.

public class Main {
    static int badHash(int a, int b) { return a + b; }
    static int goodHash(int a, int b) { return 31 * a + b; }
    public static void main(String[] args) {
        System.out.println("bad (1,2): " + badHash(1, 2) + ", (2,1): " + badHash(2, 1));
        System.out.println("good (1,2): " + goodHash(1, 2) + ", (2,1): " + goodHash(2, 1));
    }
}

Rekordy jako typy wartości

W przypadku obiektów służących wyłącznie do przechowywania danych record automatycznie generuje poprawny kod hashCode o dobrym rozkładzie.

HashCode należy pisać ręcznie tylko wtedy, gdy potrzebna jest niestandardowa semantyka albo nie można użyć rekordu.

public class Main {
    record Money(long cents, String currency) {}
    public static void main(String[] args) {
        Money a = new Money(1099, "USD");
        Money b = new Money(1099, "USD");
        System.out.println(a.equals(b));
        System.out.println(a.hashCode() == b.hashCode());
    }
}

Złożenie całości

Kompletna klasa reprezentująca wartość: niezmienne pola, equals i hashCode oparte na tych samych polach oraz przejrzysta metoda toString.

import java.util.Objects;

public class Main {
    static final class Version {
        final int major, minor, patch;
        Version(int major, int minor, int patch) {
            this.major = major; this.minor = minor; this.patch = patch;
        }
        @Override public boolean equals(Object o) {
            return o instanceof Version v && v.major == major && v.minor == minor && v.patch == patch;
        }
        @Override public int hashCode() { return Objects.hash(major, minor, patch); }
        @Override public String toString() { return major + "." + minor + "." + patch; }
    }
    public static void main(String[] args) {
        Version v = new Version(2, 1, 0);
        System.out.println(v + " hash=" + v.hashCode());
    }
}

Szybkie sprawdzenie

Proszę sprawdzić swoje umiejętności związane z hashCode.

Podsumowanie

Poznali Państwo zasady poprawnej implementacji hashCode:

W typowym przypadku należy użyć Objects.hash(...).
W przypadku ręcznego haszowania należy zastosować wzorzec z mnożnikiem 31.
Tablice należy haszować za pomocą Arrays.hashCode, a nie domyślnej implementacji.
Pola używane przez hashCode muszą być zgodne z equals, a preferowanym rozwiązaniem są rekordy.

Następnie zobaczą Państwo, jak Java 8+ przekształca przepełnione kubełki w drzewa.

import java.util.Objects;

public class Main {
    public static void main(String[] args) {
        System.out.println("hashCode recap done: " + Objects.hash("done"));
    }
}

Często zadawane pytania

Czy lekcja „Implementowanie hashCode” jest bezpłatna?

Tak — pełny tekst „Implementowanie hashCode” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Java Academy, przejdź na CoddyKit PRO. Kurs Java Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Implementowanie hashCode”?

Pisanie poprawnych funkcji haszujących Ćwiczysz Java Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Java Academy?

Nie wymagamy żadnego doświadczenia. Java Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Implementowanie hashCode”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Java Academy?

Tak. Każda lekcja Java Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do Java Academy