Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lære Arbejde med Hashmap i Java | Mestring af Map i Java
Learn
Kurser
Learning Tracks
Popular Topics
Practice
Projects
Quizzes & Challenges
Quizzes
Challenges
/
Java Datastrukturer

bookArbejde med Hashmap i Java

Lad os nu se nærmere på klassen, der implementerer Map-interfacet — HashMap.

Denne klasse er almindeligt anvendt, når vi taler om maps. Du har allerede haft mulighed for at arbejde med denne klasse og undersøge dens metoder. Men lad os finde ud af, hvordan denne klasse faktisk fungerer.

Først skal du forstå, hvad en hashkode er, da den bruges internt i en HashMap.

Hashkode

Hvert objekt har sin egen hashkode, som kan opnås ved hjælp af Object-klassens hashCode()-metode. Lad os 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 dataene "Hello World!" en hashkode på "-969099747". Metoden, der bestemmer præcis hvilken hashkode der vil blive overskrevet i String-klassen, ser således ud:

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 opdeles i et byte-array ved hjælp af getBytes()-metoden, hvorefter hver byte behandles og tilføjes til hashkoden. På denne måde bliver hashkoden maksimalt unik, hvilket hjælper programmet med at identificere dette objekt.

For objekter af brugerdefinerede klasser kan du også overskrive hashkoden ved at definere en unik metode til, hvordan objekter opnår dette tal. Lad os oprette en testklasse User og overskrive 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 er der 2 attributter, som jeg brugte i hashCode()-metoden. Jeg valgte tilfældige operationer i hashCode()-metoden for at opnå et maksimalt tilfældigt tal, hvilket gør det unikt for hvert User-objekt.

Dette er netop hashkoden. Lad os nu finde ud af, hvordan den bruges i en HashMap.

HashMap

En HashMap kan visualiseres som et array af spande. En spand er en liste, hvor et element gemmes. Oprindeligt har HashMap 16 spande, hvilket er DEFAULT_INITIAL_CAPACITY.

Når du indsætter et element i HashMap ved hjælp af put()-metoden, skal HashMap bestemme, hvilken specifik spand dette element skal placeres i. Dette gøres ved hjælp af en simpel formel: keyValue.hashCode() & (n - 1), hvor n er størrelsen på arrayet af spande i HashMap. '&' er en bitvis AND-operation, hvilket er lavniveau programmering, så vi går ikke i detaljer med det.

Det er vigtigt at forstå, at HashMap bruger hashkoden for nøglens værdi til at finde den passende spand. Derfor er det afgørende at skabe en maksimalt unik hashkode for at undgå kollisioner.

Kollision

Uanset hvor unik en hashkode er, kan der stadig opstå en situation, hvor HashMap beregner den samme spand for to elementer. I sådanne tilfælde opstår der en kollision. Kort sagt er en kollision en situation, hvor to eller flere elementer ender i den samme spand. De gemmes der som en SinglyLinkedList, som du implementerede tidligere.

Lad os se på en illustration:

Kollision er ikke ønskværdig, da det påvirker optimering. Hvis du ser på denne tabel, vil du se, at i det bedste tilfælde har HashMap konstant algoritmisk kompleksitet, mens det i det værste tilfælde er lineært. Denne lineære algoritmiske kompleksitet opstår på grund af betydelige kollisioner. Derfor anbefaler programmører at bruge nøgler med hashkoder, der er så unikke som muligt for at undgå kollisioner.

Hvordan håndterer HashMap kollisioner?

HashMap håndterer også kollisioner gennem konstant ændring af størrelsen på bucket-arrayet. Når antallet af elementer når 75% af størrelsen på bucket-arrayet, udløser HashMap en ændring af størrelsen ved at fordoble størrelsen på bucket-arrayet. Derefter fordeles elementerne på ny over de nye buckets ved hjælp af den nye værdi af n i formlen.

Dermed er HashMap en meget optimeret datastruktur og bruges ofte som den primære implementering af Map-interfacet.

Hvorfor er det vigtigt at kende dette?

Dette er lavniveau programmeringsteori, som er vigtig, fordi datastrukturer kan have stor indflydelse på applikationens ydeevne, når man arbejder med store datasæt. Dette sker, når datastrukturerne misbruges.

Misbrug af datastrukturer sker, fordi programmører ikke forstår, hvordan disse datastrukturer fungerer. Du vil jo gerne være en dygtig programmør, ikke?

Desuden bliver spørgsmål om datastrukturer ofte stillet til jobsamtaler.

Hvis du er interesseret i at dykke dybere ned i, hvordan HashMap fungerer under motorhjelmen, kan du læse mere i Java-dokumentationen i IntelliJ IDEA.

I IntelliJ IDEA kan du holde Ctrl (Windows/Linux) eller Command (macOS) nede og klikke på klassenavnet for at navigere til dens definition og se alle tilgængelige metoder.

1. Hvilken af følgende implementeringer bruger en hash-tabel til at gemme nøgle-værdi-par?

2. Hvad sker der i en HashMap, hvis to nøgler har den samme hashkode?

question mark

Hvilken af følgende implementeringer bruger en hash-tabel til at gemme nøgle-værdi-par?

Select the correct answer

question mark

