Laten we nu nader kijken naar de klasse die de Map-interface implementeert — HashMap.

Deze klasse wordt veelvuldig gebruikt wanneer er over maps wordt gesproken. Je hebt al de kans gehad om met deze klasse te werken en de methoden ervan te bestuderen. Maar laten we ontdekken hoe deze klasse daadwerkelijk werkt.

Allereerst is het belangrijk te begrijpen wat een hashcode is, aangezien deze intern in een HashMap wordt gebruikt.

Hashcode

Elk object heeft een eigen hashcode, die kan worden verkregen met de Object-methode van de hashCode()-klasse. Bekijk het volgende voorbeeld:

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

Zoals te zien is, heeft het String-object met de data "Hello World!" een hashcode van "-969099747". De methode die bepaalt welke hashcode precies wordt overschreven in de String-klasse ziet er als volgt uit:

Main.java


              1234567
            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

Het String-object wordt opgesplitst in een byte-array met behulp van de methode getBytes(), waarna elke byte wordt verwerkt en toegevoegd aan de hashcode. Op deze manier wordt de hashcode maximaal uniek, wat het programma helpt dit object te identificeren.

Voor objecten van aangepaste klassen kun je ook de hashcode overschrijven door een unieke manier te definiëren waarop objecten dit nummer verkrijgen. Laten we een testklasse User maken en de methode voor de hashcode hiervoor overschrijven.

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

In de klasse User zijn er 2 attributen die ik gebruikte in de methode hashCode(). Ik heb willekeurige bewerkingen gekozen in de methode hashCode() om een maximaal willekeurig getal te verkrijgen, waardoor het uniek is voor elk User-object.

Dit is precies de hashcode. Nu gaan we bekijken hoe deze wordt gebruikt in een HashMap.

HashMap

Een HashMap kan worden voorgesteld als een array van buckets. Een bucket is een lijst waarin een element wordt opgeslagen. Aanvankelijk heeft de HashMap 16 buckets, wat de DEFAULT_INITIAL_CAPACITY is.

Wanneer je een element toevoegt aan de HashMap met de put()-methode, moet de HashMap bepalen in welke specifieke bucket dit element geplaatst moet worden. Dit gebeurt met een eenvoudige formule: keyValue.hashCode() & (n - 1), waarbij n de grootte van de array van buckets in de HashMap is. '&' is een bitwise AND-operatie, wat ook laag-niveau programmeren is, dus we gaan niet in op de details.

Het is belangrijk te begrijpen dat de HashMap de hashcode van de sleutel gebruikt om de juiste bucket te vinden. Daarom is het essentieel om een zo uniek mogelijke hashcode te creëren om botsingen te voorkomen.

Botsing

Hoe uniek een hashcode ook is, het kan toch voorkomen dat de HashMap voor twee elementen dezelfde bucket berekent. In zulke gevallen ontstaat er een botsing. Eenvoudig gezegd is een botsing een situatie waarin twee of meer elementen in dezelfde bucket terechtkomen. Ze worden daar opgeslagen als een SinglyLinkedList, die je eerder hebt geïmplementeerd.

Bekijk de volgende illustratie:

Botsing is niet wenselijk omdat het de optimalisatie beïnvloedt. Als je kijkt naar deze tabel, zie je dat in het beste geval de HashMap constante algoritmische complexiteit heeft, terwijl in het slechtste geval deze lineair is. Deze lineaire algoritmische complexiteit ontstaat door aanzienlijke botsingen. Daarom adviseren programmeurs om sleutels te gebruiken met hashcodes die zo uniek mogelijk zijn om botsingen te vermijden.

Hoe gaat HashMap om met Collisies?

HashMap pakt collisies aan door constante resizing van de bucket array. Wanneer het aantal elementen 75% van de grootte van de bucket array bereikt, start HashMap een resize door de grootte van de bucket array te verdubbelen. Daarna verdeelt het de elementen opnieuw over de nieuwe buckets met behulp van de nieuwe waarde van n in de formule.

Hierdoor is HashMap een sterk geoptimaliseerde datastructuur en wordt het vaak gebruikt als de primaire implementatie van de Map-interface.

Waarom moet je dit allemaal weten?

Dit is laag-niveau programmeertheorie die belangrijk is omdat bij het werken met grote datasets datastructuren een aanzienlijke invloed kunnen hebben op de prestaties van applicaties. Dit gebeurt wanneer deze datastructuren verkeerd worden gebruikt.

