Interni delle funzioni hash e gestione delle collisioni
Capisca come Python calcola l'hash degli oggetti, come open addressing e chaining risolvono le collisioni e perché il caso medio O(1) può degradare a O(n)
Interni delle funzioni hash e gestione delle collisioni è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cos'è una hash map?
Una hash map (dizionario in Python) associa le chiavi ai valori usando una funzione hash che converte qualsiasi chiave in un indice intero dell'array sottostante. Una funzione hash ideale distribuisce le chiavi in modo uniforme nell'array, consentendo operazioni di ricerca, inserimento e cancellazione in O(1) nel caso medio. L'array sottostante viene chiamato tabella hash o array di bucket.
In Python, dict è una hash map altamente ottimizzata. Comprenderne i meccanismi interni aiuta a valutare il comportamento nel caso peggiore e a scegliere chiavi appropriate.
# Python dict is a hash map
hm = {}
hm['alice'] = 95
hm['bob'] = 87
hm['carol'] = 91
print(hm['alice']) # O(1) lookup: 95
print('bob' in hm) # O(1) membership: True
del hm['bob'] # O(1) deletion
print(hm) # {'alice': 95, 'carol': 91}Funzioni hash e il metodo __hash__
Python chiama __hash__(key) per calcolare un intero a partire dalla chiave, quindi calcola il resto della divisione di tale intero per la dimensione della tabella, così da trovare l'indice del bucket. I tipi integrati come int, str e tuple dispongono di implementazioni hash integrate e veloci. list e dict non sono hashable (sono mutabili e modificarli invaliderebbe qualsiasi hash memorizzato).
Una buona funzione hash distribuisce le chiavi in modo uniforme, è deterministica ed è veloce da calcolare. L'hash delle stringhe di Python viene randomizzato tra un'esecuzione e l'altra (una funzionalità di sicurezza): usi PYTHONHASHSEED=0 per disabilitare questa randomizzazione e ottenere risultati riproducibili nei test.
# Built-in hash in Python
print(hash(42)) # integer hashes to itself (CPython)
print(hash('hello')) # string hash (randomised per run)
print(hash((1, 2, 3))) # tuple hash: depends on contents
# Unhashable types
try:
hash([1, 2, 3]) # lists are mutable -> not hashable
except TypeError as e:
print('Error:', e)
# Custom class: define __hash__ and __eq__
class Point:
def __init__(self, x, y): self.x = x; self.y = y
def __hash__(self): return hash((self.x, self.y))
def __eq__(self, other): return self.x == other.x and self.y == other.y
points = {Point(1, 2): 'A', Point(3, 4): 'B'}
print(points[Point(1, 2)]) # 'A'Collisioni: quando due chiavi producono lo stesso bucket
Si verifica una collisione quando due chiavi distinte producono lo stesso indice di bucket. Le collisioni sono inevitabili (principio dei cassetti: infinite chiavi e un numero finito di bucket). Le due strategie standard di risoluzione sono il chaining e l'open addressing. Python usa una variante dell'open addressing con probing pseudo-casuale.
Il chaining memorizza una lista concatenata (o un array dinamico) in ogni bucket; tutte le chiavi che collidono in quel bucket formano una catena. L'open addressing cerca il bucket vuoto successivo in base a una sequenza di probing.
# Simplified chaining hash map
class ChainingHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _idx(self, key):
return hash(key) % self.capacity
def put(self, key, val):
bucket = self.buckets[self._idx(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
def get(self, key):
for k, v in self.buckets[self._idx(key)]:
if k == key:
return v
return None
hm = ChainingHashMap()
hm.put('a', 1); hm.put('b', 2)
print(hm.get('a')) # 1
print(hm.get('c')) # NoneOpen addressing: probing lineare
Nel probing lineare, quando si verifica una collisione all'indice i, la mappa controlla i+1, i+2, ... (tornando all'inizio quando raggiunge la fine) finché non trova uno slot vuoto. La ricerca deve seguire la stessa sequenza di probing per trovare la chiave. Le cancellazioni richiedono un marcatore «tombstone» invece di svuotare lo slot, per evitare di interrompere la catena di probing.
Il clustering è il principale svantaggio: quando si forma un gruppo di slot occupati, gli inserimenti successivi in quell'area estendono il gruppo, facendo peggiorare le prestazioni fino ad avvicinarsi a O(n).
class LinearProbingHashMap:
DELETED = object() # tombstone sentinel
def __init__(self, capacity=8):
self.capacity = capacity
self.keys = [None] * capacity
self.vals = [None] * capacity
self.size = 0
def _probe(self, key):
idx = hash(key) % self.capacity
while self.keys[idx] is not None and self.keys[idx] != key:
idx = (idx + 1) % self.capacity
return idx
def put(self, key, val):
idx = self._probe(key)
if self.keys[idx] is None:
self.size += 1
self.keys[idx] = key
self.vals[idx] = val
def get(self, key):
idx = self._probe(key)
if self.keys[idx] == key:
return self.vals[idx]
return None
hm = LinearProbingHashMap()
hm.put('x', 10); hm.put('y', 20)
print(hm.get('x')) # 10Fattore di carico e ridimensionamento
Il fattore di carico è il rapporto tra il numero di elementi memorizzati e la capacità totale: α = n/m. All'aumentare di α, cresce la probabilità di collisione e le prestazioni peggiorano. Il dict di Python viene ridimensionato (la capacità raddoppia) quando il fattore di carico supera circa 2/3. Il ridimensionamento calcola nuovamente l'hash di tutti gli elementi esistenti e li inserisce nella nuova tabella più grande: è un'operazione O(n) che si verifica raramente, mantenendo a O(1) il costo ammortizzato degli inserimenti.
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(30):
d[i] = i
new_size = sys.getsizeof(d)
if new_size != prev_size:
print(f'Resized at n={i+1}: {prev_size} -> {new_size} bytes')
prev_size = new_sizeO(1) medio contro O(n) nel caso peggiore
Con una buona funzione hash, le collisioni sono rare e la lunghezza attesa delle catene è costante indipendentemente da n. Di conseguenza, la ricerca, l'inserimento e la cancellazione hanno complessità O(1) nel caso medio. Tuttavia, uno scenario nel caso peggiore, ad esempio un input creato deliberatamente per associare tutte le chiavi allo stesso bucket, porta tutte le operazioni a O(n). Il seed hash randomizzato di Python riduce il rischio di questo attacco, ma teoricamente non elimina il caso peggiore.
Nell'analisi durante un colloquio, dica: «O(1) in media, O(n) nel caso peggiore a causa delle collisioni».
# Python randomised hash seed prevents worst-case hash-flooding
import os
print('PYTHONHASHSEED:', os.environ.get('PYTHONHASHSEED', 'random'))
# By default Python randomises the hash of strings each run
# This prevents an attacker from crafting keys that all collide
# To reproduce results in testing: PYTHONHASHSEED=0 python script.pydict, defaultdict e Counter in Python
Python offre tre varianti di hash map che è utile conoscere. dict è la mappa generica; l'accesso a una chiave mancante genera KeyError. defaultdict(factory) restituisce un valore predefinito quando si accede a una chiave mancante (utile per raccogliere elementi in liste o per contare). Counter è una sottoclasse specializzata per contare oggetti hashable; supporta anche operazioni aritmetiche tra contatori.
from collections import defaultdict, Counter
# defaultdict for grouping
groups = defaultdict(list)
for word in ['apple', 'ant', 'banana', 'bee', 'avocado']:
groups[word[0]].append(word)
print(dict(groups))
# {'a': ['apple','ant','avocado'], 'b': ['banana','bee']}
# Counter for frequency
c = Counter('abracadabra')
print(c.most_common(3)) # [('a',5),('b',2),('r',2)]
print(c['a'] - Counter('aa')['a']) # counter subtractionHash map e hash set a confronto
Un hash set memorizza solo le chiavi (senza valori associati) e supporta in O(1) la verifica dell'appartenenza, l'inserimento e la cancellazione. Il set di Python è un hash set. Usi un set quando deve solo rispondere alla domanda «questo elemento esiste?» senza memorizzare dati associati. Usi un dict quando deve associare valori (conteggi, risultati e così via) alle chiavi.
# set for membership testing
visited = set()
for node in [1, 3, 5, 3, 7, 1]:
if node not in visited:
print('New node:', node)
visited.add(node)
# Set operations: union, intersection, difference
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print('Union:', A | B) # {1,2,3,4,5,6}
print('Intersection:', A & B) # {3,4}
print('Difference:', A - B) # {1,2}Implementare una hash map da zero (versione da colloquio)
A volte, durante un colloquio, Le viene chiesto di implementare una hash map di base. I componenti fondamentali sono: un array di bucket di dimensione fissa (usi 16 o 1024), una lista di coppie (chiave, valore) in ogni bucket per il chaining, una funzione hash (usi la funzione hash integrata di Python con % capacity) e il ridimensionamento quando il fattore di carico supera 0.7. Menzionare spontaneamente il ridimensionamento e il fattore di carico dimostra una conoscenza approfondita dell'argomento.
class HashMap:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, val):
b = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(b):
if k == key:
b[i] = (key, val)
return
b.append((key, val))
self.size += 1
if self.size / self.capacity > 0.7:
self._resize()
def get(self, key, default=None):
for k, v in self.buckets[self._hash(key)]:
if k == key:
return v
return default
def _resize(self):
old = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
hm = HashMap()
for i in range(20):
hm.put(i, i * 2)
print(hm.get(10)) # 20
print(hm.capacity) # should have resizedQuando le hash map falliscono: chiavi non hashable
Solo gli oggetti hashable possono essere usati come chiavi di un dizionario. In Python, un oggetto è hashable se dispone di un metodo __hash__ e di un metodo __eq__, e se il suo valore hash non cambia durante il suo ciclo di vita. Liste, set e dict sono mutabili e quindi non sono hashable. Tuple e frozenset sono alternative hashable a liste e set quando vengono usati come chiavi.
Un errore comune nei colloqui: per raggruppare gli anagrammi è necessario usare una tuple ordinata (non una lista ordinata) come chiave del dict.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # tuple is hashable; list is not
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]Riepilogo della complessità delle hash map
Le hash map offrono complessità O(1) nel caso medio per inserimento, cancellazione e ricerca: sono alla base di molte soluzioni ottimali nei colloqui. Le ipotesi fondamentali sono: una buona funzione hash distribuisce le chiavi in modo uniforme, il fattore di carico rimane limitato (il ridimensionamento lo mantiene tale) e gli oggetti usati come chiavi sono immutabili e hashable. Quando queste ipotesi sono rispettate, le hash map trasformano le scansioni lineari O(n) in ricerche O(1), consentendo soluzioni come two-sum in O(n) invece di O(n²).
Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: una hash map associa le chiavi agli indici dei bucket tramite una funzione hash e raggiunge una complessità O(1) nel caso medio, le collisioni vengono risolte con il chaining (una lista concatenata per bucket) o con l'open addressing (probing per trovare lo slot vuoto successivo) e solo gli oggetti immutabili e hashable possono essere chiavi di un dizionario: usi le tuple invece delle liste quando è necessaria una chiave costituita da una sequenza. Nella prossima lezione risolveremo il problema two-sum e le sue numerose varianti da colloquio.
Domande Frequenti
La lezione «Interni delle funzioni hash e gestione delle collisioni» è gratuita?
Sì — il testo completo di «Interni delle funzioni hash e gestione delle collisioni» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Interni delle funzioni hash e gestione delle collisioni»?
Capisca come Python calcola l'hash degli oggetti, come open addressing e chaining risolvono le collisioni e perché il caso medio O(1) può degradare a O(n) Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Interni delle funzioni hash e gestione delle collisioni»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Interni delle funzioni hash e gestione delle collisioni
- Two-sum e le sue numerose varianti
- Conteggio e raggruppamento delle frequenze
- Sequenza consecutiva più lunga e cache LRU