Hash funksjon
I denne delen vil vi diskutere om hash-funksjonen som hjelper til med å utføre hash-koden til den relaterte nøkkelen til dataelementet i datastrukturen som nevnt i det følgende:
Int hashItem ( int nøkkel ){
komme tilbake nøkkel % tabellstørrelse ;
}
Prosessen med å utføre indeksen til en matrise kalles hashing. Noen ganger blir den samme typen kode utført for å generere den samme indeksen ved å bruke de samme nøklene kalt kollisjoner som håndteres gjennom forskjellig kjeding (oppretting av koblede lister) og implementering av åpne adresseringsstrategier.
Arbeid av Hash Table i C++
Pekerne til de virkelige verdiene holdes i hash-tabellen. Den bruker en nøkkel for å søke ut indeksen til en matrise der verdiene mot nøklene må lagres på ønsket plassering i en matrise. Vi tok hashtabellen med størrelse 10 som nevnt i følgende:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
La oss tilfeldig ta alle data mot forskjellige nøkler og lagre disse nøklene i en hash-tabell ved bare å beregne indeksen. Så dataene lagres mot nøklene i den beregnede indeksen ved hjelp av en hash-funksjon. Anta at vi tar en data = {14,25,42,55,63,84} og nøkler =[ 15,9,5,25,66,75 ].
Beregn indeksen til disse dataene ved å bruke hash-funksjonen. Indeksverdien er nevnt i følgende:
| Nøkkel | 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 |
Etter å ha opprettet indeksen til en matrise, plasserer du dataene mot nøkkelen på den nøyaktige indeksen til en gitt matrise som beskrevet tidligere.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Etter det kan vi se at en kollisjon oppstår hvis to eller flere nøkler har samme hash-kode som resulterer i samme indeks av elementene i matrisen. Vi har én løsning for å unngå sjansene for kollisjon: å velge en god hash-metode og implementere de nøyaktige strategiene.
La oss nå diskutere de forskjellige implementeringsteknikkene ved hjelp av riktige eksempler.
Eksempel: Legg til data i en hash-tabell ved hjelp av en åpen hashing-teknikk
I dette eksemplet tar vi en implementeringsteknikk som Open Hashing for å unngå kollisjon i hashtabellen. I åpen hashing eller kjeding lager vi en koblet liste for å kjede verdiene til hashtabellen. Kodebiten til dette eksemplet er vedlagt i det følgende som beskriver den åpne hashing-teknikken:
#include#inkluder
klasse HashTable {
privat :
statisk konst int bordstørrelse = 10 ;
std :: liste < int > bordHar [ bordstørrelse ] ;
int hashFunc ( int nøkkel ) {
komme tilbake nøkkel % bordstørrelse ;
}
offentlig :
tomrom sett inn ( int nøkkel ) {
int indeks = hashFunc ( nøkkel ) ;
bordHar [ indeks ] . push_back ( nøkkel ) ;
}
tomrom visningstabell ( ) {
til ( int Jeg = 0 ; Jeg < bordstørrelse ; ++ Jeg ) {
std :: cout << '[' << Jeg << ']' ;
til ( auto den = bordHar [ Jeg ] . begynne ( ) ; den ! = bordHar [ Jeg ] . slutt ( ) ; ++ den ) {
std :: cout << ' -> ' << * den ;
}
std :: cout << std :: endl ;
}
}
} ;
int hoved- ( ) {
HashTable hasTable ;
hasTable. sett inn ( femten ) ;
hasTable. sett inn ( 33 ) ;
hasTable. sett inn ( 23 ) ;
hasTable. sett inn ( 65 ) ;
hasTable. sett inn ( 3 ) ;
hasTable. visningstabell ( ) ;
komme tilbake 0 ;
}
Dette er et veldig interessant eksempel: vi bygger en koblet liste og setter inn dataene i hash-tabellen. Først og fremst definerer vi bibliotekene ved starten av programmet. De < liste > biblioteket brukes for implementeringen av den koblede listen. Etter det bygger vi en klasse kalt 'HashTable' og lager attributtene til klassen som er private som tabellstørrelse og tabellmatrise ved å bruke nøkkelordet 'private:'. Husk at de private attributtene ikke er brukbare utenfor klassen. Her tar vi størrelsen på bordet som '10'. Vi initialiserer hashmetoden ved å bruke denne og beregner indeksen til hashtabellen. I hash-funksjonen sender vi nøkkelen og størrelsen på hash-tabellen.
Vi bygger noen påkrevde funksjoner og gjør disse funksjonene offentlige i klassen. Husk at offentlige funksjoner er brukbare utenfor klassen hvor som helst. Vi bruker nøkkelordet 'public:' for å starte den offentlige delen av klassen . Siden vi ønsker å legge til nye elementer i hash-tabellen, lager vi en funksjon kalt 'InsertHash' med en nøkkel som argument for funksjonen. I funksjonen 'sett inn' initialiserer vi indeksvariabelen. Vi sender hash-funksjonen til indeksvariabelen. Etter det, send indeksvariabelen til den koblede listetabellenHar[]bruke 'push'-metoden for å sette inn et element i tabellen.
Etter det bygger vi en 'viewHashTab'-funksjon for å vise hashtabellen for å se de nylig innsatte dataene. I denne funksjonen tar vi en 'for'-løkke som søker etter verdiene til slutten av hashtabellen. Sørg for at verdiene er lagret i samme indeks som er utviklet ved hjelp av en hash-funksjon. I loopen sender vi verdiene ved deres respektive indeks og avslutter klassen her. I 'hoved'-funksjonen tar vi objektet til en klasse kalt 'hasTable'. Ved hjelp av dette klasseobjektet kan vi få tilgang til metoden for innsetting ved å sende nøkkelen i metoden. Nøkkelen som vi sendte i 'hoved'-funksjonen beregnes i 'sett inn'-funksjonen som returnerer indeksposisjonen i hashtabellen. Vi viste hash-tabellen ved å kalle «view»-funksjonen ved hjelp av et «Class»-objekt.
Utdataene fra denne koden er vedlagt i følgende:
Som vi kan se, er hashtabellen opprettet med hell ved å bruke den koblede listen i C++. Åpen kjetting brukes for å unngå kollisjon av samme indeks.
Konklusjon
Til syvende og sist konkluderte vi med at en hash-tabell er den mest nye teknikken for å lagre og få nøklene med verdipar til å håndtere enorme mengder data effektivt. Sjansene for kollisjon er svært høye i hashtabellen, og ødelegger dataene og lagringen. Vi kan overvinne denne kollisjonen ved å bruke forskjellige teknikker for hashtabellbehandling. Ved å utvikle hashtabellen i C++ kan utviklerne øke ytelsen ved å bruke den best egnede teknikken for å lagre dataene i hashtabellen. Vi håper at denne artikkelen er nyttig for din forståelse av hashtabellen.