Pyyhkäise näyttääksesi valikon

Tarkastellaan nyt lähemmin luokkaa, joka toteuttaa Map-rajapinnan — 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 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


              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


              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.

Omaksi luokaksi määritellyille olioille voidaan myös ylikirjoittaa hajautuskoodi määrittelemällä yksilöllinen tapa, jolla olio saa tämän numeron. Luodaan testiluokka User ja ylikirjoitetaan sen hajautuskoodi-metodi.

Main.java


              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, jolloin se on yksilöllinen jokaiselle User-oliolle.

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

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 HashMapiin put()-metodilla, HashMapin täytyy määrittää, mihin tiettyyn koriin tämä 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 olennaista luoda mahdollisimman yksilöllinen hash-koodi törmäysten välttämiseksi.

Törmäys

Riippumatta siitä, kuinka yksilöllinen hash-koodi on, voi silti syntyä tilanne, jossa HashMap laskee saman korin kahdelle alkiolle. 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ätä 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 säiliötaulukon jatkuvalla koon muuttamisella. Kun alkioiden määrä saavuttaa 75 % säiliötaulukon koosta, HashMap laukaisee koon kasvattamisen kaksinkertaistamalla säiliötaulukon koon. Tämän jälkeen se jakaantuu alkiot uudelleen uusiin säiliöihin 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.

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

2. Mitä tapahtuu, jos kahdella avaimella on sama hajautusarvo `HashMap`:ssa?

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 1. Luku 14

Kysy tekoälyä

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

Osio 1. Luku 14

Työskentely HashMapin Kanssa Javassa

Hajautusarvo

HashMap

Törmäys

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

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

2. Mitä tapahtuu, jos kahdella avaimella on sama hajautusarvo HashMap:ssa?

2. Mitä tapahtuu, jos kahdella avaimella on sama hajautusarvo `HashMap`:ssa?