Java Academy · Lektion

Implementering af hashCode

Skriv korrekte hashfunktioner

Lektion 3 af 413 trin

Implementering af hashCode er en gratis Java Academy-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Java Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Java Academy-kurset indeholder 4 lektioner i alt.

Mål for en god hashCode

En god hashCode() bør:

Returnere den samme værdi for ens objekter (kontrakten).
Fordele forskellige objekter på mange forskellige værdier.
Være billig at beregne.

En dårlig hashCode, der returnerer en konstant, overholder stadig kontrakten, men forvandler tabellen til en langsom sammenkædet liste.

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 til det almindelige tilfælde

Den enkleste korrekte tilgang er Objects.hash(field1, field2, ...).

Den håndterer null-værdier og kombinerer felter med en standardalgoritme. Brug de samme felter, som du sammenligner i 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());
    }
}

Den klassiske multiplikator 31

Ved håndskrevet hashing multiplicerer standardmønstret et løbende resultat med 31 og lægger hvert felts hashkode til.

31 er et ulige primtal, og 31 * x er det samme som (x << 5) - x, så JVM'en kan optimere det.

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

Beregning af hashværdier for primitive typer

Hver primitiv type har en anbefalet måde at blive hashed på:

int: brug selve værdien.
long: (int)(value ^ (value >>> 32)).
boolean: 1 eller 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));
    }
}

Beregning af hashværdier for arrays

Kald ikke hashCode() direkte på et array; det bruger identiteten, ikke indholdet.

Brug Arrays.hashCode(arr) til et fladt array eller Arrays.deepHashCode(arr) til indlejrede arrays.

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

Hold equals og hashCode synkroniseret

Felterne, der bruges i hashCode(), skal være en delmængde af felterne, der bruges i equals() (helst præcis de samme).

Hvis equals sammenligner flere felter end hashCode, har to ens objekter stadig samme hashkode. Det er tilladt. Men hvis hashCode bruger et felt, som equals ignorerer, bryder du kontrakten.

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

Cachelagring af hashværdien

For uforanderlige objekter med dyr hashing kan du gemme resultatet i et felt.

String gør præcis dette internt. Gør det kun, når objektet virkelig er uforanderligt, så den cachelagrede værdi aldrig bliver forældet.

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

Fordelingen er vigtig

En hashCode med god fordeling spreder nøglerne jævnt over buckets. Lad os tælle antallet af forskellige hashkoder for en gruppe objekter.

Jo flere forskellige værdier, desto færre kollisioner og desto hurtigere bliver tabellen.

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

Eksempel på en dårlig fordeling

Hvis du lægger felter sammen uden multiplikation, opstår der kollisioner: (1,2) og (2,1) hashes begge til 3.

Multiplikatoren 31 bryder denne symmetri, fordi rækkefølgen så har betydning.

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

Foretræk Records til værdityper

Til rene databærere genererer en record automatisk en korrekt hashCode med god fordeling.

Skriv kun hashCode i hånden, når du har brug for brugerdefineret semantik, eller når du ikke kan bruge en record.

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

Sæt det hele sammen

En komplet værdiklasse: uforanderlige felter, equals og hashCode baseret på de samme felter samt en enkel 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());
    }
}

Hurtigt tjek

Test dine hashCode-færdigheder.

Besvar den i den interaktive lektion

Opsummering

Du har lært at implementere hashCode korrekt:

Brug Objects.hash(...) i det almindelige tilfælde.
Mønsteret med multiplikatoren 31 til håndskrevet hashing.
Beregn hashværdier for arrays med Arrays.hashCode, ikke med standardimplementeringen.
Hold hashCode-felterne synkroniseret med equals, og foretræk records.

Nu skal du se, hvordan Java 8+ omdanner overfyldte buckets til træer.

import java.util.Objects;

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

Gratis at komme i gang

Lær Java med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 104
Lektioner: 374

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Implementering af hashCode” gratis?

Ja — hele teksten til “Implementering af hashCode” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Java Academy-kurset, skal du opgradere til CoddyKit PRO. Java Academy-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Implementering af hashCode”?

Skriv korrekte hashfunktioner Du øver dig i Java Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på Java Academy?

Der kræves ingen tidligere erfaring. Java Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.

Hvor lang tid tager lektionen “Implementering af hashCode”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne Java Academy-lektion?

Ja. Alle Java Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

← Tilbage til Java Academy