Programmazione · concetti · strutture dati
Cos'è una hash table?
Una hash table (chiamata anche hash map) è una struttura dati che memorizza coppie chiave-valore e ti permette di trovare qualsiasi valore tramite la sua chiave in, mediamente, tempo costante - indipendentemente da quanti dati contiene. È una delle strutture più utili in tutta la programmazione ed è ciò che alimenta i dizionari e le map integrati in quasi ogni linguaggio. Una volta capito come funziona, molti momenti del tipo "come fa a essere così veloce?" trovano una spiegazione.
Il problema che risolve
Immagina di memorizzare una rubrica telefonica come un semplice elenco. Per trovare una persona, potresti dover scorrere ogni voce - un lavoro lento che diventa più lento man mano che la rubrica cresce, un'operazione O(n). La promessa di una hash table è diversa: dagli la chiave e salta più o meno direttamente al valore, senza scorrere. Questa è la differenza tra controllare ogni voce e sapere esattamente dove cercare.
Come funziona: la hash function e i bucket
Sotto il cofano, una hash table è supportata da un array di slot chiamati bucket. L'ingrediente magico è la hash function: prende la tua chiave e la trasforma in un numero, che viene mappato a un indice in quell'array.
index = hash(key) % number_of_bucketsPer memorizzare un valore, fai l'hash della chiave per ottenere un indice e collochi il valore in quel bucket. Per rileggerlo, fai di nuovo l'hash della stessa chiave, atterri sullo stesso indice e prendi il valore. Poiché calcolare l'hash e indicizzare un array sono entrambi passaggi veloci e a costo fisso, le ricerche non diventano più lente man mano che la table cresce. Questo è tutto il trucco.
Collisioni e come si gestiscono
Due chiavi diverse possono avere lo stesso hash e finire nello stesso bucket. Questo si chiama collisione, e ogni hash table reale deve gestirla. Ci sono due strategie comuni:
- Chaining: ogni bucket contiene una piccola lista, e le voci in collisione vengono memorizzate insieme in quella lista. Le ricerche controllano poi la lista (di solito molto corta) nel bucket giusto.
- Open addressing: se un bucket è occupato, la table cerca lo slot libero successivo secondo una regola fissa, e le ricerche seguono la stessa regola.
Con una buona hash function e abbastanza bucket, le collisioni restano rare e quelle liste restano minuscole, così le ricerche rimangono veloci.
E le prestazioni?
È qui che le hash table brillano, ed è qui che sta l'onesta avvertenza. In media, inserimento, ricerca ed eliminazione sono tutti O(1) - tempo costante. Nel caso peggiore, se una cattiva hash function o un input ostile scarica ogni chiave in un solo bucket, quelle operazioni degradano a O(n), perché torni a scorrere una singola lista lunga. Le buone implementazioni evitano questo usando hash function solide e facendo il ridimensionamento (rehashing in un array più grande) quando la table diventa troppo piena, il che mantiene le prestazioni a un O(1) ammortizzato. Se vuoi un ripasso su questa notazione, vedi la nostra guida alla notazione Big O.
Dove ne usi già una
Usi le hash table di continuo, spesso senza nominarle. I tipi dizionario e map nella maggior parte dei linguaggi sono hash table sotto il cofano: il dict di Python, la HashMap di Java, la Map di JavaScript e gli oggetti, l'Hash di Ruby, la map di Go. Sono anche lo strumento di riferimento per le cache, per la de-duplicazione degli elementi e per il conteggio delle occorrenze. La classica ottimizzazione che trasforma una ricerca lenta con cicli annidati in una veloce - passando da O(n²) a O(n) - viene quasi sempre fatta sostituendo scansioni ripetute con una ricerca in una hash table.
I compromessi
- Veloce, ma non ordinata. Una hash table di base non mantiene le chiavi in alcun ordine, né ordinato né di inserimento (anche se alcune versioni dei linguaggi aggiungono un ordinamento in cima).
- Usa memoria extra. Mantenere rare le collisioni significa mantenere bucket di riserva, quindi una hash table baratta un po' di memoria in cambio della sua velocità.
- Il caso peggiore è reale. L'O(1) è una media; un input avversario può forzare il percorso lento, il che conta per il codice sensibile alla sicurezza.
FAQ
Una hash table è la stessa cosa di un dizionario? In termini quotidiani, sì - un dizionario o una map è l'idea generale (chiave a valore), e una hash table è il modo più comune per implementarla. Quando qualcuno dice "dict" di Python o "HashMap" di Java, sta usando una hash table.
Perché la ricerca è O(1) in media? Perché calcoli l'hash della chiave e indicizzi direttamente in un array, invece di scorrere le voci. Entrambi i passaggi richiedono tempo costante indipendentemente da quanti elementi sono memorizzati, quindi il costo medio non cresce con i dati.
Cos'è una collisione? Quando due chiavi diverse hanno lo stesso hash e finiscono nello stesso bucket. È normale e prevista; le hash table la gestiscono con chaining o open addressing, e la mantengono rara con una buona hash function e il ridimensionamento.
Quando non dovrei usare una hash table? Quando hai bisogno che le chiavi siano tenute in ordine, o per query ordinate su intervalli - una struttura basata su albero si adatta meglio. Anche quando la memoria è estremamente limitata, poiché le hash table mantengono spazio di riserva per restare veloci.