Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lære Arbeide Med Hashmap I Java | Mastering Map in Java
Java Datastrukturer

bookArbeide Med Hashmap I Java

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

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

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

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-objektet deles opp i 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 hashkode-metoden for den.

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

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 se 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 til 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 der HashMap beregner samme bøtte for to elementer. I slike tilfeller oppstår en kollisjon. Enkelt forklart er en kollisjon en situasjon der 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 gunstig da det påvirker optimaliseringen. Hvis du ser på denne tabellen, vil du se at i beste fall har HashMap konstant algoritmisk kompleksitet, mens det i verste fall er 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, vil HashMap utløse en endring av størrelse ved å doble størrelsen på bøtte-arrayet. Deretter fordeles elementene på nytt over de nye bøttene ved å bruke den nye verdien av n i formelen.

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

Hvorfor er det viktig å vite dette?

Dette er lavnivå programmeringsteori som er viktig fordi datastrukturer kan ha stor innvirkning på applikasjonsytelsen når man arbeider med store datasett. Dette skjer når disse datastrukturene brukes feil.

Feil bruk av datastrukturer oppstår fordi programmerere ikke forstår hvordan disse datastrukturene fungerer. Tross alt ønsker du å bli en god programmerer, ikke sant?

I tillegg blir spørsmål om datastrukturer ofte stilt i intervjuer.

Hvis du er interessert i å lære mer om hvordan HashMap fungerer under panseret, kan du se Java-dokumentasjonen i IntelliJ IDEA.

I IntelliJ IDEA, hold nede Ctrl (Windows/Linux) eller Command (macOS) og klikk på klassenavnet for å navigere til definisjonen og se alle tilgjengelige metoder.

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 hash-kode?

question mark

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

Select the correct answer

question mark

Hva skjer i en HashMap hvis to nøkler har samme hash-kode?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 2

Spør AI

expand

Spør AI

ChatGPT

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

bookArbeide Med Hashmap I Java

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

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

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

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-objektet deles opp i 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 hashkode-metoden for den.

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

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 se 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 til 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 der HashMap beregner samme bøtte for to elementer. I slike tilfeller oppstår en kollisjon. Enkelt forklart er en kollisjon en situasjon der 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 gunstig da det påvirker optimaliseringen. Hvis du ser på denne tabellen, vil du se at i beste fall har HashMap konstant algoritmisk kompleksitet, mens det i verste fall er 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, vil HashMap utløse en endring av størrelse ved å doble størrelsen på bøtte-arrayet. Deretter fordeles elementene på nytt over de nye bøttene ved å bruke den nye verdien av n i formelen.

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

Hvorfor er det viktig å vite dette?

Dette er lavnivå programmeringsteori som er viktig fordi datastrukturer kan ha stor innvirkning på applikasjonsytelsen når man arbeider med store datasett. Dette skjer når disse datastrukturene brukes feil.

Feil bruk av datastrukturer oppstår fordi programmerere ikke forstår hvordan disse datastrukturene fungerer. Tross alt ønsker du å bli en god programmerer, ikke sant?

I tillegg blir spørsmål om datastrukturer ofte stilt i intervjuer.

Hvis du er interessert i å lære mer om hvordan HashMap fungerer under panseret, kan du se Java-dokumentasjonen i IntelliJ IDEA.

I IntelliJ IDEA, hold nede Ctrl (Windows/Linux) eller Command (macOS) og klikk på klassenavnet for å navigere til definisjonen og se alle tilgjengelige metoder.

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 hash-kode?

question mark

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

Select the correct answer

question mark

Hva skjer i en HashMap hvis to nøkler har samme hash-kode?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 2
some-alt