Hash funktion
I dette afsnit vil vi diskutere om hashfunktionen, der hjælper med at udføre hashkoden for den relaterede nøgle til dataelementet i datastrukturen som nævnt i det følgende:
Int hashItem ( int nøgle ){
Vend tilbage nøgle % bordstørrelse ;
}
Processen med at udføre indekset for et array kaldes hashing. Nogle gange udføres den samme type kode for at generere det samme indeks ved hjælp af de samme nøgler kaldet kollisioner, som håndteres gennem forskellige kæder (oprettelse af linkede lister) og implementering af åbne adresseringsstrategier.
Arbejde med Hash Table i C++
Henvisningerne til de reelle værdier gemmes i hash-tabellen. Den bruger en nøgle til at søge efter indekset for et array, hvor værdierne mod nøglerne skal gemmes på den ønskede placering i et array. Vi tog hashtabellen med størrelse 10 som nævnt i følgende:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Lad os tilfældigt tage alle data mod forskellige nøgler og gemme disse nøgler i en hash-tabel ved blot at beregne indekset. Så dataene gemmes mod nøglerne i det beregnede indeks ved hjælp af en hash-funktion. Antag, at vi tager et data = {14,25,42,55,63,84} og nøgler =[ 15,9,5,25,66,75 ].
Beregn indekset for disse data ved hjælp af hash-funktionen. Indeksværdien er nævnt i følgende:
| Nøgle | femten | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Beregn indeks | 15 %10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Data | 14 | 25 | 42 | 55 | 63 | 84 |
Efter at have oprettet indekset for et array, skal du placere dataene mod nøglen på det nøjagtige indeks for et givet array som beskrevet tidligere.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Derefter kan vi se, at der opstår en kollision, hvis to eller flere nøgler har den samme hash-kode, hvilket resulterer i det samme indeks af elementerne i arrayet. Vi har én løsning til at undgå risikoen for kollision: at vælge en god hash-metode og implementere de nøjagtige strategier.
Lad os nu diskutere de forskellige implementeringsteknikker ved hjælp af rigtige eksempler.
Eksempel: Tilføj data i en hash-tabel ved hjælp af en åben hashing-teknik
I dette eksempel tager vi en implementeringsteknik som Open Hashing for at undgå kollision i hashtabellen. I åben hashing eller chaining opretter vi en linket liste for at kæde værdierne i hashtabellen. Kodestykket af dette eksempel er vedhæftet i det følgende, der beskriver den åbne hashing-teknik:
#include#inkluder
klasse HashTabel {
privat :
statisk konst int bordstørrelse = 10 ;
std :: liste < int > bordHar [ bordstørrelse ] ;
int hashFunc ( int nøgle ) {
Vend tilbage nøgle % bordstørrelse ;
}
offentlig :
ugyldig indsætte ( int nøgle ) {
int indeks = hashFunc ( nøgle ) ;
bordHar [ indeks ] . skub tilbage ( nøgle ) ;
}
ugyldig visningstabel ( ) {
til ( int jeg = 0 ; jeg < bordstørrelse ; ++ jeg ) {
std :: cout << '[' << jeg << ']' ;
til ( auto det = bordHar [ jeg ] . begynde ( ) ; det ! = bordHar [ jeg ] . ende ( ) ; ++ det ) {
std :: cout << ' -> ' << * det ;
}
std :: cout << std :: endl ;
}
}
} ;
int vigtigste ( ) {
HashTable hasTable ;
harTabel. indsætte ( femten ) ;
harTabel. indsætte ( 33 ) ;
harTabel. indsætte ( 23 ) ;
harTabel. indsætte ( 65 ) ;
harTabel. indsætte ( 3 ) ;
harTabel. visningstabel ( ) ;
Vend tilbage 0 ;
}
Dette er et meget interessant eksempel: vi bygger en linket liste og indsætter dataene i hash-tabellen. Først og fremmest definerer vi bibliotekerne ved starten af programmet. Det < liste > bibliotek bruges til den linkede listeimplementering. Derefter bygger vi en klasse med navnet 'HashTable' og opretter klassens attributter, der er private som tabelstørrelse og tabelarray ved hjælp af nøgleordet 'private:'. Husk at de private attributter ikke kan bruges uden for klassen. Her tager vi størrelsen på bordet som '10'. Vi initialiserer hashmetoden ved hjælp af denne og beregner indekset for hashtabellen. I hash-funktionen videregiver vi nøglen og størrelsen på hashtabellen.
Vi bygger nogle få påkrævede funktioner og gør disse funktioner offentlige i klassen. Husk at offentlige funktioner kan bruges uden for klassen overalt. Vi bruger nøgleordet 'public:' til at starte den offentlige del af klassen . Da vi ønsker at tilføje nye elementer til hash-tabellen, opretter vi en funktion ved navn 'InsertHash' med en nøgle som argument for funktionen. I funktionen 'indsæt' initialiserer vi indeksvariablen. Vi sender hash-funktionen til indeksvariablen. Derefter skal du sende indeksvariablen til den linkede liste tabelHar[]ved at bruge 'push'-metoden til at indsætte et element i tabellen.
Derefter bygger vi en 'viewHashTab'-funktion til at vise hash-tabellen for at se de nyligt indsatte data. I denne funktion tager vi en 'for'-løkke, der søger efter værdierne indtil slutningen af hash-tabellen. Sørg for, at værdierne er gemt i det samme indeks, som er udviklet ved hjælp af en hash-funktion. I løkken sender vi værdierne ved deres respektive indeks og afslutter klassen her. I 'main'-funktionen tager vi objektet i en klasse ved navn 'hasTable'. Ved hjælp af dette klasseobjekt kan vi få adgang til indsættelsesmetoden ved at sende nøglen i metoden. Nøglen, som vi sendte i 'hoved'-funktionen, beregnes i 'indsæt'-funktionen, der returnerer indekspositionen i hash-tabellen. Vi viste hash-tabellen ved at kalde 'view'-funktionen ved hjælp af et 'Class'-objekt.
Outputtet af denne kode er vedhæftet i følgende:
Som vi kan se, er hash-tabellen oprettet med succes ved hjælp af den linkede liste i C++. Åben kædering bruges til at undgå kollisionen af det samme indeks.
Konklusion
I sidste ende konkluderede vi, at en hash-tabel er den mest nye teknik til at gemme og få nøglerne med værdipar til at håndtere enorme mængder data effektivt. Chancerne for kollision er meget høje i hash-tabellen, hvilket ødelægger dataene og deres lagring. Vi kan overvinde denne kollision ved hjælp af forskellige teknikker til hash-tabellen. Ved at udvikle hashtabellen i C++ kan udviklerne øge ydeevnen ved at bruge den bedst egnede teknik til at gemme dataene i hashtabellen. Vi håber, at denne artikel er nyttig for din forståelse af hash-tabellen.