Tabella hash nella struttura dati: Python Esempio

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, i valori hash vengono utilizzati perché hanno una dimensione di lunghezza fissa indipendentemente dai valori utilizzati per generarli. Fa sì che i valori hash occupino uno spazio minimo rispetto ad altri valori di diversa lunghezza.

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.

Cos'è una tabella hash?

A TABELLA HASH è una struttura dati che memorizza 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 suo 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 desideriamo archiviare i record dei dipendenti e ciascun 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 di cui sopra richiederà spazio libero aggiuntivo dell'ordine di (m*n²) dove la variabile m è la dimensione del schieramentoe 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 di cui sopra ottenendo il numero del dipendente e utilizzandolo per generare un valore intero hash, cifre fisse e ottimizzare lo spazio di archiviazione. Lo scopo di una funzione hash è creare una chiave che verrà utilizzata per fare riferimento al valore che vogliamo archiviare. La funzione accetta il valore da salvare quindi utilizza un algoritmo per calcolare il valore della chiave.

Di seguito è riportato 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₁ % 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 un elenco con una dimensione fissa di 3 e i seguenti valori

,

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 sarà occupata dal primo valore in questo modo

h(1) = 1% 3

= 1

Il valore 1 occuperà lo spazio su indice 1

Passo 2) Calcola la posizione che sarà occupata dal secondo valore

h(2) = 2% 3

= 2

Il valore 2 occuperà lo spazio su indice 2

Passo 3) Calcola la posizione che sarà occupata dal terzo valore.

h(3) = 3% 3

= 0

Il valore 3 occuperà lo spazio su 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 archiviare 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

,

Supponiamo che la dimensione della tabella hash sia 7 e utilizzeremo la formula (k₁ % m) dove m è la dimensione della tabella hash.

La tabella seguente mostra i valori hash che verranno generati.

