hash table c programs implement hash table
Denne opplæringen forklarer C ++ Hash-tabeller og Hash-kart. Du vil også lære om Hash Table-applikasjoner og implementering i C ++:
Hashing er en teknikk der vi kan kartlegge en stor mengde data til en mindre tabell ved hjelp av en “hash-funksjon”.
Ved hjelp av hashingsteknikken kan vi søke i dataene raskere og mer effektivt sammenlignet med andre søketeknikker som lineær og binær søk.
La oss forstå hashingsteknikken med et eksempel i denne opplæringen.
=> Les gjennom Easy C ++ Training Series.
Hva du vil lære:
Hashing In C ++
La oss ta et eksempel på et universitetsbibliotek som huser tusenvis av bøker. Bøkene er ordnet i henhold til emner, avdelinger osv. Men fremdeles vil hver seksjon ha mange bøker som dermed vanskeliggjør søking etter bøker.
For å overvinne denne vanskeligheten tildeler vi altså et unikt nummer eller en nøkkel til hver bok, slik at vi kjenner bokens beliggenhet umiddelbart. Dette oppnås faktisk gjennom hashing.
Fortsetter med vårt bibliotekseksempel, i stedet for å identifisere hver bok basert på avdeling, emne, seksjon osv. Som kan resultere i en veldig lang streng, beregner vi en unik heltallverdi eller nøkkel for hver bok i biblioteket ved hjelp av en unik funksjon og lagre disse nøklene i en egen tabell.
Den unike funksjonen nevnt ovenfor kalles “Hash-funksjonen” og den separate tabellen kalles “Hash-tabellen”. En hash-funksjon brukes til å kartlegge den gitte verdien til en bestemt unik nøkkel i Hash-tabellen. Dette gir raskere tilgang til elementer. Jo mer effektiv hashing-funksjonen er, desto mer effektiv blir kartleggingen av hvert element til den unike nøkkelen.
La oss vurdere en hash-funksjon h (x) som kartlegger verdien “ x ”Ved“ x% 10 ”I matrisen. For de gitte dataene kan vi konstruere en hash-tabell som inneholder nøkler eller Hash-koder eller Hashes som vist i diagrammet nedenfor.
I diagrammet ovenfor kan vi se at oppføringene i matrisen blir kartlagt til deres posisjoner i hash-tabellen ved hjelp av en hash-funksjon.
Dermed kan vi si at hashing er implementert ved hjelp av to trinn som nevnt nedenfor:
#1) Verdien konverteres til en unik heltallnøkkel eller hasj ved hjelp av en hash-funksjon. Den brukes som en indeks for å lagre det opprinnelige elementet, som faller inn i hash-tabellen.
I diagrammet ovenfor er verdi 1 i hash-tabellen den unike nøkkelen til å lagre element 1 fra dataarrayet gitt på LHS i diagrammet.
#to) Elementet fra dataarrayet er lagret i hash-tabellen der det raskt kan hentes ut ved hjelp av hash-nøkkelen. I diagrammet ovenfor så vi at vi har lagret alle elementene i hash-tabellen etter å ha beregnet deres respektive steder ved hjelp av en hash-funksjon. Vi kan bruke følgende uttrykk for å hente hashverdier og indeksere.
hash = hash_func(key) index = hash % array_sizeHash-funksjon
Vi har allerede nevnt at effektiviteten til kartlegging avhenger av effektiviteten til hash-funksjonen vi bruker.
En hash-funksjon bør i utgangspunktet oppfylle følgende krav:
- Enkel å beregne: En hash-funksjon, skal være enkel å beregne de unike tastene.
- Mindre kollisjon: Når elementer tilsvarer de samme nøkkelverdiene, oppstår det en kollisjon. Det bør være minstekollisjoner så langt som mulig i hash-funksjonen som brukes. Ettersom kollisjoner må skje, må vi bruke passende teknikker for å løse kollisjoner for å ivareta kollisjonene.
- Uniform distribusjon: Hash-funksjon bør resultere i en jevn fordeling av data over hash-tabellen og derved forhindre klynging.
Hash-tabell C ++
Hash-tabell eller et hash-kart er en datastruktur som lagrer pekere til elementene i den opprinnelige dataarrayen.
I vårt bibliotekseksempel vil hashtabellen for biblioteket inneholde pekere til hver av bøkene i biblioteket.
Å ha oppføringer i hashtabellen gjør det lettere å søke etter et bestemt element i matrisen.
Som allerede sett bruker hash-tabellen en hash-funksjon for å beregne indeksen i matrisen med bøtter eller spor hvor den ønskede verdien kan bli funnet.
java legge til elementer i en matrise
Tenk på et annet eksempel med følgende dataark:
Anta at vi har en hashtabell i størrelse 10 som vist nedenfor:
La oss nå bruke hash-funksjonen gitt nedenfor.
Hash_code = Key_value % size_of_hash_tableDette tilsvarer Hash_code = Nøkkelverdi% 10
Ved hjelp av funksjonen ovenfor kartlegger vi nøkkelverdiene til hash-tabellplasseringene som vist nedenfor.
| Dataelement | Hash-funksjon | Hash_code |
|---|---|---|
| 22 | 22% 10 = 2 | to |
| 25 | 25% 10 = 5 | 5 |
| 27 | 27% 10 = 7 | 7 |
| 46 | 46% 10 = 6 | 6 |
| 70 | 70% 10 = 0 | 0 |
| 89 | 89% 10 = 9 | 9 |
| 31 | 31% 10 = 1 | 1 |
Ved å bruke tabellen ovenfor kan vi representere hash-tabellen som følger.
Når vi altså trenger tilgang til et element fra hash-tabellen, vil det bare ta O (1) tid å gjøre søket.
Kollisjon
Vi beregner vanligvis hash-koden ved hjelp av hash-funksjonen, slik at vi kan kartlegge nøkkelverdien til hash-koden i hash-tabellen. I det ovennevnte eksemplet på dataarrayen, la oss sette inn en verdi 12. I så fall vil hash_code for nøkkelverdien 12 være 2. (12% 10 = 2).
Men i hash-tabellen har vi allerede en kartlegging til nøkkelverdien 22 for hash_code 2 som vist nedenfor:
Som vist ovenfor har vi den samme hash-koden for to verdier, 12 og 22, dvs. 2. Når en eller flere nøkkelverdier tilsvarer samme sted, resulterer det i en kollisjon. Dermed er hashkodeplasseringen allerede okkupert av en nøkkelverdi, og det er en annen nøkkelverdi som må plasseres på samme sted.
I tilfelle hashing, selv om vi har et hashbord av veldig stor størrelse, vil en kollisjon sannsynligvis være der. Dette er fordi vi finner en liten unik verdi for en stor nøkkel generelt, og det er derfor fullstendig mulig for en eller flere verdier å ha samme hash-kode til enhver tid.
Gitt at en kollisjon er uunngåelig i hashing, bør vi alltid se etter måter å forhindre eller løse kollisjonen på. Det er forskjellige kollisjonsoppløsningsmetoder som vi kan bruke for å løse kollisjonen som skjer under hashing.
Kollisjonsteknikker
Følgende er teknikkene vi kan bruke for å løse kollisjon i hash-tabellen.
Separat lenking (åpen hasjing)
Dette er den vanligste teknikken for oppløsning. Dette er også kjent som åpen hashing og implementeres ved hjelp av en koblet liste.
I egen kjedeteknikk er hver oppføring i hasjetabellen en lenket liste. Når nøkkelen samsvarer med hash-koden, føres den inn i en liste som tilsvarer den aktuelle hash-koden. Dermed når to nøkler har samme hash-kode, blir begge oppføringene lagt inn i den koblede listen.
For eksemplet ovenfor er Separat kjetting representert nedenfor.
Ovenstående diagram representerer kjetting. Her bruker vi mod (%) -funksjonen. Vi ser at når to nøkkelverdier tilsvarer samme hash-kode, kobler vi disse elementene til den hash-koden ved hjelp av en koblet liste.
Hvis nøklene er jevnt fordelt over hasjetabellen, avhenger den gjennomsnittlige kostnaden for å slå opp den bestemte nøkkelen av det gjennomsnittlige antall nøkler i den koblede listen. Dermed forblir separat kjetting effektiv selv når det er en økning i antall oppføringer enn sporene.
Det verste tilfelle for separat kjetting er når alle nøklene tilsvarer den samme hash-koden og dermed bare settes inn i en koblet liste. Derfor må vi se etter alle oppføringene i hashtabellen og kostnaden som er proporsjonal med antall nøkler i tabellen.
Lineær sondering (åpen adressering / lukket hasj)
I åpen adressering eller lineær sonderingsteknikk lagres alle inngangspostene i selve hash-tabellen. Når nøkkelverdien tilordnes til en hash-kode og posisjonen som er pekt med hash-kode er ledig, blir nøkkelverdien satt inn på det stedet.
Hvis posisjonen allerede er opptatt, blir nøkkelverdien satt inn i neste posisjon som er ledig i hash-tabellen ved hjelp av en sonderingssekvens.
For lineær sondering kan hasjefunksjonen endres som vist nedenfor:
hash = hash% hashTableSize
hash = (hash + 1)% hashTableSize
hash = (hash + 2)% hashTableSize
hash = (hash + 3)% hashTableSize
Vi ser at i tilfelle lineær sondering er intervallet mellom spor eller påfølgende sonder konstant, dvs. 1.
I diagrammet ovenfor ser vi det i 0thsted vi skriver inn 10 ved hjelp av hash-funksjonen “hash = hash% hash_tableSize”.
Nå tilsvarer elementet 70 også plassering 0 i hashtabellen. Men den plasseringen er allerede okkupert. Derfor bruker vi lineær sondering det neste stedet som er 1. Ettersom dette stedet ikke er ledig, plasserer vi nøkkelen 70 på dette stedet som vist ved hjelp av en pil.
Den resulterende Hash-tabellen er vist nedenfor.
Lineær sondering kan lide av problemet med 'Primær klynging' der det er en sjanse for at de kontinuerlige cellene kan bli okkupert og sannsynligheten for å sette inn et nytt element blir redusert.
Også hvis to elementer får samme verdi ved den første hashfunksjonen, vil begge disse elementene følge den samme probesekvensen.
Kvadratisk sondering
Kvadratisk sondering er den samme som lineær sondering, med den eneste forskjellen som er intervallet som brukes for sondering. Som navnet antyder, bruker denne teknikken ikke-lineær eller kvadratisk avstand for å oppta spor når det oppstår en kollisjon i stedet for lineær avstand.
I kvadratisk sondering beregnes intervallet mellom sporene ved å legge til en vilkårlig polynomverdi til den allerede hashede indeksen. Denne teknikken reduserer primær gruppering i betydelig grad, men forbedrer ikke sekundær gruppering.
Dobbel hasj
Den dobbelte hashteknikken ligner lineær sondering. Den eneste forskjellen mellom dobbel hashing og lineær sondering er at i dobbel hashing-teknikk blir intervallet brukt for sondering beregnet ved hjelp av to hash-funksjoner. Siden vi bruker hash-funksjonen på nøkkelen etter hverandre, eliminerer den primære klynger så vel som sekundære klynger.
Forskjellen mellom lenking (åpen hasjing) og lineær sondering (åpen adressering)
| Kjetting (åpen hasjing) | Lineær sondering (åpen adressering) |
|---|---|
| Nøkkelverdier kan lagres utenfor tabellen ved hjelp av en egen koblet liste. | Nøkkelverdier skal bare lagres inne i tabellen. |
| Antall elementer i hash-tabellen kan overstige størrelsen på hash-tabellen. | Antall elementer i hash-tabellen vil ikke overstige antall indekser i hash-tabellen. |
| Sletting er effektiv i kjettingsteknikk. | Sletting kan være tungvint. Kan unngås hvis ikke nødvendig. |
| Siden det holdes en egen koblet liste for hvert sted, er plassen stor. | Siden alle oppføringene er plassert i samme tabell, er det mindre plass. |
C ++ Hash Tabell Implementering
Vi kan implementere hashing ved å bruke arrays eller koblede lister til å programmere hash-tabellene. I C ++ har vi også en funksjon kalt “hash map” som er en struktur som ligner på en hash-tabell, men hver oppføring er et nøkkelverdipar. I C ++ kalles det hash-kart eller bare et kart. Hash-kart i C ++ er vanligvis ikke ordnet.
Det er en topptekst definert i Standard Template Library (STL) av C ++ som implementerer kartfunksjonaliteten. Vi har dekket STL Kart i detalj i vår opplæring om STL.
Følgende implementering er for hashing ved å bruke de lenkede listene som datastruktur for hash-tabellen. Vi bruker også 'Chaining' som en teknikk for kollisjonsoppløsning i denne implementeringen.
#include #include using namespace std; class Hashing { int hash_bucket; // No. of buckets // Pointer to an array containing buckets list *hashtable; public: Hashing(int V); // Constructor // inserts a key into hash table void insert_key(int val); // deletes a key from hash table void delete_key(int key); // hash function to map values to key int hashFunction(int x) { return (x % hash_bucket); } void displayHash(); }; Hashing::Hashing(int b) { this->hash_bucket = b; hashtable = new list (hash_bucket); } //insert to hash table void Hashing::insert_key(int key) { int index = hashFunction(key); hashtable(index).push_back(key); } void Hashing::delete_key(int key) { // get the hash index for key int index = hashFunction(key); // find the key in (inex)th list list :: iterator i; for (i = hashtable(index).begin(); i != hashtable(index).end(); i++) { if (*i == key) break; } // if key is found in hash table, remove it if (i != hashtable(index).end()) hashtable(index).erase(i); } // display the hash table void Hashing::displayHash() { for (int i = 0; i ' << x; cout << endl; } } // main program int main() { // array that contains keys to be mapped int hash_array() = {11,12,21, 14, 15}; int n = sizeof(hash_array)/sizeof(hash_array(0)); Hashing h(7); // Number of buckets = 7 //insert the keys into the hash table for (int i = 0; i < n; i++) h.insert_key(hash_array(i)); // display the Hash table cout<<'Hash table created:'< Produksjon:
Hash-tabell opprettet:
0 -> 21 -> 14
1 -> 15
to
3
4 -> 11
5 -> 12
6
Hash-tabell etter sletting av nøkkel 12:
0 -> 21 -> 14
1 -> 15
to
3
4 -> 11
5
6
Utgangen viser en hash-tabell som er laget av størrelse 7. Vi bruker lenking for å løse kollisjon. Vi viser hash-tabellen etter å ha slettet en av tastene.
Bruk av Hashing
# 1) Bekreftelse av passord: Bekreftelse av passord gjøres vanligvis ved hjelp av kryptografiske hashfunksjoner. Når passordet er angitt, beregner systemet passordets hash og sendes deretter til serveren for bekreftelse. På serveren lagres hashverdiene til de originale passordene.
# 2) Datastrukturer: Ulike datastrukturer som unordered_set og unordered_map i C ++, ordbøker i python eller C #, HashSet og hash-kart i Java bruker alle nøkkelverdipar der nøkler er unike verdier. Verdiene kan være de samme for forskjellige taster. Hashing brukes til å implementere disse datastrukturene.
# 3) Message Digest: Dette er enda et program som bruker en kryptografisk hash. I meldingsfordøyelser beregner vi en hash for data som sendes og mottas eller til og med filer og sammenligner dem med de lagrede verdiene for å sikre at det ikke blir manipulert med datafilene. Den vanligste algoritmen her er “SHA 256”.
# 4) Drift av kompilator: Når kompilatoren kompilerer et program, lagres nøkkelordene for programmeringsspråk annerledes enn de andre identifikasjonene. Kompilatoren bruker en hash-tabell for å lagre disse nøkkelordene.
# 5) Databaseindeksering: Hash-tabeller brukes til databaseindeksering og diskbaserte datastrukturer.
# 6) Associative Arrays: Assosiative matriser er matriser hvis indekser er av en annen datatype enn heltallstrenger eller andre objekttyper. Hash-tabeller kan brukes til å implementere assosiative matriser.
Konklusjon
Hashing er den mest brukte datastrukturen ettersom det tar konstant tid O (1) for innsetting, sletting og søkeoperasjoner. Hashing implementeres for det meste ved å bruke en hash-funksjon som beregner en unik mindre nøkkelverdi for store dataoppføringer. Vi kan implementere hashing ved hjelp av arrays og koblede lister.
Når en eller flere dataoppføringer tilsvarer de samme verdiene av nøkler, resulterer det i en kollisjon. Vi har sett forskjellige teknikker for kollisjonsoppløsning, inkludert lineær sondering, kjetting osv. Vi har også sett implementeringen av hashing i C ++.
For å konkludere kan vi si at hashing er den klart mest effektive datastrukturen i programmeringsverdenen.
=> Se etter hele C ++ treningsserien her.
Anbefalt lesing
- Hvordan skrive komplekse forretningslogiske testscenarier ved hjelp av beslutningstabellteknikk
- Feltvalideringstabell (FVT): En testdesignteknikk for feltvalidering
- QTP Opplæring # 15 - Bruk av tekstområde, tabell og sidekontrollpunkter i QTP
- KARTER I STL
- Alt om rutere: Typer rutere, rutetabell og IP-ruting
- Topp 40 beste MySQL intervjuspørsmål og svar (2021 spørsmål)
- Topp 90 SQL-intervjuspørsmål og svar (SISTE)
- Unix Utilities-programmer Kommandoer: Hvilken, Man, Finn Su, Sudo (Del D)