Tabelle Hash

1. Cos'è una Tabella Hash?

Una Tabella Hash (o dizionario) è una struttura dati che implementa un tipo di dato astratto associativo, in grado di mappare delle chiavi a dei valori. L'elemento chiave viene elaborato da una funzione di hash ($h(key)$) che restituisce un indice numerico intero, corrispondente alla posizione all'interno di un vettore (la tabella) in cui memorizzare il valore associato.

Grazie a questo meccanismo, le operazioni di inserimento, ricerca e cancellazione vantano una complessità temporale nel caso medio pari a $\mathcal{O}(1)$.

2. Funzione di Hash e Gestione delle Collisioni

Una buona funzione di hash deve essere deterministica, veloce da calcolare e capace di distribuire le chiavi in modo uniforme per ridurre al minimo le collisioni (situazioni in cui due chiavi differenti generano lo stesso indice hash). Poiché il numero di chiavi possibili supera quasi sempre la dimensione della tabella, è fondamentale adottare strategie di risoluzione:

Concatenamento (Chaining): Ogni cella della tabella punta a una lista collegata (o vettore dinamico) che raccoglie tutti gli elementi che collidono sullo stesso indice.
Indirizzamento Aperto (Open Addressing): In caso di collisione, si cerca una cella alternativa libera all'interno della stessa tabella utilizzando tecniche di scansione (es. esplorazione lineare o quadratica).

                // Esempio basilare di Tabella Hash con concatenamento in C++
                #include <vector>
                #include <list>
                #include <string>
                #include <iostream>

                class SimpleHashTable {
                int capacity;
                std::vector<std::list<std::pair<std::string, int>>> table;

                int hashFunction(std::string key) {
                int hashVal = 0;
                for (char ch : key) {
                hashVal = (hashVal * 31 + ch) % capacity;
                }
                return hashVal;
                }

                public:
                SimpleHashTable(int cap) : capacity(cap), table(cap) {}

                void insert(std::string key, int value) {
                int idx = hashFunction(key);
                for (auto& pair :
                table[idx]) {
                if (pair.first == key) {
                pair.second = value;
                return;
                }
                }
                table[idx].push_back({key, value});
                }
                };
            

3. Simulatore Interattivo: Calcolo Indice Hash e Fattore di Carico

Verifica il comportamento del calcolo di hash e l'impatto del fattore di carico ($\alpha = \frac{N}{M}$) sulla stabilità della tabella.

hash-engine@nexus-core:~# Hash Table Simulation

Stringa Chiave:

Dimensione Tabella ($M$):

> Inserisci una chiave e la dimensione della tabella per testare la funzione di dispersione.

1. Cos'è una Tabella Hash?

2. Funzione di Hash e Gestione delle Collisioni

3. Simulatore Interattivo: Calcolo Indice Hash e Fattore di Carico

Gestione della Privacy e dei Cookie