Verkeerd gebruik van datastructuren komt voor omdat programmeurs niet begrijpen hoe deze datastructuren werken. Je wilt immers een goede programmeur worden, toch?

Bovendien worden vragen over datastructuren vaak gesteld tijdens sollicitatiegesprekken.

Als je geïnteresseerd bent om dieper in te gaan op hoe HashMap onder de motorkap werkt, kun je terecht bij de Java documentatie in IntelliJ IDEA.

In IntelliJ IDEA kun je Ctrl (Windows/Linux) of Command (macOS) ingedrukt houden en op de klasnaam klikken om naar de definitie te gaan en alle beschikbare methoden te bekijken.

1. Welke van de volgende implementaties gebruikt een hashtabel om sleutel-waardeparen op te slaan?

2. Wat gebeurt er in een `HashMap` als twee sleutels dezelfde hashcode hebben?

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 2

Vraag AI

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

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?

Veeg om het menu te tonen

Laten we nu nader kijken naar de klasse die de Map-interface implementeert — HashMap.

Allereerst is het belangrijk te begrijpen wat een hashcode is, aangezien deze intern in een HashMap wordt gebruikt.

Hashcode

Elk object heeft een eigen hashcode, die kan worden verkregen met de Object-methode van de hashCode()-klasse. Bekijk het volgende voorbeeld:

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

Main.java


              1234567
            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

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

Dit is precies de hashcode. Nu gaan we bekijken hoe deze wordt gebruikt in een HashMap.

HashMap

Botsing

Bekijk de volgende illustratie:

Hoe gaat HashMap om met Collisies?

Hierdoor is HashMap een sterk geoptimaliseerde datastructuur en wordt het vaak gebruikt als de primaire implementatie van de Map-interface.

Waarom moet je dit allemaal weten?

Verkeerd gebruik van datastructuren komt voor omdat programmeurs niet begrijpen hoe deze datastructuren werken. Je wilt immers een goede programmeur worden, toch?

Bovendien worden vragen over datastructuren vaak gesteld tijdens sollicitatiegesprekken.

Als je geïnteresseerd bent om dieper in te gaan op hoe HashMap onder de motorkap werkt, kun je terecht bij de Java documentatie in IntelliJ IDEA.

In IntelliJ IDEA kun je Ctrl (Windows/Linux) of Command (macOS) ingedrukt houden en op de klasnaam klikken om naar de definitie te gaan en alle beschikbare methoden te bekijken.

1. Welke van de volgende implementaties gebruikt een hashtabel om sleutel-waardeparen op te slaan?

2. Wat gebeurt er in een `HashMap` als twee sleutels dezelfde hashcode hebben?

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 2

Werken met HashMap in Java

Hashcode

HashMap

Botsing

Hoe gaat HashMap om met Collisies?

Waarom moet je dit allemaal weten?

1. Welke van de volgende implementaties gebruikt een hashtabel om sleutel-waardeparen op te slaan?

2. Wat gebeurt er in een `HashMap` als twee sleutels dezelfde hashcode hebben?

Werken met HashMap in Java

Hashcode

HashMap

Botsing

Hoe gaat HashMap om met Collisies?

Waarom moet je dit allemaal weten?

1. Welke van de volgende implementaties gebruikt een hashtabel om sleutel-waardeparen op te slaan?

2. Wat gebeurt er in een `HashMap` als twee sleutels dezelfde hashcode hebben?

Werken met HashMap in Java

Hashcode

HashMap

Botsing

Hoe gaat HashMap om met Collisies?

Waarom moet je dit allemaal weten?

1. Welke van de volgende implementaties gebruikt een hashtabel om sleutel-waardeparen op te slaan?

2. Wat gebeurt er in een HashMap als twee sleutels dezelfde hashcode hebben?

Werken met HashMap in Java

Hashcode

HashMap

Botsing

Hoe gaat HashMap om met Collisies?

Waarom moet je dit allemaal weten?

1. Welke van de volgende implementaties gebruikt een hashtabel om sleutel-waardeparen op te slaan?

2. Wat gebeurt er in een HashMap als twee sleutels dezelfde hashcode hebben?

2. Wat gebeurt er in een `HashMap` als twee sleutels dezelfde hashcode hebben?

2. Wat gebeurt er in een `HashMap` als twee sleutels dezelfde hashcode hebben?