hash table c programs implement hash table
Ta vadnica pojasnjuje tabele razpršitve C ++ in zemljevide razprševanja. Spoznali boste tudi informacije o aplikacijah in izvedbi tabel razprševanja v jeziku C ++:
Razprševanje je tehnika, s katero lahko s pomočjo 'zgoščevalne funkcije' preslikamo veliko količino podatkov v manjšo tabelo.
S pomočjo tehnike razprševanja lahko podatke iščemo hitreje in učinkoviteje v primerjavi z drugimi tehnikami iskanja, kot sta linearno in binarno iskanje.
Dovolite nam, da razumemo tehniko razprševanja s primerom v tej vadnici.
=> Preberite serijo Easy C ++ Training Series.
Kaj se boste naučili:
- Razpršitev v jeziku C ++
- Izvedba razpršene tabele C ++
- Aplikacije razpršitve
- Zaključek
Razpršitev v jeziku C ++
Vzemimo primer univerzitetne knjižnice, v kateri je na tisoče knjig. Knjige so razporejene po predmetih, oddelkih itd. Kljub temu pa bo v vsakem oddelku veliko knjig, zaradi katerih je iskanje knjig zelo težko.
Da bi premagali to težavo, vsaki knjigi dodelimo edinstveno številko ali ključ, tako da takoj vemo, kje je knjiga. To se res doseže s heširanjem.
Nadaljujemo z našim primerom knjižnice, namesto da bi identificirali vsako knjigo glede na njen oddelek, temo, odsek itd., Kar lahko povzroči zelo dolg niz, izračunamo enolično celoštevilčno vrednost ali ključ za vsako knjigo v knjižnici z uporabo edinstvene funkcije in shranite te ključe v ločeno tabelo.
Zgoraj omenjena edinstvena funkcija se imenuje 'Hash function', ločena tabela pa 'Hash Table'. Razpršilna funkcija se uporablja za preslikavo dane vrednosti na določen unikatni ključ v razpredelnici. To ima za posledico hitrejši dostop do elementov. Bolj kot je učinkovita funkcija zgoščevanja, učinkovitejše bo preslikava vsakega elementa v unikatni ključ.
Upoštevajmo zgoščeno funkcijo h (x) ki preslika vrednost ' x 'Ob' x% 10 «V polju. Za dane podatke lahko sestavimo razpršilno tabelo, ki vsebuje ključe ali Hash kode ali Hashe, kot je prikazano na spodnjem diagramu.
V zgornjem diagramu lahko vidimo, da so vnosi v matriki preslikani na svoja mesta v tabeli razprševanja s pomočjo razpršitvene funkcije.
Tako lahko rečemo, da se zgoščevanje izvaja v dveh korakih, kot je navedeno spodaj:
# 1) Vrednost se pretvori v enolični celoštevilski ključ ali zgoščeno s pomočjo zgoščevalne funkcije. Uporablja se kot indeks za shranjevanje prvotnega elementa, ki pade v razpršilno tabelo.
V zgornjem diagramu je vrednost 1 v razpršeni tabeli edinstveni ključ za shranjevanje elementa 1 iz podatkovnega polja, podanega na LHS diagrama.
#two) Element iz podatkovne matrike je shranjen v tabeli zgoščevanja, kjer ga je mogoče hitro pridobiti s pomočjo zgoščenega ključa. V zgornjem diagramu smo videli, da smo vse elemente shranili v tabelo zgoščevanja, potem ko smo s pomočjo funkcije zgoščevanja izračunali njihove lokacije. Za pridobivanje zgoščenih vrednosti in indeksa lahko uporabimo naslednje izraze.
hash = hash_func(key) index = hash % array_sizeFunkcija razpršitve
Omenili smo že, da je učinkovitost preslikave odvisna od učinkovitosti zgoščevalne funkcije, ki jo uporabljamo.
Hash funkcija mora v bistvu izpolnjevati naslednje zahteve:
- Enostaven za izračun: Hash funkcija bi morala biti enostavna za izračun unikatnih ključev.
- Manj trkov: Ko se elementi enačijo z enakimi ključnimi vrednostmi, pride do trka. V uporabljeni funkciji zgoščevanja mora biti čim manj trkov. Ker se trki zagotovo lahko pojavijo, moramo za trčenje uporabiti ustrezne tehnike reševanja trkov.
- Enotna distribucija: Funkcija razpršitve bi morala imeti za posledico enakomerno porazdelitev podatkov po razpredelnici in s tem preprečiti združevanje v gruče.
Tabela razpršitve C ++
Hash tabela ali zemljevid razprševanja je podatkovna struktura, ki shranjuje kazalce na elemente izvirne podatkovne matrike.
V našem primeru knjižnice bo hash tabela za knjižnico vsebovala kazalce na vsako knjigo v knjižnici.
nedefinirano sklicevanje na glavni c ++
Če imate vnose v tabeli razprševanja, olajšate iskanje določenega elementa v matriki.
Kot smo že videli, hash tabela uporablja hash funkcijo za izračun indeksa v matriko vedrov ali rež, s pomočjo katerih je mogoče najti želeno vrednost.
Razmislite o drugem primeru z naslednjim podatkovnim poljem:
Predpostavimo, da imamo razpršeno tabelo velikosti 10, kot je prikazano spodaj:
Zdaj pa uporabimo spodaj navedeno funkcijo zgoščevanja.
Hash_code = Key_value % size_of_hash_tableTo bo enakovredno Hash_code = Ključna_vrednost% 10
Z uporabo zgornje funkcije preslikamo vrednosti ključev na mesta razprševalne tabele, kot je prikazano spodaj.
| Podatkovna postavka | Funkcija razpršitve | Hash_code |
|---|---|---|
| 22. | 22% 10 = 2 | dva |
| 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. |
Z uporabo zgornje tabele lahko heš tabelo predstavimo na naslednji način.
Ko moramo torej do elementa dostopati iz zgoščene tabele, bo za iskanje potreboval le O (1) čas.
Trčenje
Običajno izračunamo zgoščevalno kodo s pomočjo zgoščevalne funkcije, tako da lahko vrednost ključa preslikamo na razpršilno kodo v razpredelniški tabeli. V zgornji primer podatkovnega polja vstavimo vrednost 12. V tem primeru bo hash_code za ključno vrednost 12 2. (12% 10 = 2).
Toda v tabeli zgoščevanja že imamo preslikavo na ključ-vrednost 22 za hash_code 2, kot je prikazano spodaj:
Kot je prikazano zgoraj, imamo isto razpršilno kodo za dve vrednosti, 12 in 22, tj. 2. Ko ena ali več ključnih vrednosti enači isti lokaciji, pride do trka. Tako je lokacija hash kode že zasedena z eno vrednostjo ključa, obstaja pa še ena vrednost ključa, ki jo je treba postaviti na isto mesto.
V primeru razpršitve, tudi če imamo razpršilno tabelo zelo velike velikosti, bo trk zagotovo prisoten. To je zato, ker na splošno najdemo majhno unikatno vrednost za velik ključ, zato je popolnoma mogoče, da ima ena ali več vrednosti kadar koli isto hash kodo.
Glede na to, da je trčenje pri razprševanju neizogibno, moramo vedno iskati načine, kako trčenje preprečiti ali razrešiti. Obstajajo različne tehnike reševanja trkov, ki jih lahko uporabimo za razrešitev trka, ki se zgodi med zgoščevanjem.
Tehnike reševanja trkov
Sledijo tehnike, ki jih lahko uporabimo za razrešitev trkov v razpršeni tabeli.
Ločeno veriženje (odprto razprševanje)
To je najpogostejša tehnika reševanja trkov. To je znano tudi kot odprto razprševanje in se izvaja s povezanim seznamom.
aplikacije, ki omogočajo prenos youtube videoposnetkov
V ločeni tehniki veriženja je vsak vnos v tabeli razprševanja povezan seznam. Ko se ključ ujema s hash kodo, se vnese na seznam, ki ustreza tej hash kodo. Torej, če imata dva ključa isto hash kodo, se oba vnosa vneseta na povezani seznam.
V zgornjem primeru je spodaj predstavljeno ločeno veriženje.
Zgornji diagram predstavlja veriženje. Tu uporabljamo funkcijo mod (%). Vidimo, da kadar sta dve ključni vrednosti enaki isti hash kodo, potem te elemente povežemo s to hash kodo s povezanim seznamom.
Če so ključi enakomerno porazdeljeni po razpršeni tabeli, so povprečni stroški iskanja določenega ključa odvisni od povprečnega števila ključev na povezanem seznamu. Tako ločena veriga ostaja učinkovita tudi, če se število vnosov poveča kot reže.
Najslabši primer za ločeno veriženje je, če so vsi ključi enaki isti hash kodi in so tako vstavljeni samo na en povezan seznam. Zato moramo poiskati vse vnose v zgoščeno tabelo in stroške, ki so sorazmerni številu ključev v tabeli.
Linearno sondiranje (odprto naslavljanje / zaprto razprševanje)
Pri tehniki odprtega naslavljanja ali linearnega tipanja se vsi vnosni zapisi shranijo v samo razpršilno tabelo. Ko se ključ-vrednost preslika v hash kodo in položaj, na katerega kaže hash code, ni zaseden, se vrednost ključa vstavi na to mesto.
Če je položaj že zaseden, se s tipalnim zaporedjem vrednost ključa vstavi v naslednji položaj, ki je v tabeli razprševanja nezaseden.
Za linearno sondiranje se lahko zgoščevalna funkcija spremeni, kot je prikazano spodaj:
hash = hash% hashTableSize
hash = (hash + 1)% hashTableSize
hash = (hash + 2)% hashTableSize
hash = (hash + 3)% hashTableSize
Vidimo, da je v primeru linearnega sondiranja interval med režami ali zaporednimi sondami konstanten, tj.
V zgornjem diagramu vidimo, da je v 0thmesto vnesemo 10 s pomočjo zgoščevalne funkcije “hash = hash% hash_tableSize”.
Zdaj je element 70 enak tudi lokaciji 0 v razpršeni tabeli. Toda ta lokacija je že zasedena. Zato bomo z linearnim sondiranjem našli naslednjo lokacijo, ki je 1. Ker je ta lokacija nezasedena, na to mesto postavimo ključ 70, kot je prikazano s puščico.
Nastala tabela razpršitve je prikazana spodaj.
Linearno sondiranje lahko trpi zaradi težave »Primarno združevanje«, pri kateri obstaja verjetnost, da se neprekinjene celice zasedejo in zmanjša verjetnost vstavljanja novega elementa.
Tudi če dva elementa dobita enako vrednost pri prvi zgoščevalni funkciji, potem bosta oba elementa sledila istemu zaporedju sonde.
Kvadratno sondiranje
Kvadratno sondiranje je enako kot linearno sondiranje, edina razlika je interval, ki se uporablja za sondiranje. Kot že ime pove, ta tehnika uporablja nelinearno ali kvadratno razdaljo, da zasede reže, ko pride do trka namesto linearne razdalje.
Pri kvadratnem sondiranju se interval med režami izračuna z dodajanjem poljubne polinomske vrednosti že zgoščenemu indeksu. Ta tehnika znatno zmanjša primarno združevanje v skupine, ne izboljša pa se pri sekundarnem združevanju.
Dvojno razprševanje
Tehnika dvojnega razprševanja je podobna linearnemu tipanju. Edina razlika med dvojnim razprševanjem in linearnim sondiranjem je, da se pri tehniki dvojnega razprševanja interval, uporabljen za tipanje, izračuna z uporabo dveh zgoščevalnih funkcij. Ker funkcijo zgoščevanja uporabljamo za ključ enega za drugim, odpravlja primarno in sekundarno združevanje.
Razlika med veriženjem (odprto razprševanje) in linearnim sondiranjem (odprto naslavljanje)
| Veriženje (odprto razprševanje) | Linearno sondiranje (odprto naslavljanje) |
|---|---|
| Vrednosti ključev lahko shranite zunaj tabele z ločenim povezanim seznamom. | Vrednosti ključev naj bodo shranjene samo v tabeli. |
| Število elementov v razpredelnici lahko presega velikost razpredelnice. | Število elementov, ki so prisotni v zgoščevalni tabeli, ne bo presegalo števila indeksov v zgoščevalni tabeli. |
| Delecija je učinkovita pri tehniki veriženja. | Izbris je lahko okoren. Če se ne zahteva, se mu je mogoče izogniti. |
| Ker se za vsako lokacijo vodi ločen povezan seznam, je zasedeni prostor velik. | Ker so vsi vnosi v isti tabeli, je zasedenega prostora manj. |
Izvedba razpršene tabele C ++
Razprševanje lahko izvedemo z uporabo nizov ali povezanih seznamov za programiranje razprševalnih tabel. V C ++ imamo tudi funkcijo, imenovano 'hash map', ki je struktura, podobna hash tabeli, vendar je vsak vnos par ključ-vrednost. V C ++ se imenuje hash map ali preprosto zemljevid. Zemljevid razpršitev v jeziku C ++ je običajno neurejen.
V knjižnici standardnih predlog (STL) C ++ je definirana glava, ki izvaja funkcionalnost zemljevidov. Pokrili smo Zemljevidi STL podrobno v naši vadnici o STL.
Naslednja izvedba je namenjena zgoščevanju z uporabo povezanih seznamov kot podatkovne strukture za razpršilno tabelo. Pri tej izvedbi uporabljamo tudi 'Chaining' kot tehniko reševanja trkov.
#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:'< Izhod:
Ustvarjena je razpredelnica:
0 -> 21 -> 14
1 -> 15
dva
3.
4 -> 11
5 -> 12
6.
ukaz grep v unixu s primeri
Hash tabela po izbrisu ključa 12:
0 -> 21 -> 14
1 -> 15
dva
3.
4 -> 11
5.
6.
Izhod prikazuje heš tabelo, ki je ustvarjena velikosti 7. Za razrešitev trka uporabljamo veriženje. Hash tabelo prikažemo po brisanju ene od tipk.
Aplikacije razpršitve
# 1) Preverjanje gesel: Preverjanje gesel se običajno opravi s pomočjo kriptografskih zgoščevalnih funkcij. Ko je geslo vneseno, sistem izračuna zgoščeno geslo in ga nato pošlje strežniku v preverjanje. Na strežniku so shranjene zgoščene vrednosti prvotnih gesel.
# 2) Strukture podatkov: Različne strukture podatkov, kot so neurejeni_nabor in neurejena_mapa v jeziku C ++, slovarji v pythonu ali C #, HashSet in zemljevid razprševanja v Javi, uporabljajo par ključ-vrednost, pri čemer so ključi enolične vrednosti. Vrednosti so lahko enake za različne tipke. Za izvajanje teh podatkovnih struktur se uporablja razpršitev.
# 3) Povzetek sporočila: To je še ena aplikacija, ki uporablja kriptografsko razpršitev. V povzetkih sporočil izračunamo razpršitev za podatke, ki jih pošiljamo in prejemamo ali celo datoteke, in jih primerjamo s shranjenimi vrednostmi, da zagotovimo, da podatkovne datoteke niso posežene. Najpogostejši algoritem tukaj je »SHA 256«.
# 4) Delovanje prevajalnika: Ko prevajalnik prevede program, se ključne besede za programski jezik shranijo drugače kot drugi identificira. Prevajalnik uporablja tabelo zgoščevanja za shranjevanje teh ključnih besed.
# 5) Indeksiranje zbirke podatkov: Hash tabele se uporabljajo za indeksiranje baz podatkov in podatkovne strukture na osnovi diska.
# 6) Asociativni nizi: Asociativni nizi so nizi, katerih indeksi so podatkovnega tipa, ki niso celoštevilski nizi ali druge vrste predmetov. Hash tabele se lahko uporabljajo za izvajanje asociativnih nizov.
Zaključek
Razpršitev je najpogosteje uporabljena podatkovna struktura, saj traja konstanten čas O (1) za vstavljanje, brisanje in iskanje. Razprševanje se večinoma izvaja z uporabo zgoščevalne funkcije, ki izračuna edinstveno manjšo vrednost ključa za velike vnose podatkov. Razprševanje lahko izvedemo z uporabo nizov in povezanih seznamov.
Kadar se en ali več vnosov podatkov enači z enakimi vrednostmi ključev, pride do trka. Opazili smo različne tehnike reševanja trkov, vključno z linearnim testiranjem, veriženjem itd. Videli smo tudi izvajanje razprševanja v jeziku C ++.
Za konec lahko rečemo, da je zgoščevanje daleč najučinkovitejša podatkovna struktura v programskem svetu.
=> Poiščite celotno serijo usposabljanj za C ++ tukaj.
Priporočeno branje
- Kako napisati kompleksne scenarije preizkusa poslovne logike s tehniko odločitvenih tabel
- Tabela validacije polja (FVT): Tehnika zasnove testa za validacijo polja
- Vadnica QTP št. 15 - Uporaba kontrolnih točk za območje besedila, tabele in strani v QTP
- KARTE V STL
- Vse o usmerjevalnikih: vrste usmerjevalnikov, usmerjevalna tabela in usmerjanje IP
- 40 najboljših vprašanj in odgovorov za intervju z MySQL (2021 vprašanj)
- Najpogostejših 90 vprašanj in odgovorov na vprašanja v zvezi z SQL (NAJNOVEJ)
- Ukazi programa Unix Utilities: Which, Man, Find Su, Sudo (Del D)