Hashtabellen uitgelegd: hashfuncties, botsingen en linear probing

Een hashtabel (hash table) bewaart sleutels zo dat je ze in gemiddeld constante tijd terugvindt. Geen lijst doorlopen, geen binair zoeken: je rekent uit waar de sleutel moet staan en kijkt daar. Elke dict in Python en elke HashMap in Java werkt zo.

Je moet dit kennen omdat het overal terugkomt. Op het tentamen vragen ze vrijwel altijd om een tabel met de hand te vullen. In sollicitatiegesprekken is "gebruik een hashmap" het antwoord op de helft van de programmeervragen. En in de praktijk wil je begrijpen waarom een opzoeking ineens traag wordt.

De hashfunctie

Een hashfunctie (hash function) zet een sleutel om in een vakjesnummer. Op Practicely gebruiken we steeds dezelfde, eenvoudige functie:

h(k) = k mod m

Hierin is m de tabelgrootte, het aantal vakjes. Bij m = 7 komt sleutel 15 in vakje 15 mod 7 = 1 en sleutel 27 in vakje 27 mod 7 = 6. De vakjes zijn genummerd van 0 tot en met m - 1.

Een goede hashfunctie verdeelt sleutels gelijkmatig over de tabel. Daarom kiest men voor m vaak een priemgetal: met m = 10 belanden alle sleutels die op een 0 eindigen in hetzelfde vakje, met m = 7 gebeurt dat veel minder snel.

Botsingen

Er zijn veel meer mogelijke sleutels dan vakjes, dus twee sleutels komen soms in hetzelfde vakje uit. Dat heet een botsing (collision). 15 en 8 hebben bij m = 7 allebei hashwaarde 1. Botsingen zijn niet te vermijden; de vraag is alleen hoe je ermee omgaat. Er zijn twee klassieke oplossingen.

Chaining

Bij chaining (separate chaining) is elk vakje een lijst. Een nieuwe sleutel komt achteraan de lijst van zijn vakje. We voegen in deze volgorde in: 15, 11, 27, 8, 20, 34 met m = 7.

Eindresultaat:

Zoeken naar 34 betekent: naar vakje 6 gaan en die lijst doorlopen. Hoe korter de lijsten, hoe sneller.

Linear probing

Bij open adressering (open addressing) staat elke sleutel direct in de tabel, zonder lijsten. De eenvoudigste variant is linear probing: is het vakje bezet, probeer dan het volgende (+1). Ben je bij het laatste vakje, dan ga je verder bij 0 (wrap-around).

Dezelfde sleutels, dezelfde volgorde, m = 7. Een leeg vakje noteren we als -.

Let op drie dingen:

• 8 botst met 15 in vakje 1 en schuift één plek op naar vakje 2.
• 20 hoort in vakje 6, dat is bezet, dus via wrap-around naar vakje 0.
• 34 hoort ook in vakje 6 en moet vijf vakjes proberen. Bezette vakjes vormen een aaneengesloten blok (cluster), en elke nieuwe sleutel die in dat blok valt, maakt het blok nog langer. Dat verschijnsel heet primary clustering en is het grote nadeel van linear probing.

Zoeken en verwijderen

Zoeken volgt exact dezelfde route als invoegen. Begin bij h(k) en schuif op tot je de sleutel vindt of een leeg vakje tegenkomt. Een leeg vakje betekent: hier zou de sleutel gestaan hebben, dus hij zit niet in de tabel.

Verwijderen is lastiger. Stel dat je 8 uit vakje 2 haalt en het vakje gewoon leeg maakt. Zoek je daarna naar 34, dan probeer je 6, 0, 1, 2 en stopt bij het lege vakje 2: "niet gevonden", terwijl 34 gewoon in vakje 3 staat. Je hebt de keten doorgeknipt.

De oplossing is een grafsteen (tombstone): een markering "hier stond iets". Hieronder genoteerd als ×.

Bij zoeken loop je door een × heen; bij invoegen mag je een × hergebruiken. Bij chaining speelt dit probleem niet: daar haal je de sleutel gewoon uit de lijst.

Load factor en rehashen

De load factor (bezettingsgraad) is

α = n / m

met n het aantal opgeslagen sleutels. In het voorbeeld hierboven is α = 6/7 ≈ 0,86. Dat is hoog, en je ziet het effect: zoeken naar 13 kost zeven stappen.

Bij linear probing moet α altijd kleiner dan 1 blijven (anders is de tabel vol) en in de praktijk ruim onder 0,7. Bij chaining kan α boven 1 komen, maar dan worden de lijsten lang.

Daarom groeit een hashtabel automatisch. Wordt α te groot, dan maak je een nieuwe, grotere tabel (vaak ongeveer twee keer zo groot) en voeg je alle sleutels opnieuw in. Dat heet rehashen (rehashing). Je kunt de oude array niet zomaar kopiëren: met een nieuwe m verandert k mod m voor bijna elke sleutel.

Rehashen we onze zes sleutels naar m = 13 (in de volgorde waarin ze in de oude tabel staan: 20, 15, 8, 34, 11, 27), dan krijg je:

Nog maar één botsing (34 en 8, allebei vakje 8) en α = 6/13 ≈ 0,46. Rehashen kost O(n), maar omdat het steeds zeldzamer gebeurt naarmate de tabel groeit, is invoegen gemiddeld over alle operaties (amortized) nog steeds O(1).

Code: hashtabel met linear probing

Een minimale hashtabel voor gehele getallen, met tombstones. Hij rehasht niet automatisch, zodat hij precies dezelfde tabellen oplevert als de voorbeelden hierboven.

LEEG = None
WEG = "×"  # tombstone


