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.
Qual è il principio di una tabella 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.
Protezione e valori hash
Con l’assegnazione di hash generati automaticamente a termini arbitrari viene creata una tabella hash. La funzione hash utilizzata a questo scopo genera un hash, ovvero una stringa di caratteri che è sempre della stessa lunghezza. La lunghezza della stringa e i caratteri in essa contenuti sono determinati dal metodo di hashing utilizzato. L’hashing viene utilizzato, ad esempio, per rendere i dati di accesso più sicuri contro gli attacchi.
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.
Uso più rapido delle banche dati
Nei database, le tabelle hash vengono utilizzate per accelerare le ricerche e l’immissione o l’eliminazione di set di dati. Prendiamo come esempio la ricerca di un cognome nel database dei dipendenti di una società. Una ricerca di questo tipo può richiedere molto tempo dal momento che la corrispondenza viene ricercata in sequenza in ogni campo del database. Se il termine di ricerca viene convertito in un valore hash e si cerca una corrispondenza nella tabella hash, in genere si ottiene il risultato molto più rapidamente.
Ma come funziona? A ogni set di dati viene assegnato un indirizzo univoco. All’interno del database, questo tipo di indirizzamento è sempre identico (001, 002, 003 o 00A1, 00A2, 00A3, ecc.). Questo indirizzo viene calcolato mediante la funzione hash.
Guardiamo un semplice esempio: un database ha spazio per 11 voci, dalla posizione 0 alla posizione 10. Il nome “Lisa” è composto da quattro caratteri ASCII con i rispettivi codici ASCII: L è 76, i è 105, s è 115 e a è 97. Provatelo voi stessi in Windows con il tastierino numerico: [Alt] + 0076, ad esempio, restituisce “L”. Tutti i valori ASCII vengono sommati e per “Lisa” otteniamo come risultato il valore hash 393. La somma dei valori ASCII corrisponde ora a una funzione hash.
A questo punto viene eseguito un calcolo del valore residuo con numeri interi: 393 % 11 (posizioni di memoria) = 35, con resto di 8 (il segno percentuale “%” corrisponde all’operatore matematico per il calcolo del valore residuo in molti linguaggi di programmazione). Questo valore residuo determina a quale punto del database, in questo caso il numero di indice 8, vengono memorizzate Lisa e tutte le altre informazioni a lei legate. È facile immaginare che in questo tipo di indirizzamento emergano frequentemente valori residui identici. Tuttavia, maggiori sono il numero di posizioni di memoria e la lunghezza del valore hash utilizzato, minore è la probabilità che si verifichi una duplicazione. Consideriamo, ad esempio, il nome “Alis Meyer” che, nonostante utilizzi le “stesse” lettere, restituirebbe un posizionamento completamente diverso, poiché la “A” è diventata maiuscola e la “l” minuscola.
La figura mostra il problema della duplicazione: nomi diversi rimandano a indici identici, creando le cosiddette collisioni (frecce azzurre). Cosa “fa” il database quando si verifica un “incidente” del genere? Il set di dati doppio viene memorizzato nel primo posto vacante disponibile nel database. Se nell’esempio effettuiamo una ricerca per “Berta Müller”, il puntatore inizia la ricerca non dalla posizione 001, ma piuttosto dalla posizione di indice 003, che permette di ottenere un (leggero) risparmio di tempo. Questo metodo viene definito hash con indirizzamento aperto, in cui viene quindi eseguita un’ispezione lineare.
Il funzionamento degli hash con concatenazione è leggermente diverso. Invece di “aprire” un nuovo set di dati, quello successivo alla prima voce corrispondente viene memorizzato in modo concatenato. Pertanto, è possibile individuare con una sola ricerca il set di dati cercato: identificando il primo set di dati si trova anche l’altro corrispondente a quella posizione di memorizzazione. Ciò si traduce in un aumento della velocità di elaborazione.
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.
Metodi di hashing
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’uso dei termini hashing “aperto” e “chiuso” non è chiaramente regolato e possono essere utilizzati in modo equivoco nelle pubblicazioni. Si raccomanda di utilizzare la rispettiva descrizione dettagliata del metodo.
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.
Vantaggi e svantaggi delle tabelle hash
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.