Come funziona una tabella hash?

Una tabella hash (hash table) è una struttura dati che implementa un array associativo.

Principio di funzionamento:

1. Hashing. Per ogni chiave (key), si calcola un codice hash (hash code) usando una funzione hash (hash function). Il codice hash è un numero intero.
2. Indicizzazione. Il codice hash viene usato per determinare un indice (index) nell'array (o vettore) della struttura interna della tabella hash. Di solito, l'indice si calcola come hash_code % dimensione_array, dove dimensione_array è la dimensione dell'array.
3. Memorizzazione. All'indice trovato, si memorizza il valore (value) associato alla chiave.

Problemi e soluzioni:

• Collisioni. Chiavi diverse possono generare lo stesso codice hash e, di conseguenza, lo stesso indice nell'array. Questo si chiama collisione.
  • Metodi per risolvere le collisioni:
    • Metodo di chaining (Separate Chaining): In ogni cella dell'array si memorizza una lista (lista, vettore, ecc.) di coppie "chiave-valore". In caso di collisione, la nuova coppia viene aggiunta a questa lista. Per la ricerca tramite indice, si percorre la lista corrispondente per trovare la chiave desiderata.
    • Metodo di open addressing (Open Addressing): In caso di collisione, si cerca un'altra cella libera nell'array seguendo una regola determinata (sondaggio).
      • Sondaggio lineare (Linear Probing): Si verificano sequenzialmente le celle index + 1, index + 2, ecc., modulo la dimensione dell'array.
      • Sondaggio quadratico (Quadratic Probing): Si verificano le celle index + 1^2, index + 2^2, ecc., modulo la dimensione dell'array.
      • Double hashing (Double Hashing): Si utilizza una seconda funzione hash per determinare il passo del sondaggio.

Vantaggi:

• In media, le operazioni di inserimento, rimozione e ricerca vengono eseguite con una complessità O(1).

Svantaggi:

• Nel caso peggiore (ad esempio, molte collisioni o funzione hash scorretta), la complessità può raggiungere O(n), dove n è il numero di elementi.
• Richiede memoria aggiuntiva (ad esempio, per le liste nel metodo di chaining o per il sondaggio nell'open addressing).

Esempio di utilizzo in C++ (std::unordered_map):

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

int main() {
    // Creazione della tabella hash (unordered_map)
    std::unordered_map<std::string, int> età;

    // Inserimento di elementi
    età["Alice"] = 30;
    età["Bob"] = 25;
    età["Charlie"] = 35;

    // Ottenere il valore tramite chiave
    std::cout << "Età di Alice: " << età["Alice"] << std::endl;

    // Ricerca di un elemento
    if (età.count("Bob")) {
        std::cout << "Bob è nella mappa." << std::endl;
    }

    // Rimuovere elemento
    età.erase("Charlie");

    return 0;
}