class HashTabel:
    def __init__(self, m):
        self.m = m
        self.vakjes = [LEEG] * m

    def _route(self, k):
        # alle vakjes in probeervolgorde: h(k), h(k)+1, ... met wrap-around
        start = k % self.m
        for stap in range(self.m):
            yield (start + stap) % self.m

    def zoek(self, k):
        for i in self._route(k):
            if self.vakjes[i] is LEEG:
                return -1  # leeg vakje: sleutel bestaat niet
            if self.vakjes[i] == k:
                return i
        return -1

    def voeg_toe(self, k):
        if self.zoek(k) != -1:
            return  # al aanwezig
        for i in self._route(k):
            if self.vakjes[i] is LEEG or self.vakjes[i] == WEG:
                self.vakjes[i] = k
                return
        raise OverflowError("tabel is vol")

    def verwijder(self, k):
        i = self.zoek(k)
        if i != -1:
            self.vakjes[i] = WEG  # niet LEEG, anders breekt de zoekketen


t = HashTabel(7)
for k in [15, 11, 27, 8, 20, 34]:
    t.voeg_toe(k)
print(["-" if v is LEEG else v for v in t.vakjes])
# [20, 15, 8, 34, 11, '-', 27]

import java.util.Arrays;

static class HashTabel {
    private static final int LEEG = Integer.MIN_VALUE;
    private static final int WEG = Integer.MIN_VALUE + 1; // tombstone
    private final int m;
    private final int[] vakjes;

    HashTabel(int m) {
        this.m = m;
        this.vakjes = new int[m];
        Arrays.fill(vakjes, LEEG);
    }

    private int h(int k) {
        return Math.floorMod(k, m); // ook correct voor negatieve sleutels
    }

    int zoek(int k) {
        for (int stap = 0; stap < m; stap++) {
            int i = (h(k) + stap) % m;
            if (vakjes[i] == LEEG) return -1; // leeg vakje: sleutel bestaat niet
            if (vakjes[i] == k) return i;
        }
        return -1;
    }

    void voegToe(int k) {
        if (zoek(k) != -1) return; // al aanwezig
        for (int stap = 0; stap < m; stap++) {
            int i = (h(k) + stap) % m;
            if (vakjes[i] == LEEG || vakjes[i] == WEG) {
                vakjes[i] = k;
                return;
            }
        }
        throw new IllegalStateException("tabel is vol");
    }

    void verwijder(int k) {
        int i = zoek(k);
        if (i != -1) vakjes[i] = WEG; // niet LEEG, anders breekt de zoekketen
    }
}

In Python geeft k % m voor een negatieve k altijd een uitkomst tussen 0 en m - 1. In Java is -3 % 7 gelijk aan -3; daarom gebruikt de Java-versie Math.floorMod.

In de praktijk: Python dict en Java HashMap

Je schrijft zelden je eigen hashtabel, maar je gebruikt er dagelijks een.

• Python dict en set gebruiken open adressering, maar niet met +1: de volgende plek wordt berekend uit meer bits van de hash, zodat clusters minder snel ontstaan. De tabel groeit zodra hij voor ongeveer twee derde gevuld is.
• Java HashMap gebruikt chaining. De standaard maximale load factor is 0,75; daarboven verdubbelt de tabel. Wordt één lijst langer dan acht elementen (en is de tabel groot genoeg), dan maakt Java er een gebalanceerde boom van, zodat ook het slechtste geval O(log n) blijft.

Voor objecten als sleutel roepen beide hash() of hashCode() aan. Daarom moet je in Java hashCode() overschrijven als je equals() overschrijft: twee gelijke objecten moeten in hetzelfde vakje uitkomen, anders vindt de map ze niet terug.

Het opzoeken van een sleutel in een dict is dus geen lineair zoeken zoals in zoeken, maar een berekening. Dat maakt het verschil tussen een O(n²)- en een O(n)-oplossing bij veel sollicitatievragen (zie complexiteit).

Complexiteit

Het slechtste geval treedt op als (bijna) alle sleutels dezelfde hashwaarde krijgen: dan heb je één lange lijst (chaining) of één lang cluster (probing), en ben je terug bij lineair zoeken. Met een goede hashfunctie en een lage load factor is dat in de praktijk zeldzaam.

Veelgemaakte fouten op het tentamen

1. Wrap-around vergeten. Valt een sleutel bij m = 7 op vakje 6 en dat is bezet, dan is de volgende poging vakje 0, niet vakje 7.
2. Stoppen bij het eerste bezette vakje tijdens zoeken. Je stopt pas bij de sleutel zelf of bij een leeg vakje. Een bezet vakje met een andere sleutel betekent: doorzoeken.
3. Bij chaining vooraan invoegen. In onze conventie komt een nieuwe sleutel achteraan de lijst: 27 → 20 → 34, niet 34 → 20 → 27.
4. Een verwijderd vakje leeg maken bij linear probing. Daarmee knip je zoekketens door. Gebruik een tombstone.
5. Bij rehashen de oude posities kopiëren. Na het vergroten moet je elke sleutel opnieuw hashen met de nieuwe m.

Samenvatting

• Een hashtabel berekent de plek van een sleutel met h(k) = k mod m; zoeken en invoegen kosten gemiddeld O(1).
• Botsingen los je op met chaining (lijst per vakje, achteraan toevoegen) of linear probing (volgende vakje, met wrap-around).
• Bij linear probing stopt zoeken pas bij de sleutel of een leeg vakje; verwijderen gaat met een tombstone.
• Houd de load factor α = n/m laag; wordt hij te hoog, dan rehash je naar een grotere tabel.
• Slechtste geval is O(n), als alle sleutels op dezelfde plek uitkomen.