Cerca una chiave in un dict Python con dieci elementi e ci metti lo stesso tempo che cercarla in un dict con dieci milioni. Non è un caso dovuto a un linguaggio veloce. Il dict di Python, la HashMap di Java e la Map di JavaScript sono tutte hash table, e l’intero design esiste per far girare lookup, inserimento e cancellazione in O(1) in media. La notazione Big O chiama questa lookup “tempo costante”. Ecco il meccanismo che se lo merita.

Come una hash table trasforma una chiave in un indice di array

Una hash table è un array più una funzione che trasforma una chiave in una posizione di quell’array.

1

indice del bucket = hash(chiave) % numero_di_bucket

hash() prende una chiave di qualsiasi dimensione (una stringa, una tupla, un oggetto) e restituisce un intero. All’interno di una singola esecuzione del programma, la stessa chiave produce sempre lo stesso intero, e una buona funzione di hash distribuisce questi interi in modo quasi uniforme sul suo intervallo di output. Prendi l’intero modulo la lunghezza dell’array e ottieni uno slot. Memorizza lì chiave e valore. Una lookup successiva ricalcola lo stesso hash, finisce sullo stesso slot e legge il valore. Nessuna scansione, nessun confronto con tutte le altre chiavi.

Tutto il resto in una hash table reale, dalla gestione delle collisioni al resize fino all’esatta sequenza di probe, serve a mantenere funzionante quella lookup a un solo passo mentre la tabella si riempie.

Una versione minimale che ignora le collisioni:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class TinyTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [None] * size

    def put(self, key, value):
        index = hash(key) % self.size
        self.buckets[index] = (key, value)

    def get(self, key):
        index = hash(key) % self.size
        if self.buckets[index] is None:
            raise KeyError(key)
        stored_key, value = self.buckets[index]
        if stored_key != key:
            raise KeyError(key)
        return value

1
2
3
4

>>> t = TinyTable()
>>> t.put("user:42", {"name": "Dana"})
>>> t.get("user:42")
{'name': 'Dana'}

Si rompe non appena due chiavi diverse hanno lo stesso indice hash. hash("user:42") % 8 e hash("user:17") % 8 possono entrambi venire 3, e TinyTable ha posto per una sola di loro: il secondo put sovrascrive silenziosamente il primo. Questa è una collisione.

Come le hash table gestiscono le collisioni: chaining vs. open addressing

Esistono due modi standard per conservare entrambe le chiavi quando finiscono sullo stesso slot.

Il chaining trasforma ogni bucket in un piccolo contenitore, di solito una lista collegata. Una collisione significa che il bucket contiene due elementi invece di uno, e la lookup scorre quella lista finché non trova la chiave giusta.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class ChainedTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def put(self, key, value):
        index = hash(key) % self.size
        bucket = self.buckets[index]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        bucket = self.buckets[hash(key) % self.size]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

La HashMap di Java è una tabella a chaining. Ogni bucket parte come lista collegata. Se un bucket raccoglie almeno 8 elementi e la tabella ha almeno 64 bucket, quel bucket si converte in un albero rosso-nero (TREEIFY_THRESHOLD e MIN_TREEIFY_CAPACITY nel codice del JDK), così una scansione O(n) nel caso peggiore di un bucket sovraccarico diventa O(log n). Torna a essere una lista se un resize lo lascia con 6 elementi o meno.

L’open addressing mantiene ogni elemento direttamente nell’array, senza struttura secondaria e senza puntatori. Su una collisione fa probing: prova un altro slot, seguendo una regola fissa, finché non ne trova uno vuoto. Il dict di CPython funziona così, e il commento sulla lookup in Objects/dictobject.c ne spiega il motivo: “Open addressing is preferred over chaining since the link overhead for chaining would be substantial.” CPython evita anche il linear probing puro, che forma ammassi quando le chiavi arrivano in un ordine prevedibile. Ogni passo di probe mescola più bit dell’hash nell’indice successivo, così due chiavi che collidono sui bit bassi si separano dopo qualche probe.

Le due strategie falliscono in modo diverso. Una tabella a chaining che si riempie diventa più lenta, e nel caso peggiore ogni elemento finisce in un’unica lista lunga. Una tabella a open addressing non ha dove metter un elemento quando l’array è pieno, quindi deve fare resize prima che questo accada.

Cos’è il load factor e perché la tabella fa resize prima di essere piena

Il load factor è il rapporto tra elementi e bucket. Entrambe le strategie lo monitorano per decidere quando fare resize, e Java e CPython scelgono soglie diverse.

