Hashtabellen

Als 47 in een tabel met 7 buckets staat, gaat de computer direct naar bucket 47 mod 7 = 5 in plaats van de hele tabel te doorzoeken.

Een sleutel omzetten in een positie

Tot nu toe betekende een waarde vinden zoeken: maximaal n stappen in een ongesorteerde array of gelinkte lijst. Arrays kunnen elke positie echter in één stap bereiken. Wat als de sleutel zelf de positie aangaf? Bij kleine gehele sleutels, bijvoorbeeld studentnummers van 0 tot 99, kun je een array van 100 cellen bewaren en student k in cel k opslaan. De MIT-notities noemen dit een array met directe toegang. Dit faalt als de mogelijke sleutels enorm talrijk zijn, zoals telefoonnummers of woorden, omdat je niet voor elke mogelijke sleutel een cel kunt betalen.

Een hashfunctie lost dit op door elke sleutel in een klein bereik posities te persen, 0 tot m − 1. Een eenvoudige voor gehele getallen is h(k) = k mod m, de rest na delen door m. De array met m cellen is de hashtabel en de cellen heten vaak buckets. Om 47 met m = 7 op te slaan, bereken je 47 mod 7 = 5 en zet je het in bucket 5. Om 47 later te vinden bereken je hetzelfde en kijk je alleen in bucket 5.

Botsingen en ketens

Er is een probleem. Met 7 buckets en meer dan 7 mogelijke sleutels moeten sommige sleutels een bucket delen: 12, 33 en 47 geven allemaal rest 5. Dit heet een botsing en de MIT-notities wijzen erop dat dit door het duivenhokprincipe onvermijdelijk is. De gebruikelijke oplossing is ketenvorming: elke bucket bevat een lijstje, een keten, van elke sleutel die daarheen hasht. 47 vinden kost dan 1 stap voor de hash plus één vergelijking per gecontroleerde sleutel in keten 5. Als 12 en 33 ervoor staan, is dat 1 + 3 = 4 stappen.

Hoe lang zijn de ketens? Bij een gelijkmatige verdeling bevat elke keten ongeveer n/m sleutels, de beladingsfactor. Houd m ongeveer zo groot als n en de ketens blijven kort, zodat zoeken, invoegen en verwijderen gemiddeld een constant aantal stappen kosten. Het gevaar is een slechte verdeling. Als elke sleutel naar dezelfde bucket hasht, bevat één keten alle n sleutels en is de tabel niet beter dan een gelinkte lijst. Stel in het lab 7 buckets in en voeg 14, 21 en 28 in: ze komen allemaal in bucket 0.

Hashtabellen in JavaScript

Je schrijft zelden zelf een hashtabel, omdat JavaScript Map en Set heeft. De ECMAScript-specificatie zegt dat ze ‘geïmplementeerd moeten worden met hashtabellen of andere mechanismen die gemiddeld toegangstijden bieden die sublineair zijn in het aantal elementen’. Met andere woorden, map.get(key) en set.has(x) moeten sneller zijn dan de hele verzameling doorzoeken. MDN voegt toe dat een Map sleutels in invoegvolgorde bewaart en, anders dan een gewoon object, geen standaardsleutels bevat die met de jouwe kunnen botsen.

const price = new Map();
price.set("apple", 1.2);
price.set("bread", 2.5);
console.log(price.get("bread")); // 2.5, no search through the list
console.log(price.has("milk"));  // false
const seen = new Set([4, 8, 15]);
console.log(seen.has(8));        // true