Sveip for å vise menyen

La oss nå se nærmere på klassen som implementerer Map-grensesnittet — HashMap.

Denne klassen er ofte brukt når vi snakker om maps. Du har allerede fått muligheten til å arbeide med denne klassen og studere dens metoder. Men la oss finne ut hvordan denne klassen faktisk fungerer.

Først må du forstå hva en hashkode er, siden den brukes internt i en HashMap.

Hashkode

Hvert objekt har sin egen hashkode, som kan hentes ved å bruke Object-klassens hashCode()-metode. La oss se på et eksempel:

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

Som du kan se, har String-objektet med dataene "Hello World!" en hashkode på "-969099747". Metoden som bestemmer nøyaktig hvilken hashkode som skal overstyres i String-klassen ser slik ut:

Main.java


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

String-objektet brytes ned til et byte-array ved hjelp av getBytes()-metoden, hvorpå hver byte behandles og legges til hashkoden. På denne måten blir hashkoden maksimalt unik, noe som hjelper programmet med å identifisere dette objektet.

For objekter av egendefinerte klasser kan du også overstyre hashkoden ved å definere en unik måte for objektene å få dette tallet på. La oss opprette en testklasse User og overstyre hashCode-metoden for den.

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

I User-klassen finnes det 2 attributter som jeg brukte i hashCode()-metoden. Jeg valgte tilfeldige operasjoner i hashCode()-metoden for å oppnå et maksimalt tilfeldig tall, slik at det blir unikt for hvert User-objekt.

Dette er selve hashkoden. Nå skal vi finne ut hvordan den brukes i en HashMap.

HashMap

En HashMap kan visualiseres som et array av bøtter. En bøtte er en liste hvor et element lagres. Opprinnelig har HashMap 16 bøtter, som er DEFAULT_INITIAL_CAPACITY.

Når du legger inn et element i HashMap ved å bruke put()-metoden, må HashMap bestemme hvilken spesifikk bøtte dette elementet skal plasseres i. Dette gjøres ved hjelp av en enkel formel: keyValue.hashCode() & (n - 1), hvor n er størrelsen på arrayet av bøtter i HashMap. '&' er en bitvis AND-operasjon, som er lavnivå programmering, så vi går ikke nærmere inn på detaljene.

Det er viktig å forstå at HashMap bruker hashkoden til nøkkelens verdi for å finne riktig bøtte for den. Derfor er det avgjørende å lage en mest mulig unik hashkode for å unngå kollisjoner.

Kollisjon

Uansett hvor unik en hashkode er, kan det likevel oppstå en situasjon hvor HashMap beregner samme bøtte for to elementer. I slike tilfeller oppstår en kollisjon. Enkelt forklart er en kollisjon en situasjon hvor to eller flere elementer havner i samme bøtte. De lagres der som en SinglyLinkedList, som du implementerte tidligere.

La oss se på en illustrasjon:

Kollisjon er ikke ønskelig da det påvirker optimaliseringen. Hvis du ser på denne tabellen, vil du se at i beste tilfelle har HashMap konstant algoritmisk kompleksitet, mens i verste tilfelle er den lineær. Denne lineære algoritmiske kompleksiteten oppstår på grunn av betydelige kollisjoner. Derfor anbefaler programmerere å bruke nøkler med hashkoder som er så unike som mulig for å unngå kollisjoner.

Hvordan håndterer HashMap kollisjoner?

HashMap håndterer også kollisjoner gjennom kontinuerlig endring av størrelsen på bøtte-arrayet. Når antallet elementer når 75 % av størrelsen på bøtte-arrayet, utløser HashMap en endring av størrelse ved å doble størrelsen på bøtte-arrayet. Deretter fordeles elementene på nytt over de nye bøttene ved bruk av den nye verdien av n i formelen.

Dermed er HashMap en svært optimalisert datastruktur og brukes ofte som hovedimplementasjonen av Map-grensesnittet.

1. Hvilken av følgende implementasjoner bruker en hashtabell for å lagre nøkkel-verdi-par?

2. Hva skjer i en `HashMap` hvis to nøkler har samme hashkode?

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 1. Kapittel 14

Spør AI

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

Seksjon 1. Kapittel 14

Arbeide med HashMap i Java

Hashkode

HashMap

Kollisjon

Hvordan håndterer HashMap kollisjoner?

1. Hvilken av følgende implementasjoner bruker en hashtabell for å lagre nøkkel-verdi-par?

2. Hva skjer i en HashMap hvis to nøkler har samme hashkode?

2. Hva skjer i en `HashMap` hvis to nøkler har samme hashkode?