La HashMap di Java fa resize quando il numero di elementi supera la capacità moltiplicata per il load factor. La Javadoc del costruttore senza argomenti indica i valori predefiniti: 16 bucket, load factor 0,75, quindi il primo resize scatta a 12 elementi. Un resize raddoppia circa il numero di bucket e rifà l’hash di ogni elemento esistente nel nuovo array. Per questo la Javadoc consiglia di dimensionare la mappa in anticipo con HashMap.newHashMap(expectedSize) (Java 19+) quando sai più o meno quanti elementi conterrà: eviti i rehash ripetuti.

Il dict di CPython fa resize più tardi e cresce più rapidamente. Il commento USABLE_FRACTION nel codice dice che la tabella fa resize quando è piena per due terzi, e GROWTH_RATE dimensiona la nuova tabella per circa tre volte il numero attuale di elementi vivi, non un semplice raddoppio.

Nessuno dei due numeri è arbitrario. Un load factor vicino a 1 riempie l’array al massimo ma rende più lenta ogni operazione man mano che i bucket si riempiono; un load factor vicino a 0 spreca memoria su slot che nessuno usa ancora. Entrambi i design si assestano tra 0,66 e 0,75, il punto in cui altra memoria non riduce più di tanto la lunghezza dei probe.

Perché la lookup di una hash table è O(1) in media, non sempre

Il tempo costante vale solo finché gli hash distribuiscono le chiavi in modo quasi uniforme tra i bucket. Due cose lo rompono.

Una funzione di hash scadente o prevedibile. Se ogni chiave che inserisci finisce nello stesso bucket, una tabella a chaining degrada in un’unica lista collegata con lookup O(n), esattamente ciò che la struttura esiste per evitare. Succede in produzione. Un server che fa hash di input controllato da un attaccante (nomi di campi di un form, header HTTP, chiavi JSON) con una funzione prevedibile è esposto ad attacchi di complessità algoritmica: l’attaccante invia migliaia di chiavi costruite per collidere e forza il comportamento peggiore su ogni richiesta. Python randomizza l’hash di str e bytes per processo dalla versione 3.3 (controllato da PYTHONHASHSEED) proprio per questo motivo. La stessa stringa produce hash diversi in due esecuzioni dell’interprete, così nessuno può precalcolare offline un set di collisioni.

Modificare una chiave dopo l’inserimento. Il bucket in cui vive una chiave è stato scelto dal suo hash, quindi la tabella assume che quell’hash non cambi mai. Python lo impone a livello di tipo: i tipi mutabili come list e dict impostano __hash__ a None, e usarne uno come chiave genera TypeError: unhashable type: 'list' prima che l’errore possa verificarsi. Tuple e stringhe sono hashabili perché immutabili. Per una classe chiave personalizzata, implementa __hash__ e __eq__ insieme e basali solo su campi che non cambiano mai. Altrimenti una chiave modificata “scompare”: l’elemento è ancora nella tabella, nel bucket indicato dal suo vecchio hash, ma la lookup cerca altrove.

Quando non usare una hash table

Una hash table risponde velocemente a una domanda: questa chiave esiste, e qual è il suo valore? Quasi tutto il resto lo fa male.

  • Query su intervalli e ordinamento. “Tutti gli utenti creati questo mese” o “la prossima chiave dopo questa” richiedono una struttura ordinata. Una hash table non ha ordine. Il dict di CPython garantisce l’ordine di inserimento dalla 3.7, ma è ordine di iterazione, non di ordinamento, e non aiuta con “tutto tra X e Y”. Quella query è il mestiere di un B-tree, per cui la maggior parte dei database usa indici B-tree come default invece di indici hash. Come funzionano gli indici database tratta il compromesso tra scan e seek dietro quella scelta.
  • Corrispondenza per prefisso o fuzzy. “Chiavi che iniziano con user:” significa controllare ogni chiave. Un trie, o una struttura ordinata con ricerca binaria, lo gestisce direttamente.
  • Chiavi intere piccole in un intervallo ristretto. Se la chiave è già un giorno della settimana o una classe di status HTTP, salta la funzione di hash e indicizza direttamente un array. Un livello di meno, nessuna collisione.

Quando una hash table è la struttura giusta, quasi non ne scrivi mai una da zero. dict, HashMap, Map e std::unordered_map sono già ottimizzate e corrette. Le usi anche indirettamente più di quanto pensi: una funzione decorata con functools.lru_cache, trattata in Decoratori Python spiegati, costruisce una chiave dagli argomenti della chiamata e la cerca in un dict.

Quindi la decisione è breve. Se l’operazione è “cerca questo per chiave esatta”, usa la hash table integrata e non scriverne una tua. Se la domanda riguarda ordine, intervalli o corrispondenze parziali, scegli da subito una struttura ordinata o un trie, perché nessuna funzione di hash aggiusta una struttura che risponde alla domanda sbagliata.

Articoli correlati