Hoe werkt een hash-tabel?

Een hash-tabel (hash table) is een datastructuur die een associatief array implementeert.

Werking principe:

1. Hashing. Voor elke sleutel (key) wordt een hash-code (hash code) berekend met behulp van een hash-functie (hash function). De hash-code is een geheel getal.
2. Indexering. De hash-code wordt gebruikt om een index (index) in de array (of vector) van de interne structuur van de hash-tabel te bepalen. Gewoonlijk wordt de index berekend als hash_code % array_grootte, waarbij array_grootte de grootte van de array is.
3. Opslag. Op de gevonden index wordt de waarde (value) opgeslagen die aan de sleutel is gekoppeld.

Problemen en oplossingen:

• Botsingen. Verschillende sleutels kunnen dezelfde hash-code opleveren en dus dezelfde index in de array. Dit wordt een botsing genoemd.
  • Methoden om botsingen op te lossen:
    • Kettingmethode (Separate Chaining): In elke cel van de array wordt een lijst (lijst, vector, etc.) van "sleutel-waarde" paren opgeslagen. Bij een botsing wordt het nieuwe paar aan deze lijst toegevoegd. Bij het zoeken op index wordt de betreffende lijst doorlopen om de gewenste sleutel te vinden.
    • Open adressering (Open Addressing): Bij een botsing wordt gezocht naar een andere vrije cel in de array volgens een bepaalde regel (sonderen).
      • Lineair sonderen (Linear Probing): Sequentieel worden de cellen index + 1, index + 2, etc. gecontroleerd, modulo de array-grootte.
      • Kwadratisch sonderen (Quadratic Probing): De cellen index + 1^2, index + 2^2, etc. worden gecontroleerd, modulo de array-grootte.
      • Dubbel hashen (Double Hashing): Een tweede hash-functie wordt gebruikt om de stapgrootte te bepalen.

Voordelen:

• Gemiddeld worden insertie-, verwijder- en zoekbewerkingen uitgevoerd met een complexiteit van O(1).

Nadelen:

• In het slechtste geval (bijvoorbeeld veel botsingen of een slechte hash-functie) kan de complexiteit O(n) bereiken, waarbij n het aantal elementen is.
• Extra geheugen is nodig (bijvoorbeeld voor lijsten bij kettingmethode of voor het sonderen bij open adressering).

Voorbeeld van gebruik in C++ (std::unordered_map):

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Aanmaken van een hash-tabel (unordered_map)
    std::unordered_map<std::string, int> leeftijden;

    // Elementen toevoegen
    leeftijden["Alice"] = 30;
    leeftijden["Bob"] = 25;
    leeftijden["Charlie"] = 35;

    // Waarde opvragen via sleutel
    std::cout << "Leeftijd van Alice: " << leeftijden["Alice"] << std::endl;

    // Element zoeken
    if (leeftijden.count("Bob")) {
        std::cout << "Bob staat in de map." << std::endl;
    }

    // Element verwijderen
    leeftijden.erase("Charlie");

    return 0;
}