Java Academy · Les

Hoe HashMap werkt

Buckets, hashing en botsingen

Les 1 van 413 stappen

Hoe HashMap werkt is een gratis Java Academy-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Java Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Java Academy bevat in totaal 4 lessen.

Wat HashMap opslaat

Een HashMap slaat sleutel-waardeparen op en biedt gemiddeld O(1)-tijd voor opzoeken, invoegen en verwijderen.

Intern bevat de map een array die de tabel wordt genoemd. Elke positie in deze array heet een bucket.

De sleutel bepaalt in welke bucket een item terechtkomt.
De waarde krijg je terug wanneer je de sleutel opzoekt.

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

De sleutel hashen

Wanneer je put(key, value) aanroept, roept de map key.hashCode() aan om een int te verkrijgen.

HashMap verspreidt die bits vervolgens met een interne functie, zodat zelfs slechte hashcodes over de buckets worden verdeeld.

Het uiteindelijke getal wordt met hash & (table.length - 1) verkleind tot een bucketindex.
De tabel heeft altijd een lengte die een macht van twee is, dus het masker werkt.

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

Buckets in actie

Elke bucket kan meer dan één item bevatten. Wanneer twee sleutels naar dezelfde bucket verwijzen, is dat een botsing.

Botsingen zijn normaal en te verwachten. HashMap handelt ze af door items in de bucket aan elkaar te koppelen.

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

Botsingen en kettingvorming

Vóór Java 8 stonden alle botsende items in een enkelvoudig gekoppelde lijst in de bucket.

Bij het opzoeken wordt de lijst doorlopen en equals() aangeroepen totdat de overeenkomende sleutel is gevonden.

Weinig botsingen: nog steeds effectief O(1).
Veel botsingen in één bucket: voor die bucket neemt de efficiëntie af richting O(n).

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

Waarom FB en Ea botsen

De tekenreeksen "FB" en "Ea" hebben in Java dezelfde hashCode(). Dit is een klassiek voorbeeld van een botsing.

Zelfs met identieke hashcodes houdt de map ze gescheiden, omdat equals() ze binnen de bucket van elkaar onderscheidt.

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

Vullingsfactor

De vullingsfactor bepaalt hoe vol de tabel wordt voordat deze groeit. De standaardwaarde is 0.75.

Bij capaciteit 16 en een vullingsfactor van 0.75 wordt het formaat aangepast vanaf 12 items.
Een lagere vullingsfactor verspilt geheugen, maar vermindert botsingen.
Een hogere vullingsfactor bespaart geheugen, maar vergroot het aantal botsingen.

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

De tabel vergroten

Wanneer het aantal items groter wordt dan capacity * loadFactor, verdubbelt de tabel in omvang.

Elk bestaand item wordt opnieuw gehasht in de nieuwe, grotere tabel. Dit is een dure bewerking, dus vooraf dimensioneren is belangrijk voor grote mappen.

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

Vooraf dimensioneren voor betere prestaties

Als je ongeveer weet hoeveel items je opslaat, geef je een initiële capaciteit op om herhaald aanpassen van het formaat te voorkomen.

Vuistregel: initiële capaciteit = 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-sleutels en -waarden

HashMap staat één null-sleutel en meerdere null-waarden toe.

De null-sleutel gaat altijd naar bucket 0 (de hashwaarde ervan wordt behandeld als 0).
Gebruik getOrDefault om onduidelijkheid tussen een ontbrekende sleutel en een null-waarde te voorkomen.

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

De volgorde van doorlopen is niet gegarandeerd

HashMap doet geen enkele toezegging over de volgorde waarin items worden doorlopen. De volgorde hangt af van hashcodes en de indeling van de buckets.

Als je een voorspelbare volgorde nodig hebt, gebruik je LinkedHashMap (volgorde van invoegen) of TreeMap (gesorteerde volgorde).

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

Het pad van get() samengevat

Een opzoekactie verloopt in deze stappen:

Bereken hashCode() en verspreid de bits.
Gebruik een masker om de bucketindex te vinden.
Loop door de bucket en vergelijk sleutels met equals().
Geef de overeenkomende waarde terug, of null.

Een goede hashCode en een correcte equals houden elke stap snel.

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

Korte controle

Test je begrip van hoe HashMap een bucket vindt.

Beantwoord dit in de interactieve les

Samenvatting

Je hebt geleerd hoe HashMap onder de motorkap werkt:

Sleutels worden gehasht en aan buckets toegewezen.
Botsingen worden afgehandeld door vermeldingen in een bucket aan elkaar te koppelen.
De beladingsfactor (0.75) zorgt voor verdubbeling en opnieuw hashen.
Door de map vooraf de juiste grootte te geven, voorkom je dure aanpassingen, en de iteratievolgorde is niet gegarandeerd.

Vervolgens zie je waarom hashCode alleen niet voldoende is zonder een correcte 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 beginnen

Leer Java met een AI-tutor — gratis

Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.

Cursussen: 104
Lessen: 374

Gratis beginnen met leren Bekijk de volledige cursus

Veelgestelde vragen

Is de les “Hoe HashMap werkt” gratis?

Ja — de volledige tekst van “Hoe HashMap werkt” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Java Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Java Academy bevat in totaal 4 lessen.

Wat leer ik in “Hoe HashMap werkt”?

Buckets, hashing en botsingen Je oefent met Java Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.

Heb ik ervaring nodig om met Java Academy te beginnen?

Ervaring vooraf is niet nodig. Java Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.

Hoe lang duurt de les “Hoe HashMap werkt”?

De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.

Kan ik code schrijven en uitvoeren in deze les over Java Academy?

Ja. Elke les over Java Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.

Alle lessen in deze cursus

← Terug naar Java Academy