Ik denk dat het nuttiger zal zijn als ik HashMaps in het Engels uitleg.

Wat is een HashMap?

Een HashMap is een datastructuur die in staat is om bepaalde sleutels aan bepaalde waarden te koppelen. De sleutels en waarden kunnen van alles zijn. Als ik bijvoorbeeld een spel zou maken, zou ik elke gebruikersnaam kunnen koppelen aan een vriendenlijst, voorgesteld door een Lijst van Strings.

Waarom een HashMap gebruiken?

HashMaps zijn veel sneller voor het ophalen van gegevens dan arrays en gelinkte lijsten. Een gesorteerde array kan een bepaalde waarde vinden in O(log n) met binair zoeken. Een HashMap kan echter in O(1) controleren of hij een bepaalde sleutel bevat. Alle sleutels moeten uniek zijn.

Hoe werken HashMaps?

HashMaps gebruiken op de achtergrond een array. Elk element in de array is een andere gegevensstructuur (meestal een gekoppelde lijst of een binaire zoekboom). De HashMap gebruikt een functie op de sleutel om te bepalen waar de waarde van de sleutel in de array moet worden geplaatst. Bijvoorbeeld, als mijn HashMap Strings accepteert… dan kunnen mogelijke hash-functies zijn:

A. Return the ASCII value of the first letter.B. Return the sum of the ASCII values of every character in the String.C. Return the ASCII value of the last character in the String.

De geretourneerde waarde bepaalt de index waarin de waarde in de array komt.

Maar wacht! Er is een probleem!

Het is mogelijk dat de geretourneerde waarde buiten de grenzen van de array valt. Daarom moeten we de geretourneerde waarde modificeren met de lengte van de arrays.

return Math.abs(number%hashMapArray.length);

Collisions:

Is het niet mogelijk dat meerdere sleutels ervoor zorgen dat de hash-functie dezelfde index genereert? Ja. Als we bijvoorbeeld de eerste hash-functie hierboven zouden gebruiken in een hash-map van strings…zullen twee strings die met dezelfde letter beginnen dezelfde array-index krijgen.

Dit wordt een botsing genoemd.

Hoe gaan we met botsingen om?

Een botsingsafhandelingstechniek heet Chaining. Omdat elk element in de array een gelinkte lijst (of vergelijkbare datastructuur) is, zullen meerdere sleutels die dezelfde hashwaarde hebben in dezelfde gelinkte lijst of “bucket” worden geplaatst. Daarna is de hash map in staat om waarden op te halen door de hash code te berekenen met de hash functie, en de betreffende gelinkte lijst te doorzoeken om te zien of die een waarde met dezelfde sleutel bevat.

Een goede hash-functie moet worden geschreven om botsingen te voorkomen.

Voordelen van Chaining:

-Array kan niet overlopen

-Data kan gemakkelijk worden verwijderd

Nadelen van Chaining:

-Mag een performance hit lijden als buckets zeer lange gelinkte lijsten bevatten.

Het totale aantal entries op het aantal buckets wordt de load factor genoemd. Als de belastingsfactor te laag is, wordt er veel ruimte verspild. Als de belastingsfactor te hoog is, gaat het voordeel van hashing verloren. Een goed compromis voor de belastingsfactor is .75