Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lära Att Arbeta med Hashmap i Java | Behärska Map i Java
Java Datastrukturer

bookAtt Arbeta med Hashmap i Java

Nu ska vi titta närmare på klassen som implementerar Map-gränssnittet — HashMap.

Denna klass är vanligt förekommande när vi pratar om mappar. Du har redan haft möjlighet att arbeta med denna klass och studera dess metoder. Men låt oss ta reda på hur denna klass faktiskt fungerar.

Först behöver du förstå vad en hashkod är, eftersom den används internt i en HashMap.

Hashkod

Varje objekt har sin egen hashkod, som kan erhållas med hjälp av Object-klassens metod hashCode(). Låt oss titta på ett exempel:

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 data "Hello World!" en hashkod på "-969099747". Metoden som avgör exakt vilken hashkod som kommer att överskrivas i String-klassen ser ut så här:

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 delas upp i en byte-array med hjälp av metoden getBytes(), varefter varje byte bearbetas och läggs till hashkoden. På detta sätt blir hashkoden maximalt unik, vilket hjälper programmet att identifiera detta objekt.

För objekt av anpassade klasser kan du även överskrida hashkoden genom att definiera ett unikt sätt för objekten att erhålla detta nummer. Låt oss skapa en testklass User och överskrida metoden för hashkod för 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 klassen User finns det 2 attribut som jag använde i metoden hashCode(). Jag valde slumpmässiga operationer i metoden hashCode() för att erhålla ett maximalt slumpmässigt tal, vilket gör det unikt för varje User-objekt.

Detta är exakt vad hashkoden är. Nu ska vi ta reda på hur den används i en HashMap.

HashMap

En HashMap kan visualiseras som en array av hinkar. En hink är en lista där ett element lagras. Inledningsvis har HashMap 16 hinkar, vilket är DEFAULT_INITIAL_CAPACITY.

När du lägger till ett element i HashMap med metoden put(), måste HashMap avgöra vilken specifik hink detta element ska placeras i. Detta görs med en enkel formel: keyValue.hashCode() & (n - 1), där n är storleken på arrayen av hinkar i HashMap. '&' är en bitvis AND-operation, vilket är låg-nivå programmering, så vi går inte in på detaljerna.

Det är viktigt att förstå att HashMap använder hashkoden för nyckelns värde för att hitta lämplig hink för det. Därför är det avgörande att skapa en så unik hashkod som möjligt för att undvika kollisioner.

Kollision

Oavsett hur unik en hashkod är kan det ändå uppstå en situation där HashMap beräknar samma hink för två element. I sådana fall uppstår en kollision. Enkelt uttryckt är en kollision en situation där två eller fler element hamnar i samma hink. De lagras där som en SinglyLinkedList, som du implementerade tidigare.

Låt oss titta på en illustration:

Kollision är inte önskvärt eftersom det påverkar optimeringen. Om du tittar på denna tabell ser du att i bästa fall har HashMap konstant algoritmisk komplexitet, medan det i värsta fall är linjärt. Denna linjära algoritmiska komplexitet uppstår vid betydande kollisioner. Därför rekommenderar programmerare att använda nycklar med hashkoder som är så unika som möjligt för att undvika kollisioner.

Hur hanterar HashMap kollisioner?

HashMap hanterar också kollisioner genom ständig omstorlekning av bucket-arrayen. När antalet element når 75 % av storleken på bucket-arrayen, initierar HashMap en omstorlekning genom att fördubbla storleken på bucket-arrayen. Därefter omfördelas elementen över de nya buckets med det nya värdet av n i formeln.

Därför är HashMap en mycket optimerad datastruktur och används ofta som den primära implementationen av Map-gränssnittet.

Varför behöver du känna till detta?

Detta är låg-nivå programmeringsteori som är viktig eftersom datastrukturer kan påverka applikationens prestanda avsevärt när man arbetar med stora datamängder. Detta sker när dessa datastrukturer används felaktigt.

Felaktig användning av datastrukturer sker eftersom programmerare inte förstår hur dessa datastrukturer fungerar. Du vill ju bli en bra programmerare, eller hur?

Dessutom ställs frågor om datastrukturer ofta vid intervjuer.

Om du är intresserad av att fördjupa dig i hur HashMap fungerar under huven kan du läsa mer i Java-dokumentationen i IntelliJ IDEA.

I IntelliJ IDEA, håll ned Ctrl (Windows/Linux) eller Command (macOS) och klicka på klassnamnet för att navigera till dess definition och se alla tillgängliga metoder.

1. Vilken av följande implementationer använder en hashtabell för att lagra nyckel-värde-par?

2. Vad händer i en HashMap om två nycklar har samma hashkod?

question mark

Vilken av följande implementationer använder en hashtabell för att lagra nyckel-värde-par?

Select the correct answer

question mark

Vad händer i en HashMap om två nycklar har samma hashkod?

Select the correct answer

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 3. Kapitel 2

