Svep för att visa menyn

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

Denna klass används ofta 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 hashCode()-metod. Låt oss titta på ett exempel:

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 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


              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 i 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 objekt att erhålla detta nummer. Låt oss skapa en testklass User och överskrida metoden för hashkod för 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 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 nummer, vilket gör det unikt för varje User-objekt.

Detta är just hashkoden. 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 den i värsta fall är linjär. 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 kontinuerlig ändring av storleken på bucket-arrayen. När antalet element når 75 % av bucket-arrayens storlek, initierar HashMap en storleksändring 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.

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?

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 1. Kapitel 14

Fråga AI

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

Avsnitt 1. Kapitel 14

Arbete med HashMap i Java

Hashkod

HashMap

Kollision

Hur hanterar HashMap kollisioner?

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?

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