La tabella hash: accesso rapido ai valori hash

Dove trovo nel libro il capitolo che mi interessava tanto? Dove va a finire l’ordine di Maria Rossi? Dove è possibile acquistare l’orologio con il cinturino in pelle marrone? – Cosa hanno in comune queste tre domande? Questi quesiti riguardano luoghi (“Dove?”) e tutti e tre presuppongono che ciò che si cerca esista. Questo modello di idea può essere facilmente trasferito nel mondo delle banche dati.

Immaginate un negozio online con migliaia di articoli e clienti. Tutti questi dati sono memorizzati in database. Il cliente ricerca nel database un articolo specifico ed effettua un ordine, mentre il mittente assegna l’articolo ordinato, tramite il database, all’acquirente con i propri dati di indirizzo. Ciò si traduce in varie attività di ricerca e ordinamento, oltre a processi di inserimento ed eliminazione durante il processo di ordinazione. Per gestire questo tipo di compiti nel modo più efficiente, grandi quantità di dati affini sono combinati in una posizione di indirizzo nel database. Questa posizione viene calcolata con valori hash ed è costituita da una tabella di combinazioni alfanumericheche hanno sempre la stessa lunghezza. Il nostro articolo vi illustrerà i principi di utilizzo di queste tabelle hash.

Innanzitutto, un valore hash è calcolato in base alle informazioni di un set di dati. I valori hash di tutti i set di dati di un database sono inseriti in una tabella hash. A partire dal valore hash, un’ulteriore operazione matematica calcola la posizione di memorizzazione di queste informazioni nel database. Se l’utente immette ora un termine di ricerca, viene eseguito anche l’hash. A questo punto, la ricerca non viene più eseguita per “orologio da polso con cinturino in pelle marrone”, ma per una corrispondenza tra il valore hash originario dell’articolo e il valore hash del termine di ricerca appena utilizzato. In altre parole, viene ricercata una corrispondenza tra due combinazioni alfanumeriche. È un metodo che viene utilizzato per le soluzioni più disparate.

Quando si tenta di effettuare il login nell’esempio del database di WordPress, la password inserita dall’utente viene convertita in un valore hash utilizzando la stessa procedura, per poi essere confrontato con la voce nel campo “user_pass” del database. Se i due hash di 34 caratteri corrispondono, l’accesso è consentito. Riconvertire un valore hash nella password corrispondente non è possibile. Questa caratteristica evidenzia l’utilità di una funzione hash.

In caso di tentativi di accesso non autorizzato, come gli attacchi brute force, l’aggressore dovrebbe provare tutte le combinazioni possibili di caratteri fino a trovare una corrispondenza con questa stringa. Se la funzione hash utilizzata è nota e si utilizzano lettere maiuscole, lettere minuscole e cifre in una password di 10 caratteri, un cybercriminale dovrebbe effettuare esattamente 839.299.365.868.340.200 tentativi per trovare una corrispondenza.

Nella ricerca per “Berta Müller”, il puntatore parte subito dal valore 003 calcolato dalla tabella hash e deve, da qui, ricercare solo un set di dati concatenato. Questo consente di “impacchettare” grandi quantità di dati in modo più elegante e di ricercarli più rapidamente.

Questo principio viene utilizzato anche nel cosiddetto “caching” al fine di poter accedere rapidamente a dati già utilizzati. Questi dati vengono memorizzati nella cache e recuperati da lì se richiesti. Questo accade, ad esempio, con i siti web visitati che, invece di essere ricaricati da zero dal server quando li visitiamo per la seconda volta, vengono recuperati dalla cache risparmiando molto tempo. Anche i cookie svolgono una sorta di identificazione comparativa, per riconoscere i “luoghi” già visitati dall’utente sul web.

Il metodo di hashing appena descritto viene anche definito hashing aperto o indirizzamento chiuso, in cui i dati possono essere memorizzati in liste concatenate in uno spazio di memoria teoricamente illimitato. Sebbene il numero di chiavi disponibili non sia maggiore, la concatenazione consente di gestire quantità maggiori di dati. In questo caso, la parola “aperto” fa riferimento alla libertà di usare una lista separata dalla tabella hash.

Quando l’hashing è chiuso, il numero di chiavi disponibili è limitato dalla capacità della tabella. Se si tenta di memorizzare più dati, viene creato un cosiddetto “overflow”. A una nuova esecuzione della tabella, si individuano le posizioni ancora libere in cui è possibile posizionare questi “overflow”.

L’hashing cuckoo è un altro metodo per evitare collisioni nella tabella del database. Il termine deriva dal comportamento del cuculo di rimuovere le uova dai nidi di altri uccelli per poi depositarvi le proprie. Ad esempio, vengono utilizzate due funzioni hash per definire due posizioni di memorizzazione. Se la prima posizione è già occupata, la chiave già presente viene spostata in una nuova posizione, mentre la seconda chiave generata viene posizionata nella prima posizione di memorizzazione. Lo svantaggio di questa variante è che può formarsi un ciclo di ricerca infinito, tanto da terminare una routine a causa del timeout.

Per effettuare una ricerca nel database, ci sono vari metodi costruiti con complicate formule matematiche che si nascondono su un sito web sotto forma di codice di programmazione, per esempio dietro il semplice campo di ricerca con la lente di ingrandimento.

I database tendono ad ingrandirsi e il volume dei dati cresce a dismisura. L’hashing dinamico tiene conto di questo, ingrandendo la tabella hash per evitare collisioni. Ciò comporta tuttavia anche la modifica dei valori hash dei dati già memorizzati. Sono state sviluppate speciali funzioni hash che risolvono elegantemente anche questo problema. Pertanto, non esiste (almeno teoricamente) alcun limite per la quantità di dati. Tuttavia, con l’aumento del volume di dati le ricerche diventano meno efficienti.

Il vantaggio maggiore dell’utilizzo di una tabella hash è che permette di effettuare rapidamente ricerche in una grande quantità di dati. Il fatto che gli architetti di database siano costretti a stimare le dimensioni richieste con largo anticipo al fine di mantenere basso il rischio di collisione rappresenta un aspetto meno pratico. È possibile utilizzare molti tipi di dati purché permettano di calcolare i valori hash.

Tra i punti deboli di questo approccio si annovera il fatto che un gran numero di collisioni può far degenerare le banche dati. La probabilità di collisioni aumenta con la quantità di dati. Diverse funzioni hash non consentono, inoltre, di passare al set di dati successivo o precedente.