1. Anatomia di una Funzione di Hash
Una funzione di hash $h: U \to \{0, 1, \dots, M-1\}$ mappa uno spazio di chiavi potenzialmente infinito ($U$) in un intervallo finito di indici di una tabella di dimensione $M$. Le proprietà fondamentali di una buona funzione di hash includono:
- Determinismo: La stessa chiave deve produrre sempre lo stesso valore di hash.
- Uniformità: Le chiavi dovrebbero essere distribuite uniformemente tra le $M$ posizioni per prevenire l'accumulo di cluster di collisioni.
- Efficienza Computazionale: Il calcolo dell'indice deve avvenire in tempo $\mathcal{O}(1)$.
2. Tecniche di Risoluzione delle Collisioni
Dal momento che il principio dei cassetti rende inevitabile il verificarsi di collisioni (due chiavi distinte che mappano sullo stesso indice), si utilizzano due macro-approcci principali:
- Concatenamento Separato (Separate Chaining): Ogni cella della tabella memorizza un puntatore a una struttura dinamica (es. lista collegata). Gli elementi con lo stesso hash vengono aggiunti alla medesima lista.
- Indirizzamento Aperto (Open Addressing): Tutti gli elementi sono memorizzati direttamente nella tabella. In caso di collisione, l'algoritmo esegue una scansione (probing) alla ricerca della prima cella libera successiva. Le varianti comuni includono l'esplorazione lineare ($h(k, i) = (h'(k) + i) \pmod M$) e quadratica.
// Implementazione di un generatore di hash basato su metodo della
moltiplicazione/divisione in C++
#include <string>
#include <iostream>
class HashProcessor {
int tableSize;
public:
HashProcessor(int size) : tableSize(size) {}
int computeHash(const
std::string& key) {
unsigned long long hashVal = 5381;
for (char c : key) {
hashVal = ((hashVal << 5) + hashVal) + c; // Algoritmo hash
djb2
}
return hashVal % tableSize;
}
};
3. Simulatore Interattivo: Analisi Collisioni e Funzione djb2
Testa la robustezza di dispersione inserendo stringhe diverse per verificare l'indice generato e la gestione teorica dei conflitti.
collision-engine@nexus-core:~#
Hash & Collision Simulation
> Inserisci i dati per testare l'algoritmo di hash e la mappatura dello spazio delle chiavi.