Spiegazione della tabella hash: che cos'è e come implementarla

Una tabella hash, nota anche come mappa hash, è una struttura di dati che associa le chiavi ai valori. È una parte di una tecnica chiamata hashing, l'altra è una funzione hash. Una funzione hash è un algoritmo che produce un indice di dove è possibile trovare o memorizzare un valore nella tabella hash.

Alcune note importanti sulle tabelle hash:

  1. I valori non vengono memorizzati in un ordine ordinato.
  2. Tieni conto di potenziali collisioni. Questo di solito viene fatto con una tecnica chiamata concatenamento. Concatenare significa creare un elenco collegato di valori, le cui chiavi sono mappate a un determinato indice.

Implementazione di una tabella hash

L'idea alla base dell'hashing è distribuire coppie chiave / valore su una matrice di segnaposto o "bucket" nella tabella hash.

Una tabella hash è in genere un array di elenchi collegati. Quando vuoi inserire una coppia chiave / valore, devi prima usare la funzione hash per mappare la chiave a un indice nella tabella hash. Data una chiave, la funzione hash può suggerire un indice in cui il valore può essere trovato o memorizzato:

index = f(key, array_size)

Questo viene spesso fatto in due passaggi:

hash = hashfunc(key) index = hash % array_size

L'utilizzo di questo metodo hashè indipendente dalla dimensione della tabella hash. hashviene ridotto a un indice, un numero compreso tra 0, l'inizio della matrice e array_size - 1la fine della matrice, utilizzando l'operatore modulo (%).

Considera la seguente stringa S:

string S = “ababcd”

Devi contare la frequenza di tutti i caratteri in S. Il modo più semplice per farlo è scorrere tutti i caratteri possibili e contare la frequenza di ciascuno, uno per uno.

Funziona, ma è lento: la complessità temporale di un tale approccio è O (26 * N), Nessendo la dimensione della stringa Smoltiplicata per 26 possibili caratteri dalla A alla Z.

void countFre(string S) { for(char c = ‘a’;c <= ‘z’;++c) { int frequency = 0; for(int i = 0;i < S.length();++i) if(S[i] == c) frequency++; cout << c << ‘ ‘ << frequency << endl; } }

Produzione:

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Diamo un'occhiata a una soluzione che utilizza l'hashing.

Prendi un array e usa la funzione hash per hash i 26 possibili caratteri con gli indici dell'array. Quindi iterare Se aumentare il valore del carattere corrente della stringa con l'indice corrispondente per ciascun carattere.

La complessità di questo approccio di hashing è O (N), dove N è la dimensione della stringa.

int Frequency[26]; int hashFunc(char c) { return (c - ‘a’); } void countFre(string S) { for(int i = 0;i < S.length();++i) { int index = hashFunc(S[i]); Frequency[index]++; } for(int i = 0;i < 26;++i) cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl; }

Produzione

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Hash Collisions

Poiché la tua mappa hash sarà probabilmente significativamente più piccola della quantità di dati che stai elaborando, le collisioni hash sono inevitabili. Esistono due approcci principali alla gestione delle collisioni: concatenamento e indirizzamento aperto .

Concatenamento

Come accennato in precedenza, il concatenamento significa che ogni coppia chiave / valore nella tabella hash, il valore è un elenco collegato di dati anziché una singola cella.

Ad esempio, immagina che la chiave 152 contenga il valore "John Smith". Se il valore "Sandra Dee" viene aggiunto alla stessa chiave, "Sandra Dee" viene aggiunto come un altro elemento alla chiave 152, subito dopo "John Smith".

152: [["John Smith", "p01"]] ... 152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

Lo svantaggio principale del concatenamento è l'aumento della complessità temporale. Invece di 0 (1) come con una normale tabella hash, ogni ricerca richiederà più tempo poiché è necessario attraversare ogni elenco collegato per trovare il valore corretto.

Indirizzamento aperto

Indirizzamento aperto significa che, una volta mappato un valore a una chiave già occupata, ti muovi lungo le chiavi della tabella hash fino a trovarne una vuota. Ad esempio, se "John Smith" è stato mappato a 152, "Sandra Dee" verrà mappato al successivo indice aperto:

152: ["John Smith", "p01"] ... 152: ["John Smith", "p01"], 153: ["Sandra Dee", "p02"]

Lo svantaggio principale dell'indirizzo aperto è che, quando si cercano valori, potrebbero non trovarsi nella mappa chiave in cui ci si aspetta. Invece, devi attraversare diverse parti della tabella hash per trovare il valore che stai cercando.