Using Hashmaps in JavaScript: Het Mappen van Keys naar Values in Datastructuren

Wat zijn hashmaps?

Hashmaps zijn een datastructuur die sleutel-waardeparen opslaat, waarbij elke sleutel uniek is en naar een waarde verwijst. De sleutel wordt gebruikt om de waarde te indexeren, wat het snel ophalen van de bijbehorende waarde mogelijk maakt. Hashmaps gebruiken een hashfunctie om een index te berekenen voor het opslaan en ophalen van waarden. De hashfunctie neemt de sleutel als invoer en genereert een unieke hashcode, die vervolgens wordt gebruikt om de index te bepalen waar de waarde in de array of bucket wordt opgeslagen.

Hashmaps versus JavaScript-objecten

JavaScript-objecten kunnen ook sleutel-waardeparen opslaan, vergelijkbaar met hashmaps. Hashmaps bieden echter voordelen ten opzichte van objecten:

1. Sleuteltypen: Hashmaps maken het mogelijk om elk datatype als sleutel te gebruiken, inclusief objecten, arrays en functies. JavaScript-objecten zijn beperkt tot het gebruik van alleen strings en symbolen als sleutels.

   const hashmap = new Map();
   hashmap.set({ name: 'John' }, 25);
   hashmap.set([1, 2, 3], 'array');
   
   const obj = {};
   obj[{ name: 'John' }] = 25; // Ongeldig: Objecten kunnen niet als sleutels in objecten worden gebruikt

2. Volgorde behouden: Hashmaps behouden de invoegvolgorde van elementen, wat betekent dat de volgorde waarin sleutel-waardeparen aan de hashmap worden toegevoegd, bewaard blijft. JavaScript-objecten garanderen geen volgorde van hun eigenschappen.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   hashmap.set('c', 3);
   console.log(Array.from(hashmap.keys())); // Output: ['a', 'b', 'c']
   
   const obj = { a: 1, b: 2, c: 3 };
   console.log(Object.keys(obj)); // Output: ['a', 'b', 'c'] (Niet gegarandeerd)

3. Grootte bijhouden: Hashmaps bieden methoden zoals size() om het aantal elementen in de hashmap op te halen. Bij JavaScript-objecten zou je handmatig het aantal eigenschappen moeten bijhouden of Object.keys(obj).length gebruiken om de grootte te bepalen.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   console.log(hashmap.size); // Output: 2
   
   const obj = { a: 1, b: 2 };
   console.log(Object.keys(obj).length); // Output: 2

Tijdscomplexiteit van hashmap-operaties

Een van de belangrijkste voordelen van hashmaps is hun tijdscomplexiteit voor basisoperaties. Hashmaps bieden een constante tijdscomplexiteit, aangeduid als O(1), voor de volgende operaties:

1. Invoegen: Het toevoegen van een nieuw sleutel-waardepaar aan de hashmap is een O(1)-operatie. De hashfunctie wordt gebruikt om de index te berekenen en het sleutel-waardepaar wordt op die index in de array of bucket opgeslagen.

2. Verwijderen: Het verwijderen van een sleutel-waardepaar uit de hashmap is ook een O(1)-operatie. De hashfunctie wordt gebruikt om de index te lokaliseren waar het sleutel-waardepaar is opgeslagen, en vervolgens wordt het van die index verwijderd.

3. Opzoeken: Het ophalen van de waarde die bij een gegeven sleutel hoort, is een O(1)-operatie. De hashfunctie wordt gebruikt om de index op basis van de sleutel te berekenen, en de waarde kan op die index worden opgevraagd.

const cache = new Map();

function fetchData(key) {
  if (cache.has(key)) {
    return cache.get(key); // Haal gegevens op uit cache (O(1) opzoeken)
  } else {
    const data = fetchFromAPI(key); // Haal gegevens op van API
    cache.set(key, data); // Sla gegevens op in cache (O(1) invoegen)
    return data;
  }
}

Een hashmap maken

Om een nieuwe hashmap te maken, gebruik je de new Map()-constructor. Dit maakt een lege hashmap om sleutel-waardeparen op te slaan.

const myHashmap = new Map();

Bijvoorbeeld, om een hashmap te maken voor het opslaan van studentgegevens:

const studentMap = new Map();

Sleutel-waardeparen toevoegen

Om een nieuw sleutel-waardepaar aan de hashmap toe te voegen, gebruik je de set()-methode. Deze heeft twee argumenten: de sleutel en de waarde.

myHashmap.set('name', 'John');
myHashmap.set('age', 25);

