Een HashMap is een van de meest gebruikte data structures in Java en is bekend om zijn efficiëntie. Data in een HashMap wordt opgeslagen in de vorm van sleutel-waardeparen.

In dit artikel zal ik u in de gelegenheid stellen om HashMap’s in Java kennelijk te maken. We zullen kijken naar de algemene bewerkingen van HashMap’s en vervolgens dieper inzien hoe het interne functioneren. U zult een begrip krijgen van de hashfunctie en hoe de indexberekening plaatsvindt. We zullen ook de tijdcomplexiteiten van de bewerkingen bestuderen en daarnaast de gedragingen in een concurrerende omgeving aanraken.

Wat is een HashMap in Java?

Een HashMap implementeert de Map interface, die deel uitmaakt van de Java collectie framework. Het is gebaseerd op het concept van Hashing.

Hashing is een techniek die een input met een willekeurige grootte omzet in een vast formaat output door middel van een hashfunctie. Het gegenereerde resultaat wordt de hashcode genoemd en in Java uitgebeeld door een geheel getal waarden. Hashcodes worden gebruikt voor efficiente zoek- en opslagbewerkingen in een HashMap.

Algemene Bewerkingen

Zoals we bovenop besproken, wordt data in een HashMap opgeslagen in de vorm van sleutel-waardeparen. De sleutel is een unieke identificator en elke sleutel is geassocieerd met een waarde.

Onderstaande zijn enkele algemene bewerkingen die worden ondersteund door een HashMap. Laten we kijken wat deze methodes doen met enkele eenvoudige codevoorbeelden:

Invoer

  • Deze methode voegt een nieuw sleutel-waardepaar toe aan de HashMap.

  • De volgorde van de toevoeging van sleutel-waardeparen wordt niet behouden.

  • Tijdens de toevoeging, als een sleutel reeds aanwezig is, wordt de bestaande waarde vervangen door de nieuwe waarde die wordt doorgegeven.

  • U kunt slechts één null-sleutel toevoegen aan de HashMap, maar u kunt meerdere null-waarden hebben.

Het handtekening voor deze bewerking wordt vermeld hieronder, gevolgd door een voorbeeld:

public V put(K key, V value)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

In het code hierboven hebben we een HashMap-voorbeeld waarin we een van type String sleutel en een van type Integer waarde toevoegen.

Ophalen:

  • Haalt de waarde op die is geassocieerd met een gegeven sleutel.

  • Geeft null terug als de sleutel niet in de HashMap aanwezig is.

De handtekening voor deze bewerking wordt vermeld hieronder, gevolgd door een voorbeeld:

public V get(Object key)

Integer value = map.get("apple"); // geeft 1 terug

In het code hierboven halen we de waarde op die is geassocieerd met de sleutel apple.

Andere algemene bewerkingen zijn onder andere:

  • remove: Verwijdert het key-value paar voor de gespecificeerde sleutel. Het retourneert null als de sleutel niet gevonden wordt.

  • containsKey: Controleert of een specifieke sleutel aanwezig is in de HashMap.

  • containsValue: Controleert of de gespecificeerde waarde aanwezig is in de HashMap.

Interne Structuur van een HashMap

Intern gebruikt een HashMap een array van bucks of bins. Elke buck is een gelinkte lijst van het type Node, die gebruikt wordt om het key-value paar van de HashMap voor te stellen.

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

Boven kunt u de structuur van de Node-klasse zien, die gebruikt wordt om de key-value paren van de HashMap op te slaan.

De Node-klasse heeft de volgende velden:

  • hash: Verwijst naar de hashCode van de sleutel.

  • key: Verwijst naar de sleutel van het key-value paar.

  • value: Verwijst naar de waarde die bij de sleutel hoort.

  • next: Dient als referentie naar de volgende node.

Het HashMap is fundamenteel gebaseerd op een hash-tabelimplementatie, en zijn prestaties zijn afhankelijk van twee sleutelparameters: de initiële capaciteit en de belastingfactor. De originele javadocs van de hash-tabelklasse definiëren deze twee parameters als volgt:

  • De capaciteit is het aantal buckets in de hash-tabel, en de initiële capaciteit is simpelweg de capaciteit op het moment dat de hash-tabel wordt aangemaakt.

  • De belastingfactor is een maat voor hoe vol de hash-tabel mag worden voordat haar capaciteit automatisch wordt vergroot.

Laten we nu proberen te verstanden hoe de basisoperaties, put en get, werken in een HashMap.

Hashfunctie

