Java Academy · Lektion

Implementera hashCode

Skriv korrekta hashfunktioner.

Lektion 3 av 413 steg

Implementera hashCode är en gratis lektion i Java Academy på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Java Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Java Academy innehåller totalt 4 lektioner.

Mål för en bra hashCode

En bra hashCode() bör:

Returnera samma värde för lika objekt (enligt kontraktet).
Sprida olika objekt över många olika värden.
Vara billig att beräkna.

En dålig hashCode som alltid returnerar samma värde uppfyller fortfarande kontraktet, men förvandlar mappen till en långsam länkad lista.

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 för standardfallet

Det enklaste korrekta tillvägagångssättet är Objects.hash(field1, field2, ...).

Metoden hanterar null-värden och kombinerar fälten med en standardalgoritm. Använd samma fält som du jämför 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 klassiska 31-multiplikatorn

För en handskriven hashfunktion multiplicerar standardmönstret ett löpande resultat med 31 och adderar hashvärdet för varje fält.

31 är ett udda primtal, och 31 * x är samma sak som (x << 5) - x, så JVM kan optimera 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());
    }
}

Hashning av primitiva typer

Varje primitiv typ har ett rekommenderat sätt att hashkodas:

int: använd värdet direkt.
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));
    }
}

Hashning av arrayer

Anropa inte hashCode() direkt på en array; då används identiteten, inte innehållet.

Använd Arrays.hashCode(arr) för en platt array eller Arrays.deepHashCode(arr) för nästlade arrayer.

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

Håll equals och hashCode synkroniserade

Fälten som används i hashCode() måste vara en delmängd av fälten som används i equals() (helst exakt samma fält).

Om equals jämför fler fält än hashCode delar två lika objekt fortfarande hashkod. Det är tillåtet. Men om hashCode använder ett fält som equals ignorerar bryter du mot kontraktet.

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

Cacha hashkoden

För oföränderliga objekt där hashningen är kostsam kan du cacha resultatet i ett fält.

String gör exakt detta internt. Gör det bara när objektet verkligen är oföränderligt, så att det cachade värdet aldrig blir inaktuellt.

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

Fördelningen spelar roll

En välfördelad hashCode sprider nycklar jämnt över buckets. Låt oss räkna antalet distinkta hashkoder för en grupp objekt.

Ju fler distinkta värden, desto färre kollisioner och desto snabbare blir mappen.

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

Exempel på dålig fördelning

Om du summerar fält utan att multiplicera uppstår kollisioner: (1,2) och (2,1) får båda hashvärdet 3.

31-multiplikatorn bryter denna symmetri eftersom ordningen då spelar roll.

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

Föredra records för värdetyper

För rena databärare genererar en record automatiskt en korrekt och välfördelad hashCode.

Skriv bara hashCode för hand när du behöver anpassad semantik eller inte kan använda 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ätt ihop delarna

En komplett värdeklass: oföränderliga fält, equals och hashCode från samma fält samt en ren 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());
    }
}

Snabbkontroll

Testa dina kunskaper om hashCode.

Besvara frågan i den interaktiva lektionen

Sammanfattning

Du har lärt dig att implementera hashCode korrekt:

Använd Objects.hash(...) för standardfallet.
Använd mönstret med 31-multiplikatorn för handskriven hashning.
Hashkoda arrayer med Arrays.hashCode, inte med standardimplementationen.
Håll hashCode-fälten synkroniserade med equals och föredra records.

Härnäst ska du se hur Java 8+ omvandlar överfulla buckets till träd.

import java.util.Objects;

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

Gratis att börja

Lär dig Java med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 104
Lektioner: 374

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Implementera hashCode” gratis?

Ja – hela texten till ”Implementera hashCode” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Java Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Java Academy innehåller totalt 4 lektioner.

Vad lär jag mig i ”Implementera hashCode”?

Skriv korrekta hashfunktioner. Ni övar på Java Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig Java Academy?

Du behöver inga förkunskaper. Utbildningen i Java Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.

Hur lång tid tar lektionen ”Implementera hashCode”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här Java Academy-lektionen?

Ja. Varje Java Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

← Tillbaka till Java Academy