Java Academy · leksjon

Implementere hashCode

Skriv korrekte hashfunksjoner

Leksjon 3 av 413 trinn

Implementere hashCode er en gratis leksjon i Java Academy på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Java Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Java Academy inneholder totalt 4 leksjoner.

Mål for en god hashCode

En god hashCode() bør:

Returnere samme verdi for like objekter (kontrakten).
Spre ulike objekter over mange forskjellige verdier.
Være billig å beregne.

En dårlig hashCode som returnerer en konstant, oppfyller fortsatt kontrakten, men gjør mapet om til en treg lenket 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 i vanlige tilfeller

Den enkleste korrekte fremgangsmåten er Objects.hash(field1, field2, ...).

Den håndterer null-verdier og kombinerer felt ved hjelp av en standardalgoritme. Bruk de samme feltene som De 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 31-multiplikatoren

For en håndskrevet hash bruker standardmønsteret å multiplisere et løpende resultat med 31 og legge til hashverdien til hvert felt.

31 er et oddetallsprimtall, og 31 * x er det samme som (x << 5) - x, slik at JVM-en kan optimalisere 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());
    }
}

Hashing av primitive typer

Hver primitiv type har en anbefalt måte å hashe på:

int: bruk verdien som den er.
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));
    }
}

Hashing av arrayer

Ikke kall hashCode() direkte på et array; det bruker identitet, ikke innhold.

Bruk Arrays.hashCode(arr) for et flatt array, eller Arrays.deepHashCode(arr) for nøstede 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)));
    }
}

Hold equals og hashCode synkronisert

Feltene som brukes i hashCode(), må være en delmengde av feltene som brukes i equals() (helst nøyaktig de samme).

Hvis equals sammenligner flere felt enn hashCode, vil to like objekter fortsatt ha samme hash. Det er tillatt. Men hvis hashCode bruker et felt som equals ignorerer, bryter De 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());
    }
}

Bufring av hashen

For uforanderlige objekter med kostbar hashing kan De lagre resultatet i et felt.

String gjør nettopp dette internt. Gjør det bare når objektet virkelig er uforanderlig, slik at den bufrede verdien aldri blir utdatert.

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 viktig

En hashCode med god fordeling sprer nøkler jevnt over bøttene. La oss telle antallet forskjellige hashkoder for en gruppe objekter.

Jo flere forskjellige verdier, desto færre kollisjoner og desto raskere blir mapet.

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å dårlig fordeling

Å summere felt uten å multiplisere gir kollisjoner: (1,2) og (2,1) hashes begge til 3.

31-multiplikatoren bryter denne symmetrien fordi rekkefølgen da spiller en rolle.

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

Foretrekk records for verdityper

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

Implementer bare hashCode manuelt når De trenger egendefinert semantikk eller ikke kan bruke 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());
    }
}

Slik henger det sammen

En komplett verdiklasse: uforanderlige felt, equals og hashCode basert på de samme feltene, og en ryddig 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());
    }
}

Kort test

Test hashCode-ferdighetene Deres.

Besvar den i den interaktive leksjonen

Oppsummering

De har lært å implementere hashCode korrekt:

Bruk Objects.hash(...) i vanlige tilfeller.
31-multiplikatormønsteret for håndskrevet hashing.
Hash arrayer med Arrays.hashCode, ikke standardimplementasjonen.
Hold hashCode-feltene synkronisert med equals, og foretrekk records.

Deretter skal De se hvordan Java 8+ konverterer overfylte bøtter til trær.

import java.util.Objects;

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

Gratis å komme i gang

Lær deg Java med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 104
Leksjoner: 374

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Implementere hashCode» gratis?

Ja – hele teksten i «Implementere hashCode» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Java Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Java Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Implementere hashCode»?

Skriv korrekte hashfunksjoner Du øver på Java Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Java Academy?

Ingen tidligere erfaring er nødvendig. Java Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.

Hvor lang tid tar leksjonen «Implementere hashCode»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Java Academy-leksjonen?

Ja. Alle Java Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til Java Academy