Funció hash
En aquesta secció, parlarem de la funció hash que ajuda a executar el codi hash de la clau relacionada de l'element de dades a l'estructura de dades tal com s'esmenta a continuació:
Int hashItem ( int clau ){
tornar clau % mida de la taula ;
}
El procés d'execució de l'índex d'una matriu s'anomena hashing. De vegades, s'executa el mateix tipus de codi per generar el mateix índex utilitzant les mateixes claus anomenades col·lisions que es gestiona mitjançant diferents encadenaments (creació de llistes enllaçades) i implementació d'estratègies d'adreçament obert.
Funcionament de la taula hash en C++
Els punters als valors reals es mantenen a la taula hash. Utilitza una clau per cercar l'índex d'una matriu en què els valors de les claus s'han d'emmagatzemar a la ubicació desitjada d'una matriu. Vam agafar la taula hash de mida 10 tal com s'esmenta a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Prenguem aleatòriament qualsevol dada contra diferents claus i emmagatzemem aquestes claus en una taula hash només calculant l'índex. Per tant, les dades s'emmagatzemen contra les claus de l'índex calculat amb l'ajuda d'una funció hash. Suposem que prenem una dada = {14,25,42,55,63,84} i les claus =[ 15,9,5,25,66,75].
Calcula l'índex d'aquestes dades mitjançant la funció hash. El valor de l'índex s'esmenta a continuació:
| clau | 15 | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Calcula l'índex | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Dades | 14 | 25 | 42 | 55 | 63 | 84 |
Després de crear l'índex d'una matriu, col·loqueu les dades contra la clau a l'índex exacte d'una matriu determinada, tal com s'ha descrit anteriorment.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Després d'això, podem veure que es produeix una col·lisió si dues o més claus tenen el mateix codi hash que resulta en el mateix índex dels elements de la matriu. Tenim una solució per evitar les possibilitats de col·lisió: seleccionar un bon mètode hash i implementar les estratègies precises.
Ara, anem a discutir les diferents tècniques d'implementació amb l'ajuda d'exemples adequats.
Exemple: afegiu una dada a una taula hash utilitzant una tècnica de hash obert
En aquest exemple, prenem una tècnica d'implementació com Open Hashing per evitar col·lisions a la taula hash. En hash obert o encadenat, creem una llista enllaçada per encadenar els valors de la taula hash. El fragment de codi d'aquest exemple s'adjunta a continuació que descriu la tècnica de hash obert:
#inclou#inclou
classe HashTable {
privat :
estàtica const int mida de la taula = 10 ;
std :: llista < int > taulaHas [ mida de la taula ] ;
int hashFunc ( int clau ) {
tornar clau % mida de la taula ;
}
públic :
buit inserir ( int clau ) {
int índex = hashFunc ( clau ) ;
taulaHas [ índex ] . fer retrocedir ( clau ) ;
}
buit veure la taula ( ) {
per ( int i = 0 ; i < mida de la taula ; ++ i ) {
std :: cout << '[' << i << ']' ;
per ( automàtic això = taulaHas [ i ] . començar ( ) ; això ! = taulaHas [ i ] . final ( ) ; ++ això ) {
std :: cout << ' -> ' << * això ;
}
std :: cout << std :: endl ;
}
}
} ;
int principal ( ) {
HashTable té una taula ;
hasTable. inserir ( 15 ) ;
hasTable. inserir ( 33 ) ;
hasTable. inserir ( 23 ) ;
hasTable. inserir ( 65 ) ;
hasTable. inserir ( 3 ) ;
hasTable. veure la taula ( ) ;
tornar 0 ;
}
Aquest és un exemple molt interessant: construïm una llista enllaçada i inserim les dades a la taula hash. En primer lloc, definim les biblioteques a l'inici del programa. El < llista > La biblioteca s'utilitza per a la implementació de la llista enllaçada. Després d'això, construïm una classe anomenada 'HashTable' i creem els atributs de la classe que són privats com a mida de taula i matriu de taula utilitzant la paraula clau 'private:'. Recordeu que els atributs privats no es poden utilitzar fora de la classe. Aquí, prenem la mida de la taula com a '10'. Inicialitzem el mètode hash amb això i calculem l'índex de la taula hash. A la funció hash, passem la clau i la mida de la taula hash.
Creem algunes funcions necessàries i fem públiques aquestes funcions a la classe. Recordeu que les funcions públiques es poden utilitzar fora de la classe a qualsevol lloc. Utilitzem la paraula clau 'public:' per iniciar la part pública de la classe . Com que volem afegir nous elements a la taula hash, creem una funció anomenada 'InsertHash' amb una clau com a argument de la funció. A la funció 'inserir', inicialitzem la variable índex. Passem la funció hash a la variable índex. Després d'això, passeu la variable d'índex a la llista enllaçada tableHas[] mitjançant el mètode 'push' per inserir un element a la taula.
Després d'això, construïm una funció 'viewHashTab' per mostrar la taula hash per veure les dades recentment inserides. En aquesta funció, fem un bucle 'for' que cerca els valors fins al final de la taula hash. Assegureu-vos que els valors s'emmagatzemen al mateix índex que es desenvolupen mitjançant una funció hash. En el bucle, passem els valors al seu índex respectiu i acabem la classe aquí. A la funció 'main', prenem l'objecte d'una classe anomenada 'hasTable'. Amb l'ajuda d'aquest objecte de classe, podem accedir al mètode d'inserció passant la clau al mètode. La clau que hem passat a la funció 'principal' es calcula a la funció 'insereix' que retorna la posició de l'índex a la taula hash. Vam mostrar la taula hash cridant la funció 'visualització' amb l'ajuda d'un objecte 'Class'.
La sortida d'aquest codi s'adjunta a continuació:
Com podem veure, la taula hash es crea amb èxit mitjançant la llista enllaçada en C++. L'encadenament obert s'utilitza per evitar la col·lisió del mateix índex.
Conclusió
Finalment, vam concloure que una taula hash és la tècnica més emergent per emmagatzemar i obtenir les claus amb parells de valors per gestionar grans quantitats de dades de manera eficient. Les possibilitats de col·lisió són molt altes a la taula hash, destruint les dades i el seu emmagatzematge. Podem superar aquesta col·lisió utilitzant diferents tècniques de gestió de la taula hash. En desenvolupar la taula hash en C++, els desenvolupadors poden augmentar el rendiment utilitzant la millor tècnica adequada per emmagatzemar les dades a la taula hash. Esperem que aquest article sigui útil per a la vostra comprensió de la taula hash.