Cos'è l'hashing?
Un hash è un valore che ha una lunghezza fissa e viene generato utilizzando una formula matematica. I valori hash vengono utilizzati nella compressione dei dati, nella crittografia, ecc. Nell'indicizzazione dei dati, vengono utilizzati i valori hash perché hanno una dimensione di lunghezza fissa indipendentemente dai valori utilizzati per generarli. Rende i valori hash per occupare uno spazio minimo rispetto ad altri valori di lunghezze variabili.
Una funzione hash utilizza un algoritmo matematico per convertire la chiave in un hash. Si verifica una collisione quando una funzione hash produce lo stesso valore hash per più di una chiave.
In questo tutorial sull'algoritmo imparerai:
- Cos'è l'hashing?
- Cos'è una tabella hash?
- Funzioni hash
- Qualità di una buona funzione hash
- Collisione
- Operazioni sulla tabella hash
- Esempio di Hash Table Python
- Spiegazione del codice della tabella hash
- Esempio di dizionario Python
- Analisi della complessità
- Applicazioni del mondo reale
- Vantaggi delle tabelle hash
- Svantaggi delle tabelle hash
Cos'è una tabella hash?
Una tabella hash è una struttura dati che memorizza i valori utilizzando una coppia di chiavi e valori. A ogni valore viene assegnata una chiave univoca generata utilizzando una funzione hash.
Il nome della chiave viene utilizzato per accedere al valore associato. Ciò rende la ricerca di valori in una tabella hash molto veloce, indipendentemente dal numero di elementi nella tabella hash.
Funzioni hash
Ad esempio, se si desidera archiviare i record dei dipendenti e ogni dipendente viene identificato in modo univoco utilizzando un numero di dipendente.
Possiamo utilizzare il numero del dipendente come chiave e assegnare i dati del dipendente come valore.
L'approccio precedente richiederà uno spazio libero aggiuntivo dell'ordine di (m * n 2 ) dove la variabile m è la dimensione dell'array e la variabile n è il numero di cifre per il numero del dipendente. Questo approccio introduce un problema di spazio di archiviazione.
Una funzione hash risolve il problema precedente ottenendo il numero del dipendente e utilizzandolo per generare un valore intero hash, cifre fisse e ottimizzando lo spazio di archiviazione. Lo scopo di una funzione hash è creare una chiave che verrà utilizzata per fare riferimento al valore che vogliamo memorizzare. La funzione accetta il valore da salvare quindi utilizza un algoritmo per calcolare il valore della chiave.
Quello che segue è un esempio di una semplice funzione hash
h(k) = k1 % m
QUI,
- h (k) è la funzione hash che accetta un parametro k. Il parametro k è il valore per il quale vogliamo calcolare la chiave.
- k 1 % m è l'algoritmo per la nostra funzione hash dove k1 è il valore che vogliamo memorizzare e m è la dimensione dell'elenco. Usiamo l'operatore modulo per calcolare la chiave.
Esempio
Supponiamo di avere una lista con una dimensione fissa di 3 e i seguenti valori
[1,2,3]
Possiamo usare la formula sopra per calcolare le posizioni che ogni valore dovrebbe occupare.
L'immagine seguente mostra gli indici disponibili nella nostra tabella hash.
Passo 1)
Calcola la posizione che verrà occupata dal primo valore in questo modo
h (1) = 1% 3
= 1
Il valore 1 occuperà lo spazio sull'indice 1
Passo 2)
Calcola la posizione che verrà occupata dal secondo valore
h (2) = 2% 3
= 2
Il valore 2 occuperà lo spazio sull'indice 2
Passaggio 3)
Calcola la posizione che verrà occupata dal terzo valore.
h (3) = 3% 3
= 0
Il valore 3 occuperà lo spazio sull'indice 0
Risultato finale
La nostra tabella hash compilata sarà ora la seguente.
Qualità di una buona funzione hash
Una buona funzione hash dovrebbe avere le seguenti qualità.
- La formula per generare l'hash dovrebbe utilizzare il valore dei dati da memorizzare nell'algoritmo.
- La funzione hash dovrebbe generare valori hash univoci anche per i dati di input che hanno la stessa quantità.
- La funzione dovrebbe ridurre al minimo il numero di collisioni. Le collisioni si verificano quando lo stesso valore viene generato per più di un valore.
- I valori devono essere distribuiti in modo coerente su tutti gli hash possibili.
Collisione
Si verifica una collisione quando l'algoritmo genera lo stesso hash per più di un valore.
Diamo un'occhiata a un esempio.
Supponiamo di avere il seguente elenco di valori
[3,2,9,11,7]
Supponiamo che la dimensione della tabella hash sia 7 e useremo la formula (k 1 % m) dove m è la dimensione della tabella hash.
La tabella seguente mostra i valori hash che verranno generati.
| Chiave | Algoritmo hash (k 1 % m) | Valore hash |
| 3 | 3% 7 | 3 |
| 2 | 3% 7 | 2 |
| 9 | 3% 7 | 2 |
| 11 | 3% 7 | 4 |
| 7 | 3% 7 | 0 |
Come possiamo vedere dai risultati precedenti, i valori 2 e 9 hanno lo stesso valore hash e non possiamo memorizzare più di un valore in ogni posizione.
Il problema dato può essere risolto utilizzando il concatenamento o il sondaggio. Le sezioni seguenti illustrano in dettaglio il concatenamento e il rilevamento.
Concatenamento
Il concatenamento è una tecnica utilizzata per risolvere il problema della collisione utilizzando elenchi concatenati ciascuno con indici univoci.
L'immagine seguente mostra l'aspetto di un elenco concatenato
Sia 2 che 9 occupano lo stesso indice, ma vengono memorizzati come elenchi collegati. Ogni elenco ha un identificatore univoco.
Vantaggi degli elenchi concatenati
Di seguito sono riportati i vantaggi degli elenchi concatenati:
- Gli elenchi concatenati hanno prestazioni migliori durante l'inserimento dei dati perché l'ordine di inserimento è O (1).
- Non è necessario ridimensionare una tabella hash che utilizza un elenco concatenato.
- Può facilmente ospitare un numero elevato di valori purché sia disponibile spazio libero.
Sondaggio
L'altra tecnica utilizzata per risolvere la collisione è il sondaggio. Quando si utilizza il metodo di sondaggio, se si verifica una collisione, possiamo semplicemente andare avanti e trovare uno slot vuoto per memorizzare il nostro valore.
I seguenti sono i metodi di sondaggio:
| Metodo | Descrizione |
| Sondaggio lineare | Proprio come suggerisce il nome, questo metodo ricerca gli slot vuoti in modo lineare partendo dalla posizione in cui si è verificata la collisione e andando avanti. Se viene raggiunta la fine dell'elenco e non viene trovato alcuno slot vuoto. Il sondaggio inizia all'inizio dell'elenco. |
| Sondaggio quadratico | Questo metodo utilizza espressioni polinomiali quadratiche per trovare il successivo slot libero disponibile. |
| Doppio hash | Questa tecnica utilizza un algoritmo di funzione hash secondaria per trovare il prossimo slot libero disponibile. |
Usando il nostro esempio sopra, la tabella hash dopo aver usato il sondaggio apparirà come segue:
Operazioni sulla tabella hash
Ecco le operazioni supportate dalle tabelle hash:
- Inserimento : questa operazione viene utilizzata per aggiungere un elemento alla tabella hash
- Ricerca in corso : questa operazione viene utilizzata per cercare elementi nella tabella hash utilizzando la chiave
- Eliminazione : questa operazione viene utilizzata per eliminare elementi dalla tabella hash
Inserimento dati operazione
L'operazione di inserimento viene utilizzata per memorizzare i valori nella tabella hash. Quando un nuovo valore viene memorizzato nella tabella hash, gli viene assegnato un numero di indice. Il numero di indice viene calcolato utilizzando la funzione hash. La funzione hash risolve eventuali collisioni che si verificano durante il calcolo del numero di indice.
Ricerca di operazioni sui dati
L'operazione di ricerca viene utilizzata per cercare i valori nella tabella hash utilizzando il numero di indice. L'operazione di ricerca restituisce il valore collegato al numero di indice di ricerca. Ad esempio, se memorizziamo il valore 6 nell'indice 2, l'operazione di ricerca con il numero di indice 2 restituirà il valore 6.
Elimina operazione dati
L'operazione di eliminazione viene utilizzata per rimuovere un valore da una tabella hash. Per eliminare l'operazione viene eseguita utilizzando il numero di indice. Una volta che un valore è stato cancellato, il numero di indice viene reso libero. Può essere utilizzato per memorizzare altri valori utilizzando l'operazione di inserimento.
Implementazione della tabella hash con esempio di Python
Diamo un'occhiata a un semplice esempio che calcola il valore hash di una chiave
def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')
Spiegazione del codice della tabella hash
QUI,
- Definisce una funzione hash_key che accetta i parametri key ed m.
- Utilizza una semplice operazione di modulo per determinare il valore hash
- Definisce una variabile m inizializzata al valore 7. Questa è la dimensione della nostra tabella hash
- Calcola e stampa il valore hash di 3
- Calcola e stampa il valore hash di 2
- Calcola e stampa il valore hash di 9
- Calcola e stampa il valore hash di 11
- Calcola e stampa il valore hash di 7
L'esecuzione del codice precedente produce i seguenti risultati.
The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0
Esempio di dizionario Python
Python viene fornito con un tipo di dati integrato chiamato Dictionary. Un dizionario è un esempio di una tabella hash. Memorizza i valori utilizzando una coppia di chiavi e valori. I valori hash vengono generati automaticamente per noi e qualsiasi collisione viene risolta per noi in background.
L'esempio seguente mostra come utilizzare un tipo di dati di dizionario in python 3
employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)
QUI,
- Definisce un dipendente della variabile del dizionario. Il nome della chiave viene utilizzato per memorizzare il valore John Doe, età memorizza 36 e posizione memorizza il valore Business Manager.
- Recupera il valore del nome della chiave e lo stampa nel terminale
- Aggiorna il valore della posizione chiave al valore Software Engineer
- Stampa i valori del nome e della posizione delle chiavi
- Elimina tutti i valori memorizzati nella nostra variabile di dizionario dipendente
- Stampa il valore dell'impiegato
L'esecuzione del codice precedente produce i seguenti risultati.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Analisi della complessità
Le tabelle hash hanno una complessità temporale media di O (1) nel migliore dei casi. La complessità temporale nel caso peggiore è O (n). Lo scenario peggiore si verifica quando molti valori generano la stessa chiave hash e dobbiamo risolvere la collisione sondando.
Applicazioni del mondo reale
Nel mondo reale, le tabelle hash vengono utilizzate per archiviare i dati
- Banche dati
- Array associativi
- Imposta
- Cache di memoria
Vantaggi delle tabelle hash
Ecco i vantaggi / vantaggi dell'utilizzo delle tabelle hash:
- Le tabelle hash hanno prestazioni elevate durante la ricerca di dati, l'inserimento e l'eliminazione di valori esistenti.
- La complessità temporale per le tabelle hash è costante indipendentemente dal numero di elementi nella tabella.
- Funzionano molto bene anche quando si lavora con set di dati di grandi dimensioni.
Svantaggi delle tabelle hash
Ecco gli svantaggi dell'utilizzo delle tabelle hash:
- Non è possibile utilizzare un valore nullo come chiave.
- Non è possibile evitare conflitti durante la generazione di chiavi utilizzando. funzioni hash. Le collisioni si verificano quando viene generata una chiave già in uso.
- Se la funzione di hashing ha molte collisioni, ciò può portare a una riduzione delle prestazioni.
Sommario:
- Le tabelle hash vengono utilizzate per memorizzare i dati utilizzando una coppia di chiavi e valori.
- Una funzione hash utilizza un algoritmo matematico per calcolare il valore hash.
- Si verifica una collisione quando lo stesso valore hash viene generato per più di un valore.
- Il concatenamento risolve le collisioni creando elenchi collegati.
- Il sondaggio risolve la collisione trovando slot vuoti nella tabella hash.
- Il rilevamento lineare ricerca lo slot libero successivo per memorizzare il valore a partire dallo slot in cui si è verificata la collisione.
- Il sondaggio quadratico utilizza espressioni polinomiali per trovare lo slot libero successivo quando si verifica una collisione.
- Il doppio hashing utilizza un algoritmo di funzione hash secondario per trovare lo slot libero successivo quando si verifica una collisione.
- Le tabelle hash hanno prestazioni migliori rispetto ad altre strutture di dati.
- La complessità temporale media delle tabelle hash è O (1)
- Un tipo di dati del dizionario in Python è un esempio di una tabella hash.
- Le tabelle hash supportano le operazioni di inserimento, ricerca ed eliminazione.
- Un valore null non può essere utilizzato come valore di indice.
- Le collisioni non possono essere evitate nelle funzioni hash. Una buona funzione hash riduce al minimo il numero di collisioni che si verificano per migliorare le prestazioni.