Come è struttita una tabella hash nel contenitore unordered_map?

unordered_map in C++ viene implementato come una tabella hash.

Principio di funzionamento:

1. Hashing: La chiave viene trasformata in un numero intero — codice hash — tramite una funzione hash.
2. Indicizzazione: Il codice hash viene usato per determinare l'indice (cestino o bucket) in un array di puntatori o liste.
3. Memorizzazione: In ogni cestino vengono memorizzate coppie chiave-valore.

Caratteristiche:

• Cestini: La tabella hash consiste in un array di cestini. Il numero di cestini può cambiare dinamicamente (rehashing) quando si raggiunge un certo fattore di carico.
• Collisioni: Chiavi diverse possono produrre lo stesso codice hash. Questo si chiama collisione. Per risolvere le collisioni, unordered_map utilizza il metodo ** chaining **: gli elementi con lo stesso hash vengono aggiunti a una lista collegata (o altra struttura dati) nel cestino corrispondente.
• Funzione hash e funzione di confronto: Per il corretto funzionamento sono necessarie due cose:
  • Una buona funzione hash, che distribuisca uniformemente le chiavi tra i cestini, minimizzando le collisioni.
  • Una funzione di equivalenza (==), per distinguere le chiavi con lo stesso codice hash nello stesso cestino.
• Prestazioni: In media, le operazioni di inserimento, rimozione e ricerca hanno complessità temporale O(1). Nel caso peggiore (ad esempio, molte collisioni o una funzione hash mal scelta), le prestazioni possono degradare a O(n), dove n è il numero di elementi.

Esempio di struttura (semplificata):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Per lista collegata nel cestino
};

struct Bucket {
  Node* head; // Puntatore all'inizio della lista
};

Bucket* buckets; // Array di cestini
size_t num_buckets;

Processo di aggiunta di un elemento:

1. Si calcola il codice hash della chiave.
2. Si determina l'indice del cestino: bucket_index = hash(key) % num_buckets.
3. Il paio chiave-valore viene aggiunto alla lista di elementi in quel cestino. Se la chiave esiste già, il valore viene aggiornato.

Processo di ricerca di un elemento:

1. Si calcola il codice hash della chiave.
2. Si determina l'indice del cestino.
3. Si attraversa la lista di elementi in quel cestino, confrontando le chiavi con quella cercata usando l'operatore ==.

Il rehashing avviene quando il numero di elementi rispetto al numero di cestini supera una soglia (fattore di carico). Durante il rehashing, viene creato un nuovo array di cestini più grande, e tutti gli elementi dei vecchi cestini vengono re-hashati e spostati in quelli nuovi.