Räsifunktsioon
Selles jaotises käsitleme räsifunktsiooni, mis aitab käivitada andmestruktuuris oleva andmeüksuse seotud võtme räsikoodi, nagu on kirjeldatud järgmises:
Int hashItem ( int võti ){
tagasi võti % laua suurus ;
}
Massiivi indeksi täitmise protsessi nimetatakse räsimiseks. Mõnikord käivitatakse sama tüüpi kood, et luua sama indeks, kasutades samu võtmeid, mida nimetatakse kokkupõrgeteks, mida käsitletakse erineva aheldamise (lingitud loendi loomise) ja avatud adresseerimisstrateegiate rakendamise kaudu.
Räsitabeli töö C++ keeles
Viiteid tegelikele väärtustele hoitakse räsitabelis. See kasutab võtit massiivi indeksi otsimiseks, kus võtmete väärtused tuleb massiivi soovitud asukohta salvestada. Võtsime räsitabeli suurusega 10, nagu on märgitud järgmises:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Võtame juhuslikult kõik andmed erinevate võtmete vastu ja salvestame need võtmed räsitabelisse, arvutades lihtsalt indeksi. Seega salvestatakse andmed arvutatud indeksi võtmete vastu räsifunktsiooni abil. Oletame, et võtame andmed = {14,25,42,55,63,84} ja võtmed =[ 15,9,5,25,66,75].
Arvutage nende andmete indeks räsifunktsiooni abil. Indeksi väärtust mainitakse järgmiselt:
| Võti | viisteist | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Indeksi arvutamine | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Andmed | 14 | 25 | 42 | 55 | 63 | 84 |
Pärast massiivi indeksi loomist asetage andmed antud massiivi täpse indeksi võtme vastu, nagu eelnevalt kirjeldatud.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Pärast seda näeme, et kokkupõrge toimub siis, kui kahel või enamal võtmel on sama räsikood, mille tulemuseks on massiivi elementide sama indeks. Kokkupõrkevõimaluste vältimiseks on meil üks lahendus: hea räsimeetodi valimine ja täpsete strateegiate rakendamine.
Nüüd arutleme erinevate rakendustehnikate üle õigete näidete abil.
Näide: lisage andmed räsitabelisse, kasutades avatud räsitehnikat
Selles näites kasutame räsitabelis kokkupõrgete vältimiseks rakendustehnikat, nagu Open Hashing. Avatud räsimisel või aheldamisel loome lingitud loendi räsitabeli väärtuste aheldamiseks. Selle näite koodilõik on lisatud järgmiselt, mis kirjeldab avatud räsitehnikat:
#include#include
klass HashTable {
privaatne :
staatiline konst int laua suurus = 10 ;
std :: nimekirja < int > laudOn [ laua suurus ] ;
int hashFunc ( int võti ) {
tagasi võti % laua suurus ;
}
avalik :
tühine sisestada ( int võti ) {
int indeks = hashFunc ( võti ) ;
laudOn [ indeks ] . lükka tagasi ( võti ) ;
}
tühine vaatatabel ( ) {
jaoks ( int i = 0 ; i < laua suurus ; ++ i ) {
std :: cout << '[' << i << ']' ;
jaoks ( auto seda = laudOn [ i ] . alustada ( ) ; seda ! = laudOn [ i ] . lõpp ( ) ; ++ seda ) {
std :: cout << ' -> ' << * seda ;
}
std :: cout << std :: endl ;
}
}
} ;
int peamine ( ) {
HashTable hasTable ;
hasTabel. sisestada ( viisteist ) ;
hasTabel. sisestada ( 33 ) ;
hasTabel. sisestada ( 23 ) ;
hasTabel. sisestada ( 65 ) ;
hasTabel. sisestada ( 3 ) ;
hasTabel. vaatatabel ( ) ;
tagasi 0 ;
}
See on väga huvitav näide: koostame lingitud loendi ja sisestame andmed räsitabelisse. Kõigepealt määratleme teegid programmi alguses. The < nimekirja > teeki kasutatakse lingitud loendi rakendamiseks. Pärast seda koostame klassi nimega 'HashTable' ja loome privaatsed klassi atribuudid tabeli suuruse ja tabelimassiivina, kasutades märksõna 'privaatne:'. Pidage meeles, et privaatseid atribuute ei saa kasutada väljaspool klassi. Siin võtame tabeli suuruseks '10'. Initsialiseerime selle abil räsimeetodi ja arvutame räsitabeli indeksi. Räsifunktsioonis edastame räsitabeli võtme ja suuruse.
Ehitame mõned vajalikud funktsioonid ja teeme need funktsioonid klassis avalikuks. Pidage meeles, et avalikud funktsioonid on väljaspool klassi kasutatavad kõikjal. Klassi avaliku osa alustamiseks kasutame märksõna „public:”. . Kuna soovime räsitabelisse lisada uusi elemente, loome funktsiooni nimega “InsertHash”, mille argumendiks on võti. Funktsioonis 'insert' initsialiseerime indeksi muutuja. Me edastame räsifunktsiooni indeksi muutujale. Pärast seda edastage indeksi muutuja lingitud loendisse tableHas[], kasutades 'push' meetodit, et sisestada element tabelisse.
Pärast seda loome funktsiooni 'viewHashTab', et kuvada räsitabel, et näha äsja sisestatud andmeid. Selles funktsioonis võtame 'for' tsükli, mis otsib väärtusi kuni räsitabeli lõpuni. Veenduge, et väärtused oleksid salvestatud samasse indeksisse, mis on välja töötatud räsifunktsiooni abil. Silmuses edastame väärtused nende vastavas indeksis ja lõpetame klassi siin. Funktsioonis 'peamine' võtame klassi 'hasTable' objekti. Selle klassiobjekti abil pääseme sisestamise meetodile ligi, edastades meetodis võtme. Funktsioonis 'peamine' edastatud võti arvutatakse funktsioonis 'insert', mis tagastab indeksi positsiooni räsitabelis. Näitasime räsitabelit, kutsudes välja funktsiooni “View” objekti “Klass” abil.
Selle koodi väljund on lisatud järgmisele:
Nagu näeme, luuakse räsitabel edukalt C++ lingitud loendi abil. Avatud aheldamist kasutatakse sama indeksi kokkupõrke vältimiseks.
Järeldus
Lõppkokkuvõttes jõudsime järeldusele, et räsitabel on kõige levinum meetod väärtuspaaridega võtmete salvestamiseks ja hankimiseks tohutute andmemahtude tõhusaks haldamiseks. Räsitabelis on kokkupõrke tõenäosus väga suur, hävitades andmed ja nende salvestamise. Sellest kokkupõrkest saame üle erinevate räsitabeli haldamise tehnikate abil. Arendades räsitabelit C++ keeles, saavad arendajad jõudlust suurendada, kasutades andmete räsitabelisse salvestamiseks parimat sobivat tehnikat. Loodame, et see artikkel aitab teil räsitabelit mõista.