Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Oppiskele Työskentely HashMapin Kanssa Javassa | Mapin Hallinta Javassa
Learn
Kurssit
Learning Tracks
Popular Topics
Practice
Projects
Quizzes & Challenges
Quizzes
Challenges
/
Java-tietorakenteet

bookTyöskentely HashMapin Kanssa Javassa

Tarkastellaan nyt lähemmin Map-rajapinnan toteuttavaa luokkaa — HashMap.

Tätä luokkaa käytetään yleisesti, kun puhutaan mapeista. Olet jo päässyt työskentelemään tämän luokan kanssa ja tutustumaan sen metodeihin. Selvitetään kuitenkin, miten tämä luokka oikeasti toimii.

Ensiksi on ymmärrettävä, mitä hajautusarvo (hash code) tarkoittaa, sillä sitä käytetään sisäisesti HashMap-luokassa.

Hajautusarvo

Jokaisella oliolla on oma hajautusarvonsa, joka voidaan saada Object-luokan hashCode()-metodilla. Tarkastellaan esimerkkiä:

Main.java

Main.java

copy

              
123456789

            
package com.example;

public class Main {
    public static void main(String[] args) {
        String example = "Hello World!";
        int hash = example.hashCode();
        System.out.println("HashCode: " + hash);
    }
}

Kuten huomaat, String-objektilla, jonka data on "Hello World!", on hash-koodi "-969099747". Menetelmä, joka määrittää tarkalleen, mikä hash-koodi ylikirjoitetaan String-luokassa, näyttää tältä:

Main.java

Main.java

copy

              
1234567

            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

String-objekti jaetaan tavutaulukoksi käyttämällä getBytes()-metodia, minkä jälkeen jokainen tavu käsitellään ja lisätään hajautuskoodiin. Näin hajautuskoodista tulee mahdollisimman yksilöllinen, mikä auttaa ohjelmaa tunnistamaan tämän objektin.

Oman luokan olioille voit myös ylikirjoittaa hajautuskoodin määrittelemällä yksilöllisen tavan, jolla oliot saavat tämän numeron. Luodaan testiluokka User ja ylikirjoitetaan sen hajautuskoodi-metodi.

Main.java

Main.java

copy

              
12345678910111213141516171819202122232425262728293031

            
package com.example;

class User {
    String name;
    int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        int h = 0;
        byte[] array = name.getBytes();
        for (byte element :
                array) {
            h += element * age + (age * 15);
        }
        return h;
    }
}

public class Main {
    public static void main(String[] args) {
        User user1 = new User("Bob", 13);
        User user2 = new User("Alice", 20);
        System.out.println("First user's hash code: " + user1.hashCode());
        System.out.println("Second user's hash code: " + user2.hashCode());
    }
}

Luokassa User on 2 attribuuttia, joita käytin hashCode()-metodissa. Valitsin satunnaisia operaatioita hashCode()-metodissa saadakseni mahdollisimman satunnaisen numeron, mikä tekee siitä yksilöllisen jokaiselle User-oliolle.

Tämä on juuri hajautuskoodi. Seuraavaksi selvitetään, miten sitä käytetään HashMap.

HashMap

HashMap voidaan hahmottaa taulukoksi koreja. Kori on lista, johon alkio tallennetaan. Aluksi HashMap sisältää 16 koria, mikä on DEFAULT_INITIAL_CAPACITY.

Kun lisäät alkion HashMap-rakenteeseen put()-metodilla, HashMapin täytyy määrittää, mihin tiettyyn koriin alkio sijoitetaan. Tämä tehdään yksinkertaisella kaavalla: keyValue.hashCode() & (n - 1), missä n on koritaulukon koko HashMapissa. '&' on bittitason AND-operaatio, joka on matalan tason ohjelmointia, joten emme mene yksityiskohtiin.

On tärkeää ymmärtää, että HashMap käyttää avaimen arvon hash-koodia löytääkseen sopivan korin. Siksi on tärkeää luoda mahdollisimman yksilöllinen hash-koodi törmäysten välttämiseksi.

Törmäys

Vaikka hash-koodi olisi kuinka yksilöllinen, voi silti syntyä tilanne, jossa HashMap laskee kahdelle alkiolle saman korin. Tällöin tapahtuu törmäys. Yksinkertaisesti sanottuna törmäys on tilanne, jossa kaksi tai useampi alkio päätyy samaan koriin. Ne tallennetaan sinne SinglyLinkedList-rakenteena, jonka toteutit aiemmin.

Tarkastellaanpa havainnollistusta:

Törmäys ei ole toivottavaa, sillä se heikentää optimointia. Jos katsot tämä taulukkoa, huomaat, että parhaassa tapauksessa HashMapilla on vakio algoritminen kompleksisuus, kun taas huonoimmassa tapauksessa se on lineaarinen. Tämä lineaarinen algoritminen kompleksisuus johtuu merkittävistä törmäyksistä. Siksi ohjelmoijat suosittelevat käyttämään avaimia, joiden hash-koodit ovat mahdollisimman yksilöllisiä törmäysten välttämiseksi.

