hash table c programs implement hash table
V tomto výučbe sú vysvetlené tabuľky hash C ++ a mapy hashov. Dozviete sa tiež o aplikáciách a implementácii tabuľky hash v C ++:
Hashing je technika, pomocou ktorej môžeme pomocou „hashovacej funkcie“ mapovať veľké množstvo údajov na menšiu tabuľku.
Pomocou hashovacej techniky môžeme vyhľadávať údaje rýchlejšie a efektívnejšie v porovnaní s inými vyhľadávacími technikami, ako je lineárne a binárne vyhľadávanie.
Pochopme techniku hashovania pomocou príkladu v tomto tutoriále.
=> Prečítajte si sériu Easy C ++ Training Series.
Čo sa dozviete:
- Hašovanie v C ++
- Implementácia tabuľky hash C ++
- Aplikácie hashovania
- Záver
Hašovanie v C ++
Vezmime si príklad univerzitnej knižnice, v ktorej sú tisíce kníh. Knihy sú usporiadané podľa predmetov, oddelení atď. Každá sekcia však bude mať množstvo kníh, vďaka čomu je hľadanie kníh veľmi ťažké.
Aby sme teda prekonali túto ťažkosť, každej knihe priradíme jedinečné číslo alebo kľúč, aby sme okamžite vedeli, kde sa kniha nachádza. To sa skutočne dosahuje hašovaním.
Pokračujeme v našom príklade z knižnice. Namiesto identifikácie každej knihy na základe jej oddelenia, predmetu, sekcie atď., Ktoré môžu viesť k veľmi dlhému reťazcu, vypočítame pre každú knihu v knižnici jedinečnú celočíselnú hodnotu alebo kľúč pomocou jedinečnej funkcie a tieto kľúče uložte do samostatnej tabuľky.
Vyššie uvedená jedinečná funkcia sa nazýva „Hash funkcia“ a samostatná tabuľka sa nazýva „Hash Table“. Hašovacia funkcia sa používa na mapovanie danej hodnoty na konkrétny jedinečný kľúč v tabuľke hash. Výsledkom je rýchlejší prístup k prvkom. Čím efektívnejšia je funkcia hash, tým efektívnejšie bude mapovanie každého prvku na jedinečný kľúč.
Uvažujme o hashovacej funkcii h (x) ktorá mapuje hodnotu „ X ”O“ x% 10 ”V poli. Pre dané dáta môžeme zostrojiť hashovaciu tabuľku obsahujúcu kľúče alebo hašovacie kódy alebo hašéry, ako je znázornené na nasledujúcom diagrame.
Na vyššie uvedenom diagrame vidíme, že položky v poli sú pomocou hašovacej funkcie mapované na ich pozície v hashovacej tabuľke.
Môžeme teda povedať, že hašovanie sa implementuje pomocou dvoch krokov, ktoré sú uvedené nižšie:
# 1) Hodnota sa prevedie na jedinečný celočíselný kľúč alebo hash pomocou hashovacej funkcie. Používa sa ako index na uloženie pôvodného prvku, ktorý spadá do hashovacej tabuľky.
Vo vyššie uvedenom diagrame je hodnota 1 v hashovacej tabuľke jedinečným kľúčom na uloženie prvku 1 z dátového poľa uvedeného na LHS diagramu.
#dva) Prvok z dátového poľa je uložený v hašovacej tabuľke, kde ho možno rýchlo získať pomocou hašovaného kľúča. Na vyššie uvedenom diagrame sme videli, že sme uložili všetky prvky do hashovacej tabuľky po výpočte ich príslušných umiestnení pomocou hashovacej funkcie. Na získanie hašovacích hodnôt a indexov môžeme použiť nasledujúce výrazy.
hash = hash_func(key) index = hash % array_sizeFunkcia hash
Už sme spomenuli, že efektívnosť mapovania závisí od účinnosti hashovacej funkcie, ktorú používame.
Hašovacia funkcia by v zásade mala spĺňať nasledujúce požiadavky:
- Ľahko vypočítateľný: Hašovacia funkcia by mala byť ľahká pri výpočte jedinečných klávesov.
- Menej kolízie: Keď sa prvky rovnajú rovnakým kľúčovým hodnotám, dôjde ku kolízii. V použitej hashovacej funkcii by malo dochádzať k čo najmenším možným kolíziám. Pretože ku kolíziám určite dôjde, musíme na ich zvládnutie použiť príslušné techniky riešenia kolízií.
- Rovnomerné rozdelenie: Výsledkom hashovacej funkcie by malo byť rovnomerné rozdelenie údajov v hashovacej tabuľke a zabrániť tak klastrovaniu.
Tabuľka hash C ++
Hašovacia tabuľka alebo hašovacia mapa je dátová štruktúra, ktorá uchováva ukazovatele na prvky pôvodného dátového poľa.
V našom príklade knižnice bude hašovacia tabuľka pre knižnicu obsahovať ukazovatele na každú z kníh v knižnici.
Mať záznamy v hashovacej tabuľke uľahčuje hľadanie konkrétneho prvku v poli.
Ako už bolo vidieť, hašovacia tabuľka používa hashovaciu funkciu na výpočet indexu do poľa segmentov alebo slotov, pomocou ktorých možno nájsť požadovanú hodnotu.
Zvážte ďalší príklad s nasledujúcim údajovým poľom:
Predpokladajme, že máme hashovaciu tabuľku veľkosti 10, ako je uvedené nižšie:
Teraz použijeme hashovaciu funkciu uvedenú nižšie.
Hash_code = Key_value % size_of_hash_tableTo sa bude rovnať Hash_code = Key_value% 10
Pomocou vyššie uvedenej funkcie mapujeme kľúčové hodnoty na umiestnenia tabuľky hash, ako je uvedené nižšie.
| Údajová položka | Funkcia hash | 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 | jeden |
Pomocou vyššie uvedenej tabuľky môžeme reprezentovať hashovaciu tabuľku nasledovne.
Keď teda potrebujeme získať prístup k prvku z hashovacej tabuľky, hľadanie bude trvať iba O (1).
Zrážka
Hašovací kód zvyčajne vypočítame pomocou hashovacej funkcie, aby sme mohli kľúčovú hodnotu namapovať na hašovací kód v hashovacej tabuľke. Vo vyššie uvedenom príklade dátového poľa vložme hodnotu 12. V takom prípade bude hash_code pre kľúčovú hodnotu 12 hodnotu 2. (12% 10 = 2).
Ale v hashovacej tabuľke už máme mapovanie na pár kľúč - hodnota 22 pre hash_code 2, ako je uvedené nižšie:
Ako je uvedené vyššie, máme rovnaký hash kód pre dve hodnoty, 12 a 22, tj. 2. Keď sa jedna alebo viac kľúčových hodnôt rovná rovnakému miestu, vedie to ku kolízii. Umiestnenie hašovacieho kódu je teda už obsadené jednou kľúčovou hodnotou a na rovnakom mieste je potrebné umiestniť ďalšiu kľúčovú hodnotu.
V prípade hašovania, aj keď máme hašovací stôl veľmi veľkých rozmerov, musí dôjsť ku kolízii. Je to tak preto, lebo všeobecne nájdeme malú jedinečnú hodnotu pre veľký kľúč, a preto je úplne možné, aby jedna alebo viac hodnôt mala v rovnakom čase rovnaký hash kód.
Vzhľadom na to, že pri hašovaní je zrážka nevyhnutná, mali by sme vždy hľadať spôsoby, ako zrážke zabrániť alebo ju vyriešiť. Existujú rôzne techniky riešenia kolízií, ktoré môžeme použiť na vyriešenie kolízie, ku ktorej dôjde pri hašovaní.
Techniky riešenia kolízií
Nasledujú techniky, ktoré môžeme použiť na riešenie kolízií v hashovacej tabuľke.
Samostatné reťazenie (otvorené hashovanie)
Toto je najbežnejšia technika riešenia kolízií. Toto sa nazýva aj otvorené hashovanie a implementuje sa pomocou prepojeného zoznamu.
V samostatnej reťazovej technike je každá položka v hashovacej tabuľke prepojeným zoznamom. Keď sa kľúč zhoduje s hašovacím kódom, zapíše sa do zoznamu zodpovedajúceho konkrétnemu hash kódu. Ak majú teda dva kľúče rovnaký hash kód, potom sa obidve položky zadajú do prepojeného zoznamu.
Pre vyššie uvedený príklad je nižšie zobrazené Samostatné reťazenie.
Vyššie uvedený diagram predstavuje reťazenie. Tu používame funkciu mod (%). Vidíme, že keď sa dve kľúčové hodnoty rovnajú rovnakému hash kódu, spojíme tieto prvky s týmto hash kódom pomocou prepojeného zoznamu.
Ak sú kľúče rovnomerne rozložené v hashovacej tabuľke, potom priemerné náklady na vyhľadanie konkrétneho kľúča závisia od priemerného počtu kľúčov v danom prepojenom zozname. Samostatné reťazenie tak zostáva účinné, aj keď dôjde k zvýšeniu počtu vstupov ako slotov.
Najhorším prípadom samostatného reťazenia je, keď sa všetky kľúče rovnajú rovnakému hash kódu, a teda sú vložené iba do jedného prepojeného zoznamu. Preto musíme vyhľadať všetky záznamy v hašovacej tabuľke a náklady, ktoré sú úmerné počtu kľúčov v tabuľke.
Lineárne sondovanie (otvorené adresovanie / uzavreté hashovanie)
Pri technike otvoreného adresovania alebo lineárneho sondovania sú všetky vstupné záznamy uložené v samotnej hashovacej tabuľke. Keď sa kľúč - hodnota mapuje na hash kód a pozícia, na ktorú ukazuje hash kód, je neobsadená, potom sa hodnota kľúča vloží na dané miesto.
Ak je pozícia už obsadená, potom sa pomocou sondovacej sekvencie vloží hodnota kľúča na ďalšiu pozíciu, ktorá nie je obsadená v hašovacej tabuľke.
Pri lineárnom snímaní sa funkcia hash môže meniť, ako je uvedené nižšie:
hash = hash% hashTableSize
hash = (hash + 1)% hashTableSize
hash = (hash + 2)% hashTableSize
hash = (hash + 3)% hashTableSize
Vidíme, že v prípade lineárneho sondovania je interval medzi slotmi alebo nasledujúcimi sondami konštantný, t. J. 1.
Na vyššie uvedenom diagrame vidíme, že na nulethumiestnenie zadáme 10 pomocou hashovacej funkcie „hash = hash% hash_tableSize“.
Teraz sa prvok 70 rovná aj pozícii 0 v hashovacej tabuľke. Ale toto miesto je už obsadené. Preto pomocou lineárneho sondovania nájdeme ďalšie miesto, ktoré je 1. Pretože toto miesto nie je obsadené, umiestnime kláves 70 na toto miesto, ako je to znázornené pomocou šípky.
Výsledná tabuľka hash je uvedená nižšie.
Lineárne snímanie môže trpieť problémom „primárneho zhlukovania“, pri ktorom existuje šanca, že sa spojité bunky môžu obsadiť a pravdepodobnosť vloženia nového prvku sa zníži.
Rovnako, ak dva prvky získajú pri prvej hashovacej funkcii rovnakú hodnotu, potom budú tieto dva prvky sledovať rovnakú postupnosť sondy.
Kvadratické sondovanie
Kvadratické sondovanie je rovnaké ako lineárne sondovanie, pričom jediným rozdielom je interval použitý na sondovanie. Ako naznačuje názov, táto technika využíva nelineárnu alebo kvadratickú vzdialenosť na obsadenie slotov, keď dôjde ku kolízii, namiesto lineárnej vzdialenosti.
Pri kvadratickom sondovaní sa interval medzi slotmi počíta tak, že sa k už hašovanému indexu pridá ľubovoľná polynomiálna hodnota. Táto technika významne obmedzuje primárne klastrovanie, ale pri sekundárnom klastrovaní sa nezlepšuje.
Double Hashing
Technika dvojitého hashovania je podobná lineárnemu sondovaniu. Jediný rozdiel medzi dvojitým hashovaním a lineárnym sondovaním je ten, že pri technike dvojitého hashovania sa interval použitý na sondovanie počíta pomocou dvoch hashových funkcií. Pretože na kľúč jednu po druhej aplikujeme hashovaciu funkciu, eliminuje sa primárne aj sekundárne zoskupovanie.
Rozdiel medzi reťazením (otvorené hashovanie) a lineárnym sondovaním (otvorené adresovanie)
| Reťazenie (otvorené hashovanie) | Lineárne sondovanie (otvorené adresovanie) |
|---|---|
| Hodnoty kľúčov možno uložiť mimo tabuľky pomocou samostatného prepojeného zoznamu. | Kľúčové hodnoty by mali byť uložené iba v tabuľke. |
| Počet prvkov v zatrieďovacej tabuľke môže presiahnuť veľkosť zatrieďovacej tabuľky. | Počet prvkov v hašovacej tabuľke nepresiahne počet indexov v hašovacej tabuľke. |
| Vymazanie je efektívne v technike reťazenia. | Vymazanie môže byť ťažkopádne. Ak sa to nevyžaduje, dá sa im vyhnúť. |
| Pretože sa pre každé miesto vedie samostatný prepojený zoznam, je zaberaný priestor veľký. | Pretože všetky záznamy sú umiestnené v tej istej tabuľke, zaberie miesto menej. |
Implementácia tabuľky hash C ++
Hašovanie môžeme implementovať pomocou polí alebo prepojených zoznamov na programovanie hašovacích tabuliek. V C ++ máme aj funkciu nazvanú „hash map“, ktorá je štruktúrou podobná hašovacej tabuľke, ale každý záznam predstavuje pár kľúč - hodnota. V C ++ sa nazýva hash mapa alebo jednoducho mapa. Hašovacia mapa v C ++ je zvyčajne neusporiadaná.
Ako nájsť kľúč zabezpečenia siete v počítači
V štandardnej knižnici šablón (STL) jazyka C ++ je hlavička definovaná, ktorá implementuje funkčnosť máp. Kryli sme Mapy STL podrobne v našom návode na STL.
Nasledujúca implementácia je určená na hašovanie pomocou prepojených zoznamov ako dátovej štruktúry tabuľky hash. Pri tejto implementácii používame aj „reťazenie“ ako techniku riešenia kolízií.
#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:'< Výkon:
Vytvorená hashovacia tabuľka:
0 -> 21 -> 14
1 -> 15
dva
3
4 -> 11
5 -> 12
6
Tabuľka hash po odstránení kľúča 12:
0 -> 21 -> 14
1 -> 15
dva
3
4 -> 11
5
6
Výstup zobrazuje hashovaciu tabuľku, ktorá je vytvorená o veľkosti 7. Na vyriešenie kolízie používame reťazenie. Tabuľku hash zobrazujeme po odstránení jedného z klávesov.
Aplikácie hashovania
# 1) Overenie hesiel: Overovanie hesiel sa zvyčajne vykonáva pomocou kryptografických hashovacích funkcií. Po zadaní hesla systém vypočíta hodnotu hash hesla a potom sa odošle na server na overenie. Na serveri sú uložené hašovacie hodnoty pôvodných hesiel.
# 2) Dátové štruktúry: Rôzne dátové štruktúry ako unordered_set a unordered_map v C ++, slovníky v pythone alebo C #, HashSet a hash mapa v Jave používajú pár kľúč - hodnota, pričom kľúčom sú jedinečné hodnoty. Hodnoty môžu byť rovnaké pre rôzne kľúče. Na implementáciu týchto dátových štruktúr sa používa hašovanie.
# 3) Súhrn správy: Toto je ešte ďalšia aplikácia, ktorá používa kryptografický hash. V prehľadoch správ vypočítame hodnotu hash pre odosielané a prijímané údaje alebo dokonca súbory a porovnávame ich s uloženými hodnotami, aby sme zaistili, že nedôjde k neoprávnenej manipulácii s dátovými súbormi. Najbežnejším algoritmom je tu „SHA 256“.
# 4) Prevádzka kompilátora: Keď kompilátor zostaví program, kľúčové slová pre programovací jazyk sa uložia odlišne od ostatných identifikácií. Kompilátor používa na ukladanie týchto kľúčových slov hashovaciu tabuľku.
# 5) Indexovanie databázy: Hašovacie tabuľky sa používajú na indexovanie databáz a dátové štruktúry na disku.
# 6) Asociatívne polia: Asociatívne polia sú polia, ktorých indexy sú dátového typu iného ako celočíselné reťazce alebo iné typy objektov. Na implementáciu asociatívnych polí je možné použiť hašovacie tabuľky.
Záver
Hašovanie je najbežnejšie používanou dátovou štruktúrou, pretože operácia vkladania, mazania a vyhľadávania trvá konštantne O (1). Hašovanie sa väčšinou implementuje pomocou hashovacej funkcie, ktorá počíta jedinečnú menšiu kľúčovú hodnotu pre veľké údaje. Môžeme implementovať hašovanie pomocou polí a prepojených zoznamov.
Kedykoľvek jeden alebo viac dátových záznamov zodpovedá rovnakým hodnotám kľúčov, vedie to ku kolízii. Videli sme rôzne techniky riešenia kolízií vrátane lineárneho sondovania, reťazenia atď. Tiež sme videli implementáciu hashovania v C ++.
Na záver môžeme povedať, že hašovanie je zďaleka najefektívnejšou dátovou štruktúrou v programovacom svete.
=> Celú sériu školení pre C ++ nájdete tu.
Odporúčané čítanie
- Ako písať zložité testovacie scenáre obchodnej logiky pomocou techniky rozhodovacej tabuľky
- Tabuľka overenia v teréne (FVT): Technika návrhu testu na overenie v teréne
- Výukový program QTP # 15 - Používanie textových oblastí, tabuliek a kontrolných bodov stránok v QTP
- MAPY V STK
- Všetko o smerovačoch: typy smerovačov, smerovacia tabuľka a smerovanie IP
- Top 40 najlepších otázok a odpovedí na rozhovor s MySQL (2021 otázok)
- Najobľúbenejších 90 otázok a odpovedí na pohovory SQL (NAJNOVŠIE)
- Príkazy obslužných programov Unixu: Which, Man, Find Su, Sudo (Part D)