Fråga AI

expand

Fråga AI

ChatGPT

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

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?

bookAtt Arbeta med Hashmap i Java

Svep för att visa menyn

Nu ska vi titta närmare på klassen som implementerar Map-gränssnittet — HashMap.

Denna klass är vanligt förekommande när vi pratar om mappar. Du har redan haft möjlighet att arbeta med denna klass och studera dess metoder. Men låt oss ta reda på hur denna klass faktiskt fungerar.

Först behöver du förstå vad en hashkod är, eftersom den används internt i en HashMap.

Hashkod

Varje objekt har sin egen hashkod, som kan erhållas med hjälp av Object-klassens metod hashCode(). Låt oss titta på ett exempel:

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 data "Hello World!" en hashkod på "-969099747". Metoden som avgör exakt vilken hashkod som kommer att överskrivas i String-klassen ser ut så här:

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 delas upp i en byte-array med hjälp av metoden getBytes(), varefter varje byte bearbetas och läggs till hashkoden. På detta sätt blir hashkoden maximalt unik, vilket hjälper programmet att identifiera detta objekt.

För objekt av anpassade klasser kan du även överskrida hashkoden genom att definiera ett unikt sätt för objekten att erhålla detta nummer. Låt oss skapa en testklass User och överskrida metoden för hashkod för 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 klassen User finns det 2 attribut som jag använde i metoden hashCode(). Jag valde slumpmässiga operationer i metoden hashCode() för att erhålla ett maximalt slumpmässigt tal, vilket gör det unikt för varje User-objekt.

Detta är exakt vad hashkoden är. Nu ska vi ta reda på hur den används i en HashMap.

HashMap

En HashMap kan visualiseras som en array av hinkar. En hink är en lista där ett element lagras. Inledningsvis har HashMap 16 hinkar, vilket är DEFAULT_INITIAL_CAPACITY.

När du lägger till ett element i HashMap med metoden put(), måste HashMap avgöra vilken specifik hink detta element ska placeras i. Detta görs med en enkel formel: keyValue.hashCode() & (n - 1), där n är storleken på arrayen av hinkar i HashMap. '&' är en bitvis AND-operation, vilket är låg-nivå programmering, så vi går inte in på detaljerna.

Det är viktigt att förstå att HashMap använder hashkoden för nyckelns värde för att hitta lämplig hink för det. Därför är det avgörande att skapa en så unik hashkod som möjligt för att undvika kollisioner.

Kollision

Oavsett hur unik en hashkod är kan det ändå uppstå en situation där HashMap beräknar samma hink för två element. I sådana fall uppstår en kollision. Enkelt uttryckt är en kollision en situation där två eller fler element hamnar i samma hink. De lagras där som en SinglyLinkedList, som du implementerade tidigare.

Låt oss titta på en illustration:

Kollision är inte önskvärt eftersom det påverkar optimeringen. Om du tittar på denna tabell ser du att i bästa fall har HashMap konstant algoritmisk komplexitet, medan det i värsta fall är linjärt. Denna linjära algoritmiska komplexitet uppstår vid betydande kollisioner. Därför rekommenderar programmerare att använda nycklar med hashkoder som är så unika som möjligt för att undvika kollisioner.

Hur hanterar HashMap kollisioner?

HashMap hanterar också kollisioner genom ständig omstorlekning av bucket-arrayen. När antalet element når 75 % av storleken på bucket-arrayen, initierar HashMap en omstorlekning genom att fördubbla storleken på bucket-arrayen. Därefter omfördelas elementen över de nya buckets med det nya värdet av n i formeln.

Därför är HashMap en mycket optimerad datastruktur och används ofta som den primära implementationen av Map-gränssnittet.

Varför behöver du känna till detta?

Detta är låg-nivå programmeringsteori som är viktig eftersom datastrukturer kan påverka applikationens prestanda avsevärt när man arbetar med stora datamängder. Detta sker när dessa datastrukturer används felaktigt.

Felaktig användning av datastrukturer sker eftersom programmerare inte förstår hur dessa datastrukturer fungerar. Du vill ju bli en bra programmerare, eller hur?

Dessutom ställs frågor om datastrukturer ofta vid intervjuer.

Om du är intresserad av att fördjupa dig i hur HashMap fungerar under huven kan du läsa mer i Java-dokumentationen i IntelliJ IDEA.

I IntelliJ IDEA, håll ned Ctrl (Windows/Linux) eller Command (macOS) och klicka på klassnamnet för att navigera till dess definition och se alla tillgängliga metoder.

1. Vilken av följande implementationer använder en hashtabell för att lagra nyckel-värde-par?

2. Vad händer i en HashMap om två nycklar har samma hashkod?

question mark

Vilken av följande implementationer använder en hashtabell för att lagra nyckel-värde-par?

Select the correct answer

question mark

Vad händer i en HashMap om två nycklar har samma hashkod?

Select the correct answer

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 3. Kapitel 2
some-alt