Tijdens het invoegen (`put`) van een sleutel-waardepaar bereken de `HashMap` eerst de hashcode van de sleutel. De hashfunctie berekent vervolgens een geheel getal voor de sleutel. Classes kunnen de `hashCode`-methode van de `Object`-klasse gebruiken of deze methode overschrijven en hun eigen implementatie leveren. (Lees over het hash code contract hier). De hash code wordt vervolgens XOR’ed (eXclusive OR) met zijn bovenste 16 bits (h >> 16) om een meer uniforme verdeling te verkrijgen.

XOR is een bitwise bewerking die twee bits vergelijkt, resulterend in 1 als de bits verschillend zijn en 0 als ze hetzelfde zijn. In dit context helpt het uitvoeren van een bitwise XOR-bewerking tussen de hash code en zijn bovenste 16 bits (gekregen door middel van de unsigned right shift `>>>>` operator) om de bits te mengen, waardoor een meer evenwellige gehashde code ontstaat.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Hierboven zie je de statische hash methode van de `HashMap` klasse.

Het idee is om een unieke hash code voor elke sleutel te hebben, maar de hashfunctie kan dezelfde hash code voor verschillende sleutels produceren. Dit leidt tot een situatie die bekend is als een botsing. We zullen in de volgende sectie zien hoe botsingen worden behandeld.

Indexberekening

Als de hash code voor een sleutel is gegenereerd, bereken de `HashMap` een index binnen het array van buckets om vast te stellen waar het sleutel-waardepaar wordt opgeslagen. Dit doet hij met behulp van een bitwise AND-bewerking, wat een efficiënte manier is om de modulo te berekenen als de arraylengte een macht van twee is.

int index = (n - 1) & hash;

Hier berekenen we de index waarop n de lengte is van de potjeste array.

Zodra de index berekend is, wordt de sleutel dan op die index in de potjeste array opgeslagen. Echter, als meerdere sleutels uiteindelijk dezelfde index krijgen, ontstaat er een botsing. In zo’n scenario behandelt de HashMap dit op een van twee manieren:

  • Chaining/Linking: Elke potjes in het array is een lijst van knopen. Als een sleutel reeds bestaat op een bepaalde index en een andere sleutel wordt gehashed naar dezelfde index, wordt hij aan de lijst toegevoegd.

  • Treeify: Als het aantal knopen een bepaald getal overschrijdt, wordt de lijst omgezet naar een boom (Dit werd geintroduceerd in Java 8).

static final int TREEIFY_THRESHOLD = 8;

Dit is het getal dat de boomstructuur bepaalt.

Daarom is het essentieel om een goede hashfunctie te hebben die de sleutels gelijkmatig over de potjes verdeelt en de kans op botsingen minimaliseert.

De ophalen (get) en verwijderen (remove) bewerkingen werken vergelijkbaar met de invoegen (put) bewerking. Dit is hoe het werkt:

  • Ophalen (get): Berekend de hashcode met behulp van de hashfunctie -> berekend de index met behulp van de hashcode -> doorloopt de lijst of boom om het knooppunt met de overeenkomstige sleutel te vinden.

  • Verwijderen (remove): Berekent de hashcode met behulp van de hashfunctie -> berekt het index met behulp van de hashcode -> verwijdert de node uit de geënkaddeerde lijst of boom.

Tijdcomplexiteit

De basisoperaties van een HashMap, zoals put, get en remove, bieden meestal een constante tijdvoering van O(1), onder de voorwaarde dat de sleutels uniform verdeeld zijn. In gevallen waar de sleutelverdeling slecht is en veel botsingen plaatsvinden, kunnen deze operaties afnemen tot een lineaire tijdcomplexiteit van O(n).

Bij treeification, waar lange ketens van botsingen worden omgezet in ge平衡e bomen, kunnen zoekoperaties efficiënter worden met een logaritmische tijdcomplexiteit van O(log n).

Synchronisatie

De HashMap-implementatie is niet gesynchroniseerd. Als meerdere threads gelijktijdig toegang krijgen tot een HashMap-instance en de map iteratief doorlopen, en als een van de threads een structuurbewerking uitvoert (zoals het toevoegen of verwijderen van een sleutel-waardemapping) op de map, kan dit leiden tot een ConcurrentModificationException.

Om dit te voorkomen, kun je een thread-safe instantie maken door de methode Collections.synchronizedMap te gebruiken.

Conclusie

In kort, is het verstandig voor ontwikkelaars om de interne werkingen van een HashMap te begrijpen om informerende beslissingen te kunnen nemen. Het begrijpen hoe een sleutel wordt gemapped, hoe botsingen plaatsvinden en hoe ze vermeden kunnen worden helpt je de HashMap efficiënt en effectief te gebruiken.