In het bovenstaande voorbeeld voegen we twee sleutel-waardeparen toe aan de myHashmap: 'name' verwijst naar 'John' en 'age' verwijst naar 25.

Laten we wat studentgegevens toevoegen aan onze studentMap:

studentMap.set('1', { name: 'John', age: 20, major: 'Computer Science' });
studentMap.set('2', { name: 'Alice', age: 22, major: 'Mathematics' });
studentMap.set('3', { name: 'Bob', age: 21, major: 'Physics' });

Waarden ophalen

Om de waarde voor een gegeven sleutel op te halen, gebruik je de get()-methode. Deze neemt de sleutel als argument en retourneert de waarde.

const name = myHashmap.get('name');
console.log(name); // Output: 'John'

In dit voorbeeld halen we de waarde op voor de sleutel 'name' uit de myHashmap, wat 'John' is.

Om de gegevens van een specifieke student uit studentMap op te halen:

const student = studentMap.get('2');
console.log(student); // Output: { name: 'Alice', age: 22, major: 'Mathematics' }

Controleren of een sleutel bestaat

Om te controleren of een sleutel bestaat in de hashmap, gebruik je de has()-methode. Deze neemt de sleutel als argument en retourneert een boolean-waarde.

const hasAge = myHashmap.has('age');
console.log(hasAge); // Output: true

Hier controleren we of de sleutel 'age' bestaat in de myHashmap met behulp van de has()-methode, die true retourneert.

Controleren of een student met ID '4' bestaat in studentMap:

const hasStudent = studentMap.has('4');
console.log(hasStudent); // Output: false

Sleutel-waardeparen verwijderen

Om een sleutel-waardepaar uit de hashmap te verwijderen, gebruik je de delete()-methode. Deze neemt de sleutel als argument en verwijdert het sleutel-waardepaar uit de hashmap.

myHashmap.delete('age');
console.log(myHashmap.has('age')); // Output: false

In dit voorbeeld verwijderen we het sleutel-waardepaar met de sleutel 'age' uit de myHashmap met behulp van de delete()-methode. Na verwijdering retourneert has('age') false.

Een student verwijderen uit studentMap:

studentMap.delete('1');
console.log(studentMap.has('1')); // Output: false

De grootte van de hashmap ophalen

Om het aantal sleutel-waardeparen in de hashmap op te halen, gebruik je de size-eigenschap. Deze retourneert de grootte van de hashmap.

console.log(myHashmap.size); // Output: 1

Hier krijgen we toegang tot de size-eigenschap van de myHashmap, die 1 retourneert, wat aangeeft dat er één sleutel-waardepaar in de hashmap zit.

Het aantal studenten in studentMap ophalen:

console.log(studentMap.size); // Output: 2

Overzicht hashmap-operaties

Dit zijn de basisoperaties die je kunt uitvoeren op een hashmap met behulp van het Map-object van JavaScript. Het Map-object biedt een manier om met sleutel-waardeparen te werken en biedt methoden om de gegevens in de hashmap te manipuleren en op te vragen.

Het Map-object behoudt de volgorde van sleutel-waardeparen, wat betekent dat wanneer je over de hashmap itereert met methoden zoals forEach() of de for...of-lus, de sleutel-waardeparen worden benaderd in de volgorde waarin ze zijn toegevoegd.

De forEach()-methode

De forEach()-methode is ingebouwd in het Map-object. Het stelt je in staat om over elk sleutel-waardepaar in de hashmap te itereren. Het gebruikt een callback-functie die voor elk paar wordt uitgevoerd.

De callback-functie krijgt drie parameters:

1. value: De waarde van het huidige paar.
2. key: De sleutel van het huidige paar.
3. map: De hashmap waarop forEach() werd aangeroepen.

const shoppingCart = new Map();
shoppingCart.set('shirt', 25);
shoppingCart.set('pants', 50);
shoppingCart.set('shoes', 75);

let totalPrice = 0;

shoppingCart.forEach((price) => {
  totalPrice += price;
});

console.log(`Total Price: $${totalPrice}`);

Total Price: $150

De for...of-lus

Je kunt ook een for...of-lus gebruiken om over een hashmap te itereren. De for...of-lus werkt met itereerbare objecten zoals arrays, strings en maps.

Wanneer je for...of met een hashmap gebruikt, retourneert elke lus een array met het [key, value]-paar.

const studentMap = new Map();
studentMap.set('1', { name: 'John', age: 20, major: 'Computer Science' });
studentMap.set('2', { name: 'Alice', age: 22, major: 'Mathematics' });
studentMap.set('3', { name: 'Bob', age: 21, major: 'Physics' });

