Hoe is een hash-tabel opgebouwd in de container…

unordered_map in C++ wordt geïmplementeerd als een hash-tabel.

Werking principe:

Hashing: De sleutel wordt omgezet in een geheel getal — hash-code — met behulp van een hash-functie.
Indexering: De hash-code wordt gebruikt om de index (emmer of bucket) in een array van pointers of lijsten te bepalen.
Opslag: In elke emmer worden paren sleutel-waarde opgeslagen.

Kenmerken:

Emmers: De hash-tabel bestaat uit een array van emmers. Het aantal emmers kan dynamisch worden aangepast (rehashing) wanneer een bepaalde belastingfactor wordt bereikt.
Botsingen: Verschillende sleutels kunnen dezelfde hash-code geven. Dit wordt een botsing genoemd. Om botsingen op te lossen, gebruikt unordered_map de methode ** chaining **: elementen met dezelfde hash worden toegevoegd aan een gekoppelde lijst (of andere datastructuur) in de betreffende emmer.
Hash-functie en vergelijkingsfunctie: Voor correct functioneren zijn twee dingen nodig:
- Een goede hash-functie die de sleutels gelijkmatig over de emmers verdeelt, om botsingen te minimaliseren.
- Een gelijkheidsfunctie (==), om sleutels met dezelfde hash-code in één emmer te onderscheiden.
Prestaties: Gemiddeld hebben invoeg-, verwijder- en zoekbewerkingen een tijdscomplexiteit van O(1). In het slechtste geval (bijvoorbeeld veel botsingen of een slecht gekozen hash-functie) kan de prestatie afnemen tot O(n), waarbij n het aantal elementen is.

Voorbeeld van een structuur (vereenvoudigd):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Voor gekoppelde lijst in emmer
};

struct Bucket {
  Node* head; // Pijl op het begin van de lijst
};

Bucket* buckets; // Array van emmers
size_t num_buckets;

Proces van het toevoegen van een element:

De hash-code van de sleutel wordt berekend.
De index van de emmer wordt bepaald: bucket_index = hash(key) % num_buckets.
Het paar sleutel-waarde wordt toegevoegd aan de lijst in die emmer. Als de sleutel al bestaat, wordt de waarde bijgewerkt.

Proces van het zoeken van een element:

De hash-code van de sleutel wordt berekend.
De index van de emmer wordt bepaald.
De lijst in die emmer wordt doorlopen, waarbij de sleutels worden vergeleken met de gezochte sleutel met behulp van ==.

Rehashing gebeurt wanneer het aantal elementen in verhouding tot het aantal emmers een drempel overschrijdt (belastingfactor). Tijdens rehashing wordt een nieuwe, grotere array van emmers gemaakt, en alle elementen uit de oude emmers worden opnieuw gehasht en naar de nieuwe verplaatst.

Hoe is een hash-tabel opgebouwd in de container unordered_map?