Funzione hash
In questa sezione discuteremo della funzione hash che aiuta a eseguire il codice hash della chiave correlata dell'elemento dati nella struttura dati come menzionato di seguito:
Articolo hash int ( int chiave ){
ritorno chiave % Dimensioni della tavola ;
}
Il processo di esecuzione dell'indice di un array è chiamato hashing. A volte, lo stesso tipo di codice viene eseguito per generare lo stesso indice utilizzando le stesse chiavi chiamate collisioni che vengono gestite attraverso diversi concatenamenti (creazione di elenchi collegati) e implementazione di strategie di indirizzamento aperte.
Funzionamento della tabella hash in C++
I puntatori ai valori reali vengono mantenuti nella tabella hash. Utilizza una chiave per cercare l'indice di un array in cui i valori rispetto alle chiavi devono essere archiviati nella posizione desiderata in un array. Abbiamo preso la tabella hash di dimensione 10 come menzionato di seguito:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Prendiamo in modo casuale tutti i dati rispetto a chiavi diverse e memorizziamo queste chiavi in una tabella hash semplicemente calcolando l'indice. Pertanto, i dati vengono archiviati rispetto alle chiavi nell'indice calcolato con l'aiuto di una funzione hash. Supponiamo di prendere dati = {14,25,42,55,63,84} e chiavi =[ 15,9,5,25,66,75 ].
Calcola l'indice di questi dati utilizzando la funzione hash. Il valore dell'indice è menzionato di seguito:
| Chiave | quindici | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Calcola indice | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Dati | 14 | 25 | 42 | 55 | 63 | 84 |
Dopo aver creato l'indice di un array, posizionare i dati rispetto alla chiave sull'indice esatto di un determinato array come descritto in precedenza.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Successivamente, possiamo vedere che si verifica una collisione se due o più chiavi hanno lo stesso codice hash che risulta nello stesso indice degli elementi nell'array. Abbiamo una soluzione per evitare le possibilità di collisione: selezionare un buon metodo di hash e implementare strategie accurate.
Ora, discutiamo le diverse tecniche di implementazione con l’aiuto di esempi appropriati.
Esempio: aggiungere dati in una tabella hash utilizzando una tecnica di hash aperto
In questo esempio, prendiamo una tecnica di implementazione come Open Hashing per evitare collisioni nella tabella hash. Nell'hashing o nel concatenamento aperto, creiamo un elenco collegato per concatenare i valori della tabella hash. Di seguito è allegato lo snippet di codice di questo esempio che descrive la tecnica di hashing aperto:
#include#include
classe HashTable {
privato :
statico cost int Dimensioni della tavola = 10 ;
standard :: elenco < int > tavoloHa [ Dimensioni della tavola ] ;
int hashFunc ( int chiave ) {
ritorno chiave % Dimensioni della tavola ;
}
pubblico :
vuoto inserire ( int chiave ) {
int indice = hashFunc ( chiave ) ;
tavoloHa [ indice ] . respingere ( chiave ) ;
}
vuoto viewTable ( ) {
per ( int io = 0 ; io < Dimensioni della tavola ; ++ io ) {
standard :: cout << '[' << io << ']' ;
per ( auto Esso = tavoloHa [ io ] . inizio ( ) ; Esso ! = tavoloHa [ io ] . FINE ( ) ; ++ Esso ) {
standard :: cout << ' -> ' << * Esso ;
}
standard :: cout << standard :: fine ;
}
}
} ;
int principale ( ) {
HashTable haTable ;
hasTable. inserire ( quindici ) ;
hasTable. inserire ( 33 ) ;
hasTable. inserire ( 23 ) ;
hasTable. inserire ( 65 ) ;
hasTable. inserire ( 3 ) ;
hasTable. viewTable ( ) ;
ritorno 0 ;
}
Questo è un esempio molto interessante: costruiamo una lista concatenata e inseriamo i dati nella tabella hash. Innanzitutto definiamo le librerie all'avvio del programma. IL < elenco > La libreria viene utilizzata per l'implementazione dell'elenco collegato. Successivamente, creiamo una classe denominata 'HashTable' e creiamo gli attributi della classe che sono privati come dimensione della tabella e array di tabelle utilizzando la parola chiave 'private:'. Ricorda che gli attributi privati non sono utilizzabili al di fuori della classe. Qui, prendiamo la dimensione della tabella come “10”. Inizializziamo il metodo hash utilizzando questo e calcoliamo l'indice della tabella hash. Nella funzione hash passiamo la chiave e la dimensione della tabella hash.
Costruiamo alcune funzioni richieste e le rendiamo pubbliche nella classe. Ricorda che le funzioni pubbliche sono utilizzabili al di fuori della classe ovunque. Usiamo la parola chiave “public:” per avviare la parte pubblica della classe . Poiché vogliamo aggiungere nuovi elementi alla tabella hash, creiamo una funzione denominata 'InsertHash' con una chiave come argomento della funzione. Nella funzione “inserisci”, inizializziamo la variabile indice. Passiamo la funzione hash alla variabile indice. Successivamente, passa la variabile indice all'elenco collegato tableHas[]utilizzando il metodo 'push' per inserire un elemento nella tabella.
Successivamente, creiamo una funzione “viewHashTab” per visualizzare la tabella hash per vedere i dati appena inseriti. In questa funzione, prendiamo un ciclo “for” che cerca i valori fino alla fine della tabella hash. Assicurarsi che i valori siano archiviati nello stesso indice sviluppato utilizzando una funzione hash. Nel ciclo passiamo i valori al rispettivo indice e terminiamo qui la classe. Nella funzione “main”, prendiamo l'oggetto di una classe denominata “hasTable”. Con l'aiuto di questo oggetto di classe possiamo accedere al metodo di inserimento passando la chiave nel metodo. La chiave che abbiamo passato nella funzione “main” viene calcolata nella funzione “insert” che restituisce la posizione dell'indice nella tabella hash. Abbiamo visualizzato la tabella hash chiamando la funzione “view” con l'aiuto di un oggetto “Class”.
L'output di questo codice è allegato di seguito:
Come possiamo vedere, la tabella hash viene creata con successo utilizzando l'elenco collegato in C++. Il concatenamento aperto viene utilizzato per evitare la collisione dello stesso indice.
Conclusione
Alla fine, abbiamo concluso che una tabella hash è la tecnica più emergente per archiviare e ottenere chiavi con coppie di valori per gestire enormi quantità di dati in modo efficiente. Le possibilità di collisione sono molto elevate nella tabella hash, distruggendo i dati e la loro archiviazione. Possiamo superare questa collisione utilizzando diverse tecniche di gestione della tabella hash. Sviluppando la tabella hash in C++, gli sviluppatori possono aumentare le prestazioni utilizzando la tecnica più adatta per archiviare i dati nella tabella hash. Ci auguriamo che questo articolo sia utile per comprendere la tabella hash.