for (const [id, student] of studentMap) {
  console.log(`Student ID: ${id}`);
  console.log(`Name: ${student.name}`);
  console.log(`Age: ${student.age}`);
  console.log(`Major: ${student.major}`);
  console.log('---');
}

Student ID: 1
Name: John
Age: 20
Major: Computer Science
---
Student ID: 2
Name: Alice
Age: 22
Major: Mathematics
---
Student ID: 3
Name: Bob
Age: 21
Major: Physics
---

Hashmap-iteratie visualiseren

Hier is een diagram dat laat zien hoe itereren over een hashmap werkt:

Het diagram toont de hashmap en het itereren over elk sleutel-waardepaar. Voor elk paar verwerken we het op basis van wat we moeten doen, zoals berekeningen, vergelijkingen of andere operaties.

Zowel forEach() als for...of stellen je in staat om over de sleutel-waardeparen van een hashmap te itereren in JavaScript. Welke je gebruikt, hangt af van je specifieke behoeften. forEach() is handig wanneer je iets wilt doen voor elk paar, terwijl for...of nuttig is wanneer je zowel de sleutels als waarden in elke lus nodig hebt.

Houd er rekening mee dat de volgorde van iteratie in een hashmap gebaseerd is op de volgorde waarin de paren zijn toegevoegd. Het Map-object van JavaScript behoudt deze volgorde.

Itereren over hashmaps komt vaak voor bij het werken met sleutel-waardeparen, en JavaScript heeft deze methoden om het gemakkelijker en sneller te maken. Voor meer informatie over Map-objecten en iteratie, bekijk de MDN Web Docs.

Wat zijn botsingen?

In een hashmap gebeuren botsingen wanneer twee of meer sleutels naar dezelfde index hashen. Dit betekent dat meerdere sleutel-waardeparen op dezelfde positie in de array of bucket moeten worden opgeslagen. Als dit niet goed wordt afgehandeld, kunnen botsingen leiden tot het overschrijven van gegevens of traag ophalen van waarden.

Hier is een voorbeeld van een botsing in een hashmap:

In dit voorbeeld hashen zowel de sleutels 'John' als 'Alice' naar dezelfde index (Index 0), wat een botsing veroorzaakt.

Als botsingen niet worden opgelost, kunnen deze problemen optreden:

1. Gegevens overschrijven: Als een nieuw sleutel-waardepaar naar dezelfde index hasht als een bestaand paar, kan het bestaande paar worden overschreven, wat tot gegevensverlies leidt.

2. Traag ophalen: Wanneer botsingen optreden, wordt het vinden van waarden trager omdat de hashmap meer stappen moet doen om de juiste waarde te vinden tussen de gebotste paren.

Om deze problemen op te lossen, gebruiken hashmaps technieken voor het afhandelen van botsingen.

Manieren om botsingen af te handelen

Er zijn twee hoofdmanieren om botsingen in hashmaps af te handelen:

1. Separate Chaining

• Elke index van de array of bucket van de hashmap slaat een gelinkte lijst van sleutel-waardeparen op.
• Wanneer een botsing optreedt, wordt het nieuwe sleutel-waardepaar toegevoegd aan de gelinkte lijst op die index.
• Het vinden van een waarde betekent door de gelinkte lijst op de gehashte index gaan om het gewenste sleutel-waardepaar te vinden.

2. Open Addressing

• Open addressing gebruikt geen gelinkte lijsten om botsingen af te handelen. In plaats daarvan zoekt het naar de volgende vrije index in de array wanneer een botsing optreedt.
• Er zijn verschillende manieren om de volgende index te vinden, zoals lineair probing, kwadratisch probing en dubbel hashen.
• Wanneer een botsing gebeurt, gebruikt de hashmap de probing-methode om de volgende lege plek in de array te vinden om het sleutel-waardepaar op te slaan.

Best practices voor het gebruik van hashmaps

1. Kies een goede hashfunctie die botsingen vermindert en sleutels gelijkmatig verspreidt.
2. Denk na over het verwachte aantal elementen en gewenste prestaties bij het kiezen van de startgrootte van de hashmap.
3. Wees je bewust van hoe botsingen de snelheid van hashmap-operaties kunnen beïnvloeden, vooral bij veel botsingen.
4. Gebruik separate chaining of open addressing op basis van wat je toepassing nodig heeft, waarbij je rekening houdt met zaken als geheugengebruik en ophalensnelheid.