Java Academy · Lektion

Så fungerar HashMap

Buckets, hashning och kollisioner.

Lektion 1 av 413 steg

Så fungerar HashMap är en gratis lektion i Java Academy på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Java Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Java Academy innehåller totalt 4 lektioner.

Vad HashMap lagrar

En HashMap lagrar nyckel-värdepar och ger i genomsnitt uppslagning, insättning och borttagning i O(1).

Internt innehåller den en array som kallas tabellen. Varje plats i denna array kallas en bucket.

Nyckeln avgör vilken bucket en post hamnar i.
Värdet är det du får tillbaka när du slår upp nyckeln.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 30);
        ages.put("Bob", 25);
        System.out.println(ages.get("Alice"));
    }
}

Hasha nyckeln

När du anropar put(key, value) anropar map-objektet key.hashCode() för att få ett int.

HashMap sprider sedan dessa bitar med en intern funktion, så att även svaga hashkoder fördelas över bucketarna.

Det slutliga talet reduceras med hash & (table.length - 1) för att få ett bucketindex.
Tabellens längd är alltid en tvåpotens, så masken fungerar.

public class Main {
    public static void main(String[] args) {
        String key = "Alice";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);
        int index = spread & (16 - 1);
        System.out.println("hashCode: " + h);
        System.out.println("bucket index: " + index);
    }
}

Bucketar i praktiken

Varje bucket kan innehålla mer än en post. När två nycklar mappas till samma bucket uppstår en kollision.

Kollisioner är normala och förväntade. HashMap hanterar dem genom att länka ihop posterna i bucketen.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

Kollisioner och länkning

Före Java 8 låg alla poster som kolliderade i en enkellänkad lista inuti bucketen.

Vid en uppslagning går HashMap igenom listan och anropar equals() tills den hittar den matchande nyckeln.

Få kollisioner: fortfarande i praktiken O(1).
Många kollisioner i en bucket: försämras mot O(n) för den bucketen.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

Varför FB och Ea kolliderar

Strängarna "FB" och "Ea" har samma hashCode() i Java. Det här är ett klassiskt exempel på en kollision.

Även med identiska hashkoder håller map-objektet dem åtskilda, eftersom equals() skiljer dem åt inuti bucketen.

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

Lastfaktor

Lastfaktorn styr hur full tabellen får bli innan den växer. Standardvärdet är 0.75.

Kapaciteten 16 och lastfaktorn 0.75 innebär att storleksändring utlöses vid 12 poster.
En lägre lastfaktor slösar minne men minskar antalet kollisioner.
En högre lastfaktor sparar minne men ökar antalet kollisioner.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

Ändra storlek på tabellen

När antalet poster överstiger capacity * loadFactor fördubblas tabellens storlek.

Varje befintlig post hashas om i den nya, större tabellen. Det här är en kostsam operation, så det är viktigt att ange rätt storlek i förväg för stora map-objekt.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

Förinställ storleken för bättre prestanda

Om du ungefär vet hur många poster du kommer att lagra kan du ange en initial kapacitet för att undvika upprepade storleksändringar.

Tumregel: initial kapacitet = expectedSize / 0.75 + 1.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

Null-nycklar och null-värden

HashMap tillåter en null-nyckel och flera null-värden.

Null-nyckeln hamnar alltid i bucket 0 (dess hash behandlas som 0).
Använd getOrDefault för att undvika tvetydighet mellan en saknad nyckel och ett null-värde.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

Iterationsordningen garanteras inte

HashMap ger inga garantier för iterationsordningen. Ordningen beror på hashkoderna och bucketarnas layout.

Om du behöver en förutsägbar ordning kan du använda LinkedHashMap (insättningsordning) eller TreeMap (sorterad ordning).

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

get()-sökvägen sammanfattad

En sökning följer dessa steg:

Beräkna hashCode() och sprid bitarna.
Använd en mask för att hitta bucketens index.
Gå igenom bucket och jämför nycklar med equals().
Returnera det matchande värdet eller null.

En bra hashCode tillsammans med en korrekt equals gör varje steg snabbt.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

Snabbkontroll

Testa din förståelse av hur HashMap hittar en bucket.

Besvara frågan i den interaktiva lektionen

Sammanfattning

Du har lärt dig hur HashMap fungerar internt:

Nycklar hashkodas och mappas till buckets.
Kollisioner hanteras genom att länka poster i en bucket.
Belastningsfaktorn (0.75) utlöser en fördubbling och omhashning.
Genom att ange en lämplig initial storlek undviker du kostsamma storleksändringar, och itereringsordningen garanteras inte.

Härnäst ska vi se varför hashCode inte räcker utan en korrekt equals.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

Gratis att börja

Lär dig Java med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 104
Lektioner: 374

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Så fungerar HashMap” gratis?

Ja – hela texten till ”Så fungerar HashMap” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Java Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Java Academy innehåller totalt 4 lektioner.

Vad lär jag mig i ”Så fungerar HashMap”?

Buckets, hashning och kollisioner. Ni övar på Java Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig Java Academy?

Du behöver inga förkunskaper. Utbildningen i Java Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.

Hur lång tid tar lektionen ”Så fungerar HashMap”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här Java Academy-lektionen?

Ja. Varje Java Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

← Tillbaka till Java Academy