Kuinka HashMap käsittelee törmäyksiä?

HashMap ratkaisee törmäykset myös kasvattamalla bucket-taulukon kokoa säännöllisesti. Kun alkioiden määrä saavuttaa 75 % bucket-taulukon koosta, HashMap laukaisee koon kasvattamisen kaksinkertaistamalla bucket-taulukon koon. Tämän jälkeen se jakoa alkiot uudelleen uusiin bucketeihin käyttäen kaavan uutta n-arvoa.

Näin ollen HashMap on erittäin optimoitu tietorakenne ja sitä käytetään usein Map-rajapinnan ensisijaisena toteutuksena.

Miksi tämä kaikki on tärkeää tietää?

Tämä on matalan tason ohjelmointiteoriaa, joka on tärkeää, koska suurten tietomäärien kanssa työskennellessä tietorakenteet voivat vaikuttaa merkittävästi sovelluksen suorituskykyyn. Tämä tapahtuu, kun näitä tietorakenteita käytetään väärin.

Tietorakenteiden väärinkäyttö johtuu siitä, että ohjelmoijat eivät ymmärrä, miten nämä tietorakenteet toimivat. Loppujen lopuksi haluat varmasti tulla hyväksi ohjelmoijaksi, eikö niin?

Lisäksi tietorakenteisiin liittyviä kysymyksiä kysytään usein työhaastatteluissa.

Jos haluat perehtyä tarkemmin siihen, miten HashMap toimii taustalla, voit tutustua Java-dokumentaatioon IntelliJ IDEA:ssa.

IntelliJ IDEA:ssa pidä painettuna Ctrl (Windows/Linux) tai Command (macOS) ja napsauta luokan nimeä siirtyäksesi sen määritelmään ja nähdäksesi kaikki käytettävissä olevat metodit.

1. Mikä seuraavista toteutuksista käyttää hajautustaulua avain-arvo-parien tallentamiseen?

2. Mitä tapahtuu HashMap-rakenteessa, jos kahdella avaimella on sama hash-koodi?

question mark

Mikä seuraavista toteutuksista käyttää hajautustaulua avain-arvo-parien tallentamiseen?

Select the correct answer

question mark

Mitä tapahtuu HashMap-rakenteessa, jos kahdella avaimella on sama hash-koodi?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 3. Luku 2

Kysy tekoälyä

expand

Kysy tekoälyä

ChatGPT

Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme

Suggested prompts:

Can you explain more about how hash codes are generated in Java?

What happens if two objects have the same hash code in a HashMap?

Why is it important to override the hashCode() method in custom classes?

bookTyöskentely HashMapin Kanssa Javassa

Pyyhkäise näyttääksesi valikon

Tarkastellaan nyt lähemmin Map-rajapinnan toteuttavaa luokkaa — HashMap.

Tätä luokkaa käytetään yleisesti, kun puhutaan mapeista. Olet jo päässyt työskentelemään tämän luokan kanssa ja tutustumaan sen metodeihin. Selvitetään kuitenkin, miten tämä luokka oikeasti toimii.

Ensiksi on ymmärrettävä, mitä hajautusarvo (hash code) tarkoittaa, sillä sitä käytetään sisäisesti HashMap-luokassa.

Hajautusarvo

Jokaisella oliolla on oma hajautusarvonsa, joka voidaan saada Object-luokan hashCode()-metodilla. Tarkastellaan esimerkkiä:

Main.java

Main.java

copy

              
123456789

            
package com.example;

public class Main {
    public static void main(String[] args) {
        String example = "Hello World!";
        int hash = example.hashCode();
        System.out.println("HashCode: " + hash);
    }
}

Kuten huomaat, String-objektilla, jonka data on "Hello World!", on hash-koodi "-969099747". Menetelmä, joka määrittää tarkalleen, mikä hash-koodi ylikirjoitetaan String-luokassa, näyttää tältä:

Main.java

Main.java

copy

              
1234567

            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

String-objekti jaetaan tavutaulukoksi käyttämällä getBytes()-metodia, minkä jälkeen jokainen tavu käsitellään ja lisätään hajautuskoodiin. Näin hajautuskoodista tulee mahdollisimman yksilöllinen, mikä auttaa ohjelmaa tunnistamaan tämän objektin.

Oman luokan olioille voit myös ylikirjoittaa hajautuskoodin määrittelemällä yksilöllisen tavan, jolla oliot saavat tämän numeron. Luodaan testiluokka User ja ylikirjoitetaan sen hajautuskoodi-metodi.

Main.java

Main.java

copy

              
12345678910111213141516171819202122232425262728293031

            
package com.example;

class User {
    String name;
    int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        int h = 0;
        byte[] array = name.getBytes();
        for (byte element :
                array) {
            h += element * age + (age * 15);
        }
        return h;
    }
}

