Java Academy · Oppitunti

hashCoden toteuttaminen

Kirjoita oikeat hajautusfunktiot.

Oppitunti 3/413 vaihetta

hashCoden toteuttaminen on ilmainen Java Academy-oppitunti CoddyKitissä. Tämä on oppitunti 3/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Java Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Java Academy-kurssilla on yhteensä 4 oppituntia.

Hyvän hashCode-metodin tavoitteet

Hyvän hashCode()-metodin pitäisi:

Palauttaa sama arvo samoille olioille (sopimus).
Jakaa erisuuret oliot moniin eri arvoihin.
Olla edullinen laskea.

Huono hashCode, joka palauttaa aina vakioarvon, täyttää silti sopimuksen, mutta muuttaa mapin hitaaksi linkitetyksi listaksi.

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 tavalliseen tapaukseen

Yksinkertaisin oikea tapa on Objects.hash(field1, field2, ...).

Se käsittelee null-arvot ja yhdistää kentät vakiintuneella algoritmilla. Käyttäkää samoja kenttiä kuin equals-metodissa.

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

Perinteinen kertoja 31

Käsin kirjoitetussa hajautuksessa vakiintunut malli kertoo kertyvän tuloksen luvulla 31 ja lisää siihen kunkin kentän hajautusarvon.

31 on pariton alkuluku, ja 31 * x vastaa lauseketta (x << 5) - x, joten JVM voi optimoida sen.

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

Primitiivityyppien hajauttaminen

Jokaiselle primitiivityypille on suositeltu tapa laskea hajautusarvo:

int: käytetään arvoa sellaisenaan.
long: (int)(value ^ (value >>> 32)).
boolean: 1 tai 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));
    }
}

Taulukoiden hajauttaminen

Älkää kutsuko hashCode()-metodia suoraan taulukolle, koska se käyttää sisällön sijaan identiteettiä.

Käyttäkää yksiulotteiselle taulukolle Arrays.hashCode(arr)-metodia ja sisäkkäisille taulukoille Arrays.deepHashCode(arr)-metodia.

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

Pidä equals ja hashCode synkronoituna

hashCode()-metodissa käytettyjen kenttien on oltava equals()-metodissa käytettyjen kenttien osajoukko (mieluiten täsmälleen samat kentät).

Jos equals vertailee useampia kenttiä kuin hashCode, samat oliot saavat silti saman hajautusarvon. Se on sallittua. Jos hashCode kuitenkin käyttää kenttää, jonka equals jättää huomiotta, sopimus rikkoutuu.

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

Hajautusarvon välimuistittaminen

Muuttumattomille olioille, joiden hajautusarvon laskeminen on kallista, tuloksen voi tallentaa välimuistiin kenttään.

String tekee juuri näin sisäisesti. Tehkää tämä vain, jos olio on todella muuttumaton, jotta välimuistissa oleva arvo ei vanhene.

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

Jakaumalla on merkitystä

Hyvin jakautunut hashCode jakaa avaimet tasaisesti lokeroihin. Lasketaan erästä olioita eri hajautusarvojen määrä.

Mitä enemmän eri arvoja on, sitä vähemmän törmäyksiä syntyy ja sitä nopeampi map on.

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

Esimerkki huonosta jakaumasta

Kenttien summaaminen ilman kertomista aiheuttaa törmäyksiä: (1,2) ja (2,1) saavat molemmat hajautusarvoksi 3.

Kertoja 31 rikkoo tämän symmetrian, koska tällöin järjestyksellä on merkitystä.

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

Arvotyypeille kannattaa suosia recordeja

Puhtaasti dataa välittävälle tyypille record luo automaattisesti oikean ja hyvin jakautuneen hashCode-metodin.

Kirjoittakaa hashCode käsin vain, jos tarvitsette mukautettua semantiikkaa tai ette voi käyttää recordia.

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

Kootaan kokonaisuus

Täydellinen arvoluokka sisältää muuttumattomat kentät, samoihin kenttiin perustuvat equals- ja hashCode-metodit sekä selkeän toString-metodin.

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

Pikainen tarkistus

Testatkaa hashCode-taitonne.

Vastaa interaktiivisessa oppitunnissa

Kertaus

Opitte toteuttamaan hashCode-metodin oikein:

Käyttäkää Objects.hash(...)-metodia tavallisessa tapauksessa.
Käsin kirjoitetussa hajautuksessa käytetään kertojan 31 mallia.
Hajauttakaa taulukot Arrays.hashCode-metodilla, älkää oletustoteutuksella.
Pidättehän hashCode-kentät synkronoituna equals-metodin kanssa ja suositte recordeja.

Seuraavaksi näette, miten Java 8+ muuttaa liian pitkät lokerot puiksi.

import java.util.Objects;

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

Aloita maksutta

Opi Java tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 104
Oppitunnit: 374

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”hashCoden toteuttaminen” ilmainen?

Kyllä – oppitunnin ”hashCoden toteuttaminen” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Java Academy-kurssin, päivitä CoddyKit PROhon. Java Academy-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”hashCoden toteuttaminen”?

Kirjoita oikeat hajautusfunktiot. Harjoittelet Java Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Java Academy-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Java Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 3/4.

Kuinka kauan ”hashCoden toteuttaminen”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Java Academy-oppitunnilla?

Kyllä. Jokainen Java Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

← Takaisin: Java Academy