Hvad sker der i en HashMap, hvis to nøgler har den samme hashkode?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 3. Kapitel 2

Spørg AI

expand

Spørg AI

ChatGPT

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

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?

bookArbejde med Hashmap i Java

Stryg for at vise menuen

Lad os nu se nærmere på klassen, der implementerer Map-interfacet — HashMap.

Denne klasse er almindeligt anvendt, når vi taler om maps. Du har allerede haft mulighed for at arbejde med denne klasse og undersøge dens metoder. Men lad os finde ud af, hvordan denne klasse faktisk fungerer.

Først skal du forstå, hvad en hashkode er, da den bruges internt i en HashMap.

Hashkode

Hvert objekt har sin egen hashkode, som kan opnås ved hjælp af Object-klassens hashCode()-metode. Lad os 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 dataene "Hello World!" en hashkode på "-969099747". Metoden, der bestemmer præcis hvilken hashkode der vil blive overskrevet i String-klassen, ser således ud:

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 opdeles i et byte-array ved hjælp af getBytes()-metoden, hvorefter hver byte behandles og tilføjes til hashkoden. På denne måde bliver hashkoden maksimalt unik, hvilket hjælper programmet med at identificere dette objekt.

For objekter af brugerdefinerede klasser kan du også overskrive hashkoden ved at definere en unik metode til, hvordan objekter opnår dette tal. Lad os oprette en testklasse User og overskrive 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 er der 2 attributter, som jeg brugte i hashCode()-metoden. Jeg valgte tilfældige operationer i hashCode()-metoden for at opnå et maksimalt tilfældigt tal, hvilket gør det unikt for hvert User-objekt.

Dette er netop hashkoden. Lad os nu finde ud af, hvordan den bruges i en HashMap.

HashMap

En HashMap kan visualiseres som et array af spande. En spand er en liste, hvor et element gemmes. Oprindeligt har HashMap 16 spande, hvilket er DEFAULT_INITIAL_CAPACITY.

Når du indsætter et element i HashMap ved hjælp af put()-metoden, skal HashMap bestemme, hvilken specifik spand dette element skal placeres i. Dette gøres ved hjælp af en simpel formel: keyValue.hashCode() & (n - 1), hvor n er størrelsen på arrayet af spande i HashMap. '&' er en bitvis AND-operation, hvilket er lavniveau programmering, så vi går ikke i detaljer med det.

Det er vigtigt at forstå, at HashMap bruger hashkoden for nøglens værdi til at finde den passende spand. Derfor er det afgørende at skabe en maksimalt unik hashkode for at undgå kollisioner.

Kollision

Uanset hvor unik en hashkode er, kan der stadig opstå en situation, hvor HashMap beregner den samme spand for to elementer. I sådanne tilfælde opstår der en kollision. Kort sagt er en kollision en situation, hvor to eller flere elementer ender i den samme spand. De gemmes der som en SinglyLinkedList, som du implementerede tidligere.

Lad os se på en illustration:

Kollision er ikke ønskværdig, da det påvirker optimering. Hvis du ser på denne tabel, vil du se, at i det bedste tilfælde har HashMap konstant algoritmisk kompleksitet, mens det i det værste tilfælde er lineært. Denne lineære algoritmiske kompleksitet opstår på grund af betydelige kollisioner. Derfor anbefaler programmører at bruge nøgler med hashkoder, der er så unikke som muligt for at undgå kollisioner.

Hvordan håndterer HashMap kollisioner?

HashMap håndterer også kollisioner gennem konstant ændring af størrelsen på bucket-arrayet. Når antallet af elementer når 75% af størrelsen på bucket-arrayet, udløser HashMap en ændring af størrelsen ved at fordoble størrelsen på bucket-arrayet. Derefter fordeles elementerne på ny over de nye buckets ved hjælp af den nye værdi af n i formlen.

Dermed er HashMap en meget optimeret datastruktur og bruges ofte som den primære implementering af Map-interfacet.

Hvorfor er det vigtigt at kende dette?

Dette er lavniveau programmeringsteori, som er vigtig, fordi datastrukturer kan have stor indflydelse på applikationens ydeevne, når man arbejder med store datasæt. Dette sker, når datastrukturerne misbruges.

Misbrug af datastrukturer sker, fordi programmører ikke forstår, hvordan disse datastrukturer fungerer. Du vil jo gerne være en dygtig programmør, ikke?

Desuden bliver spørgsmål om datastrukturer ofte stillet til jobsamtaler.

Hvis du er interesseret i at dykke dybere ned i, hvordan HashMap fungerer under motorhjelmen, kan du læse mere i Java-dokumentationen i IntelliJ IDEA.

I IntelliJ IDEA kan du holde Ctrl (Windows/Linux) eller Command (macOS) nede og klikke på klassenavnet for at navigere til dens definition og se alle tilgængelige metoder.

1. Hvilken af følgende implementeringer bruger en hash-tabel til at gemme nøgle-værdi-par?

2. Hvad sker der i en HashMap, hvis to nøgler har den samme hashkode?

question mark

Hvilken af følgende implementeringer bruger en hash-tabel til at gemme nøgle-værdi-par?

Select the correct answer

question mark

Hvad sker der i en HashMap, hvis to nøgler har den samme hashkode?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 3. Kapitel 2
some-alt