public class Main {
    public static void main(String[] args) {
        User user1 = new User("Bob", 13);
        User user2 = new User("Alice", 20);
        System.out.println("First user's hash code: " + user1.hashCode());
        System.out.println("Second user's hash code: " + user2.hashCode());
    }
}

Luokassa User on 2 attribuuttia, joita käytin hashCode()-metodissa. Valitsin satunnaisia operaatioita hashCode()-metodissa saadakseni mahdollisimman satunnaisen numeron, mikä tekee siitä yksilöllisen jokaiselle User-oliolle.

Tämä on juuri hajautuskoodi. Seuraavaksi selvitetään, miten sitä käytetään HashMap.

HashMap

HashMap voidaan hahmottaa taulukoksi koreja. Kori on lista, johon alkio tallennetaan. Aluksi HashMap sisältää 16 koria, mikä on DEFAULT_INITIAL_CAPACITY.

Kun lisäät alkion HashMap-rakenteeseen put()-metodilla, HashMapin täytyy määrittää, mihin tiettyyn koriin alkio sijoitetaan. Tämä tehdään yksinkertaisella kaavalla: keyValue.hashCode() & (n - 1), missä n on koritaulukon koko HashMapissa. '&' on bittitason AND-operaatio, joka on matalan tason ohjelmointia, joten emme mene yksityiskohtiin.

On tärkeää ymmärtää, että HashMap käyttää avaimen arvon hash-koodia löytääkseen sopivan korin. Siksi on tärkeää luoda mahdollisimman yksilöllinen hash-koodi törmäysten välttämiseksi.

Törmäys

Vaikka hash-koodi olisi kuinka yksilöllinen, voi silti syntyä tilanne, jossa HashMap laskee kahdelle alkiolle saman korin. Tällöin tapahtuu törmäys. Yksinkertaisesti sanottuna törmäys on tilanne, jossa kaksi tai useampi alkio päätyy samaan koriin. Ne tallennetaan sinne SinglyLinkedList-rakenteena, jonka toteutit aiemmin.

Tarkastellaanpa havainnollistusta:

Törmäys ei ole toivottavaa, sillä se heikentää optimointia. Jos katsot tämä taulukkoa, huomaat, että parhaassa tapauksessa HashMapilla on vakio algoritminen kompleksisuus, kun taas huonoimmassa tapauksessa se on lineaarinen. Tämä lineaarinen algoritminen kompleksisuus johtuu merkittävistä törmäyksistä. Siksi ohjelmoijat suosittelevat käyttämään avaimia, joiden hash-koodit ovat mahdollisimman yksilöllisiä törmäysten välttämiseksi.

Kuinka HashMap käsittelee törmäyksiä?

HashMap ratkaisee törmäykset myös kasvattamalla bucket-taulukon kokoa säännöllisesti. Kun alkioiden määrä saavuttaa 75 % bucket-taulukon koosta, HashMap laukaisee koon kasvattamisen kaksinkertaistamalla bucket-taulukon koon. Tämän jälkeen se jakoa alkiot uudelleen uusiin bucketeihin käyttäen kaavan uutta n-arvoa.

Näin ollen HashMap on erittäin optimoitu tietorakenne ja sitä käytetään usein Map-rajapinnan ensisijaisena toteutuksena.

Miksi tämä kaikki on tärkeää tietää?

Tämä on matalan tason ohjelmointiteoriaa, joka on tärkeää, koska suurten tietomäärien kanssa työskennellessä tietorakenteet voivat vaikuttaa merkittävästi sovelluksen suorituskykyyn. Tämä tapahtuu, kun näitä tietorakenteita käytetään väärin.

Tietorakenteiden väärinkäyttö johtuu siitä, että ohjelmoijat eivät ymmärrä, miten nämä tietorakenteet toimivat. Loppujen lopuksi haluat varmasti tulla hyväksi ohjelmoijaksi, eikö niin?

Lisäksi tietorakenteisiin liittyviä kysymyksiä kysytään usein työhaastatteluissa.

Jos haluat perehtyä tarkemmin siihen, miten HashMap toimii taustalla, voit tutustua Java-dokumentaatioon IntelliJ IDEA:ssa.

IntelliJ IDEA:ssa pidä painettuna Ctrl (Windows/Linux) tai Command (macOS) ja napsauta luokan nimeä siirtyäksesi sen määritelmään ja nähdäksesi kaikki käytettävissä olevat metodit.

1. Mikä seuraavista toteutuksista käyttää hajautustaulua avain-arvo-parien tallentamiseen?

2. Mitä tapahtuu HashMap-rakenteessa, jos kahdella avaimella on sama hash-koodi?

question mark

Mikä seuraavista toteutuksista käyttää hajautustaulua avain-arvo-parien tallentamiseen?

Select the correct answer

question mark

Mitä tapahtuu HashMap-rakenteessa, jos kahdella avaimella on sama hash-koodi?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 3. Luku 2
some-alt