Tabele Hash și Tehnici de Hashing
Tabele Hash și Tehnici de Hashing¶
Ideea Fundamentală¶
O tabelă hash mapează chei la valori folosind o funcție hash $h(k)$ care transformă o cheie într-un index de array:
$$h: K \to {0, 1, ..., m-1}$$
unde $m$ este dimensiunea tabelei. Rezultatul? Operații de inserare, căutare și ștergere în $O(1)$ în medie.
De ce nu funcționează mereu perfect?¶
Deoarece mulțimea cheilor posibile este mult mai mare decât $m$, este inevitabil ca două chei diferite să producă același index. Aceasta se numește coliziune:
$$h(k_1) = h(k_2) \quad \text{dar} \quad k_1 \neq k_2$$
Întreaga provocare a tabelelor hash constă în gestionarea coliziunilor eficient.
Funcții Hash¶
O funcție hash bună trebuie să fie:
- Deterministă — aceeași cheie produce mereu același hash
- Uniformă — distribuie cheile cât mai egal în tabelă
- Rapidă — calculabilă în $O(1)$
Metoda Diviziunii¶
$$h(k) = k \mod m$$
Simplă dar eficientă. Alegem $m$ ca un număr prim care nu e aproape de o putere a lui 2, pentru a evita pattern-uri.
Metoda Înmulțirii (Knuth)¶
$$h(k) = \lfloor m \cdot (k \cdot A \mod 1) \rfloor$$
unde $A \approx 0.6180339887$ (inversul raportului de aur). Avantaj: funcționează bine indiferent de valoarea lui $m$.
Hash pentru Stringuri¶
def hash_string(s, m):
"""Polynomial rolling hash"""
h = 0
base = 31 # un număr prim mic
for char in s:
h = (h * base + ord(char)) % m
return h
Ideea: tratăm string-ul ca un număr în baza 31. Fiecare caracter contribuie la hash ponderat de poziția sa.
Rezolvarea Coliziunilor¶
1. Chaining (Înlănțuire)¶
Fiecare slot din tabelă conține o listă cu toate elementele care au același hash.
class HashTableChaining:
def __init__(self, size=16):
self.size = size
self.table = [[] for _ in range(size)]
self.count = 0
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
idx = self._hash(key)
# Verificăm dacă cheia există deja
for i, (k, v) in enumerate(self.table[idx]):
if k == key:
self.table[idx][i] = (key, value)
return
self.table[idx].append((key, value))
self.count += 1
# Redimensionare dacă factorul de încărcare > 0.75
if self.count / self.size > 0.75:
self._resize()
def get(self, key):
idx = self._hash(key)
for k, v in self.table[idx]:
if k == key:
return v
raise KeyError(key)
def delete(self, key):
idx = self._hash(key)
for i, (k, v) in enumerate(self.table[idx]):
if k == key:
self.table[idx].pop(i)
self.count -= 1
return v
raise KeyError(key)
def _resize(self):
old_table = self.table
self.size *= 2
self.table = [[] for _ in range(self.size)]
self.count = 0
for chain in old_table:
for key, value in chain:
self.put(key, value)
2. Open Addressing (Adresare Deschisă)¶
Toate elementele se stochează direct în array. La coliziune, căutăm următorul slot liber prin probing.
Linear Probing — verificăm sloturile consecutive:
$$h(k, i) = (h'(k) + i) \mod m$$
class HashTableLinearProbing:
DELETED = object() # marker pentru ștergere lazy
def __init__(self, size=16):
self.size = size
self.keys = [None] * size
self.vals = [None] * size
self.count = 0
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
if self.count / self.size > 0.5: # prag mai mic pentru open addressing
self._resize()
idx = self._hash(key)
while self.keys[idx] is not None and self.keys[idx] is not self.DELETED:
if self.keys[idx] == key:
self.vals[idx] = value # actualizare
return
idx = (idx + 1) % self.size
self.keys[idx] = key
self.vals[idx] = value
self.count += 1
def get(self, key):
idx = self._hash(key)
while self.keys[idx] is not None:
if self.keys[idx] == key:
return self.vals[idx]
idx = (idx + 1) % self.size
raise KeyError(key)
def delete(self, key):
idx = self._hash(key)
while self.keys[idx] is not None:
if self.keys[idx] == key:
self.keys[idx] = self.DELETED
self.count -= 1
return self.vals[idx]
idx = (idx + 1) % self.size
raise KeyError(key)
Atenție la ștergere! În open addressing nu putem pur și simplu pune
None— am rupe lanțul de probing. De aceea folosim un markerDELETED(ștergere lazy).
Comparație¶
| Aspect | Chaining | Open Addressing |
|---|---|---|
| Coliziuni | Liste externe | Probing intern |
| Factor de încărcare | Poate fi > 1 | Trebuie < 1 (ideal < 0.5) |
| Cache | Slab (pointeri) | Excelent (date contigue) |
| Ștergere | Simplă | Necesită marker |
Factorul de Încărcare¶
$$\alpha = \frac{n}{m}$$
unde $n$ = număr de elemente, $m$ = dimensiunea tabelei.
- Chaining: numărul mediu de comparații per operație = $1 + \alpha$
- Linear Probing: $\frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)$ pentru căutare nereușită
Când $\alpha$ crește peste un prag (0.75 pentru chaining, 0.5 pentru open addressing), redimensionăm tabela (de obicei $\times 2$) și reinserăm toate elementele.
Aplicație: Detectarea Duplicatelor¶
def has_duplicates(arr):
"""O(n) timp, O(n) spațiu — vs O(n²) cu brute force"""
seen = set() # implementat ca hash table intern
for x in arr:
if x in seen:
return True
seen.add(x)
return False
def two_sum(arr, target):
"""Găsește perechea (i, j) cu arr[i] + arr[j] == target"""
complement = {}
for i, x in enumerate(arr):
if target - x in complement:
return (complement[target - x], i)
complement[x] = i
return None
Exerciții¶
- Implementați o tabelă hash cu double hashing: $h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m$
- Care este complexitatea worst-case a unei tabele hash? Construiți un exemplu
- Explicați de ce
dictdin Python folosește open addressing, nu chaining - Implementați un LRU Cache folosind un hash map + listă dublu înlănțuită