Hash-toiminto
Tässä osiossa käsittelemme hajautusfunktiota, joka auttaa suorittamaan tietorakenteen tietokohteen liittyvän avaimen hash-koodin, kuten seuraavassa mainitaan:
Int hashItem ( int avain ){
palata avain % pöydän koko ;
}
Prosessia taulukon indeksin suorittamiseksi kutsutaan hajautusprosessiksi. Joskus samantyyppinen koodi suoritetaan luomaan sama indeksi käyttämällä samoja avaimia, joita kutsutaan törmäyksiksi ja joita käsitellään erilaisilla ketjutuksilla (linkitettyjen luetteloiden luominen) ja avointen osoitestrategioiden toteutuksella.
Hash-taulukon työskentely C++:ssa
Osoittimet todellisiin arvoihin säilytetään hash-taulukossa. Se etsii avaimen avulla taulukon indeksiä, jossa avaimia vastaan olevat arvot on tallennettava haluttuun paikkaan taulukossa. Otimme hash-taulukon, jonka koko on 10, kuten seuraavassa mainittiin:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Otetaan satunnaisesti mitkä tahansa tiedot eri avaimia vastaan ja tallennetaan nämä avaimet hash-taulukkoon vain laskemalla indeksi. Joten tiedot tallennetaan lasketun indeksin avaimia vasten hash-funktion avulla. Oletetaan, että otamme datan = {14,25,42,55,63,84} ja avaimet =[ 15,9,5,25,66,75 ].
Laske näiden tietojen indeksi hash-funktiolla. Indeksin arvo mainitaan seuraavassa:
| Avain | viisitoista | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Laske indeksi | 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 |
Kun olet luonut taulukon indeksin, sijoita tiedot tietyn taulukon tarkan indeksin avainta vastaan, kuten aiemmin on kuvattu.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Tämän jälkeen voimme nähdä, että törmäys tapahtuu, jos kahdella tai useammalla avaimella on sama hash-koodi, mikä johtaa samaan taulukon elementtien indeksiin. Meillä on yksi ratkaisu välttääksemme törmäysmahdollisuudet: hyvän hajautusmenetelmän valitseminen ja tarkkojen strategioiden toteuttaminen.
Keskustellaan nyt erilaisista toteutustekniikoista oikeiden esimerkkien avulla.
Esimerkki: Lisää data hash-taulukkoon käyttämällä avointa hajautustekniikkaa
Tässä esimerkissä otamme toteutustekniikan, kuten Open Hashingin, välttääksemme törmäyksiä hash-taulukossa. Avoimessa hajautus- tai ketjutuksessa luomme linkitetyn listan hajautustaulukon arvojen ketjuttamiseksi. Tämän esimerkin koodinpätkä on liitetty seuraavassa, joka kuvaa avointa hajautustekniikkaa:
#include#include
luokkaa HashTable {
yksityinen :
staattinen konst int pöydän koko = 10 ;
std :: lista < int > taulukossa on [ pöydän koko ] ;
int hashFunc ( int avain ) {
palata avain % pöydän koko ;
}
julkinen :
mitätön lisää ( int avain ) {
int indeksi = hashFunc ( avain ) ;
taulukossa on [ indeksi ] . työnnä takaisin ( avain ) ;
}
mitätön Näytä Taulukko ( ) {
varten ( int i = 0 ; i < pöydän koko ; ++ i ) {
std :: cout << '[' << i << ']' ;
varten ( auto se = taulukossa on [ i ] . alkaa ( ) ; se ! = taulukossa on [ i ] . loppu ( ) ; ++ se ) {
std :: cout << '->' << * se ;
}
std :: cout << std :: endl ;
}
}
} ;
int pää ( ) {
HashTable hasTable ;
hasTable. lisää ( viisitoista ) ;
hasTable. lisää ( 33 ) ;
hasTable. lisää ( 23 ) ;
hasTable. lisää ( 65 ) ;
hasTable. lisää ( 3 ) ;
hasTable. Näytä Taulukko ( ) ;
palata 0 ;
}
Tämä on erittäin mielenkiintoinen esimerkki: rakennamme linkitetyn luettelon ja lisäämme tiedot hash-taulukkoon. Ensinnäkin määrittelemme kirjastot ohjelman alussa. The < lista > kirjastoa käytetään linkitetyn luettelon toteuttamiseen. Sen jälkeen rakennamme luokan nimeltä “HashTable” ja luomme luokan yksityiset attribuutit taulukkokokona ja taulukkotaulukona käyttämällä “private:”-avainsanaa. Muista, että yksityiset attribuutit eivät ole käytettävissä luokan ulkopuolella. Tässä taulukon kooksi otetaan '10'. Alustamme hash-menetelmän tällä ja laskemme hash-taulukon indeksin. Hajautusfunktiossa välitämme hash-taulukon avaimen ja koon.
Rakennamme muutamia vaadittuja toimintoja ja julkaisemme nämä toiminnot luokassa. Muista, että julkiset toiminnot ovat käytettävissä luokan ulkopuolella missä tahansa. Käytämme 'public:'-avainsanaa luokan julkisen osan aloittamiseen . Koska haluamme lisätä uusia elementtejä hash-taulukkoon, luomme funktion nimeltä 'InsertHash', jossa on funktion argumentti avain. 'Insert'-funktiossa alustamme indeksimuuttujan. Välitämme hash-funktion indeksimuuttujalle. Sen jälkeen välitä indeksimuuttuja linkitetylle listalle tableHas[]push-menetelmällä elementin lisäämiseksi taulukkoon.
Sen jälkeen rakennamme 'viewHashTab'-funktion näyttämään hash-taulukon nähdäksesi juuri lisätyt tiedot. Tässä funktiossa otamme 'for'-silmukan, joka etsii arvoja hash-taulukon loppuun asti. Varmista, että arvot on tallennettu samaan indeksiin, joka on kehitetty hash-funktiolla. Silmukassa välitämme arvot niiden vastaavassa indeksissä ja lopetamme luokan tähän. 'Main'-funktiossa otamme luokan 'hasTable' objektin. Tämän luokkaobjektin avulla pääsemme lisäysmenetelmään antamalla avaimen menetelmässä. Avain, jonka välitimme 'main'-funktiossa, lasketaan 'insert'-funktiossa, joka palauttaa indeksin sijainnin hash-taulukossa. Näytämme hash-taulukon kutsumalla 'view'-funktiota 'Class'-objektin avulla.
Tämän koodin tulos on liitetty seuraavaan:
Kuten näemme, hash-taulukko luodaan onnistuneesti käyttämällä linkitettyä luetteloa C++:ssa. Avointa ketjutusta käytetään välttämään saman indeksin törmäys.
Johtopäätös
Lopulta päätimme, että hash-taulukko on kehittyvin tekniikka arvoparien avainten tallentamiseen ja hankkimiseen valtavien tietomäärien tehokkaaseen käsittelyyn. Hajautustaulukossa törmäysmahdollisuudet ovat erittäin suuret, mikä tuhoaa tiedot ja sen tallennuksen. Voimme voittaa tämän törmäyksen käyttämällä erilaisia hash-taulukon hallinnan tekniikoita. Kehittämällä hash-taulukkoa C++:ssa kehittäjät voivat lisätä suorituskykyä parhaiten sopivalla tekniikalla tietojen tallentamiseen hash-taulukkoon. Toivomme, että tämä artikkeli auttaa ymmärtämään hash-taulukkoa.