Le	Algoritmo hash (k1 % 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 sopra, i valori 2 e 9 hanno lo stesso valore hash e non possiamo memorizzare più di un valore in ciascuna posizione.

Il problema dato può essere risolto usando il concatenamento o il sondaggio. Le sezioni seguenti discutono in dettaglio il concatenamento e il sondaggio.

chaining

Il concatenamento è una tecnica utilizzata per risolvere il problema della collisione utilizzando elenchi collegati ciascuno con indici univoci.

L'immagine seguente visualizza l'aspetto di un elenco concatenato

Sia 2 che 9 occupano lo stesso indice, ma sono memorizzati come elenchi collegati. Ogni elenco ha un identificatore univoco.

Vantaggi degli elenchi concatenati

Ecco i vantaggi degli elenchi concatenati:

• Gli elenchi concatenati offrono prestazioni migliori durante l'inserimento di dati perché l'ordine di inserimento è O(1).
• Non è necessario ridimensionare una tabella hash che utilizza un elenco concatenato.
• Può contenere facilmente un gran numero 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 in cui memorizzare il nostro valore.

Di seguito sono riportati 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 è avvenuta la collisione e andando avanti. Se viene raggiunta la fine dell'elenco e non viene trovato nessuno slot vuoto. L'indagine inizia dall'inizio dell'elenco.
Sondaggio quadratico	Questo metodo utilizza espressioni polinomiali quadratiche per trovare il successivo slot libero disponibile.
Double hashing	Questa tecnica utilizza un algoritmo di funzione hash secondaria per trovare il successivo slot libero disponibile.

Utilizzando il nostro esempio precedente, la tabella hash dopo aver utilizzato il sondaggio apparirebbe come segue:

Operazioni sulle tabelle hash

Ecco i Operazioni supportate dalle tabelle Hash:

• Inserimento - Questo Operation viene utilizzato per aggiungere un elemento alla tabella hash
• Ricerca - Questo Operation viene utilizzato per cercare elementi nella tabella hash utilizzando la chiave
• Eliminazione - Questo Operazione viene utilizzata per eliminare elementi dalla tabella hash

Operazione di inserimento dati

L'operazione di inserimento viene utilizzata per memorizzare 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.

Cerca l'operazione dati

L'operazione di ricerca viene utilizzata per cercare valori nella tabella hash utilizzando il numero di indice. L'operazione di ricerca restituisce il valore collegato al numero dell'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.

Operazione di eliminazione dei dati

L'operazione di eliminazione viene utilizzata per rimuovere un valore da una tabella hash. Per eliminare il OperaLa cancellazione avviene tramite il numero di indice. Una volta eliminato un valore, il numero di indice viene reso libero. Può essere utilizzato per memorizzare altri valori tramite l'operazione di inserimento.

Implementazione della tabella hash con Python Esempio

Diamo un'occhiata a un semplice esempio che calcola il valore hash di una chiave

def hash_key( key, m):
    return key % m


m = 7

print(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,

1. Definisce una funzione hash_key che accetta i parametri key e m.
2. Utilizza una semplice operazione di modulo per determinare il valore hash
3. Definisce una variabile m inizializzata al valore 7. Questa è la dimensione della nostra tabella hash
4. Calcola e stampa il valore hash di 3
5. Calcola e stampa il valore hash di 2
6. Calcola e stampa il valore hash di 9
7. Calcola e stampa il valore hash di 11
8. Calcola e stampa il valore hash di 7

L'esecuzione del codice sopra riportato produce i seguenti risultati.

The hash value for 3 is 3
The hash value for 2 is 2
The hash value for 9 is 2
The hash value for 11 is 4
The hash value for 7 is 0

Python Esempio di dizionario

Python viene fornito con un tipo di dati integrato chiamato Dizionario. Un dizionario è un esempio di 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 è possibile utilizzare un tipo di dati 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,

1. Definisce un impiegato variabile del dizionario. Il nome della chiave viene utilizzato per archiviare il valore John Doe, l'età memorizza 36 e la posizione memorizza il valore Business Manager.
2. Recupera il valore del nome della chiave e lo stampa nel terminale
3. Aggiorna il valore della posizione chiave al valore Software Engineer
4. Stampa i valori del nome e della posizione dei tasti
5. Elimina tutti i valori memorizzati nella variabile dipendente del nostro dizionario
6. Stampa il valore del dipendente

L'esecuzione del codice sopra riportato 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) nello scenario migliore. 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 tramite sondaggio.

Applicazioni del mondo reale

Nel mondo reale, le tabelle hash vengono utilizzate per archiviare i dati

• Database
• Matrici associative
• Set
• Cache di memoria

Vantaggi delle tabelle hash

Ecco i vantaggi/vantaggi dell'utilizzo delle tabelle hash:

• Le tabelle hash offrono prestazioni elevate durante la ricerca di dati, l'inserimento e l'eliminazione di valori esistenti.
• La complessità temporale delle 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 null come chiave.
• Non è possibile evitare collisioni durante la generazione delle chiavi utilizzando. funzioni hash. Le collisioni si verificano quando viene generata una chiave già in uso.
• Se la funzione di hashing presenta molte collisioni, ciò può portare a un calo delle prestazioni.

Sommario

• Le tabelle hash vengono utilizzate per archiviare 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.
• La tastatura lineare ricerca il successivo slot libero per memorizzare il valore a partire dallo slot dove è avvenuta la collisione.
• Il sondaggio quadratico utilizza espressioni polinomiali per trovare il successivo slot libero quando si verifica una collisione.
• Double l'hashing utilizza un algoritmo della funzione hash secondaria per trovare il successivo slot libero quando si verifica una collisione.
• Le tabelle hash hanno prestazioni migliori rispetto ad altre strutture dati.
• La complessità temporale media delle tabelle hash è O (1)
• Un tipo di dati dizionario in Python è un esempio di tabella hash.
• Le tabelle hash supportano le operazioni di inserimento, ricerca ed eliminazione.
• Un valore null non può essere utilizzato come valore di indice.
• Non è possibile evitare le collisioni nelle funzioni hash. Una buona funzione hash riduce al minimo il numero di collisioni che si verificano per migliorare le prestazioni.