Hash funkcia
V tejto časti budeme diskutovať o hašovacej funkcii, ktorá pomáha spustiť hašovací kód súvisiaceho kľúča dátovej položky v dátovej štruktúre, ako je uvedené nižšie:
Int hashItem ( int kľúč ){
vrátiť kľúč % tabuľková veľkosť ;
}
Proces vykonávania indexu poľa sa nazýva hashovanie. Niekedy sa vykoná rovnaký typ kódu na vygenerovanie rovnakého indexu pomocou rovnakých kľúčov nazývaných kolízie, ktoré sa riešia prostredníctvom rôznych reťazení (tvorba prepojeného zoznamu) a implementácie stratégií otvoreného adresovania.
Práca s tabuľkou hash v C++
Ukazovatele na skutočné hodnoty sú uložené v hašovacej tabuľke. Používa kľúč na vyhľadanie indexu poľa, v ktorom je potrebné uložiť hodnoty oproti kľúčom na požadované miesto v poli. Zobrali sme hašovaciu tabuľku veľkosti 10, ako je uvedené nižšie:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Zoberme si náhodne akékoľvek údaje proti rôznym kľúčom a uložme tieto kľúče do hašovacej tabuľky jednoduchým výpočtom indexu. Dáta sú teda uložené oproti kľúčom vo vypočítanom indexe pomocou hašovacej funkcie. Predpokladajme, že vezmeme dáta = {14,25,42,55,63,84} a kľúče =[ 15,9,5,25,66,75 ].
Vypočítajte index týchto údajov pomocou hašovacej funkcie. Hodnota indexu je uvedená nasledovne:
| kľúč | pätnásť | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Vypočítajte index | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Údaje | 14 | 25 | 42 | 55 | 63 | 84 |
Po vytvorení indexu poľa umiestnite údaje oproti kľúču na presný index daného poľa, ako je opísané vyššie.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Potom môžeme vidieť, že kolízia nastane, ak dva alebo viac kľúčov má rovnaký hash kód, čo vedie k rovnakému indexu prvkov v poli. Máme jedno riešenie, ako sa vyhnúť kolíziám: výber dobrej hašovacej metódy a implementácia presných stratégií.
Teraz poďme diskutovať o rôznych technikách implementácie pomocou správnych príkladov.
Príklad: Pridajte údaje do hašovacej tabuľky pomocou otvorenej hašovacej techniky
V tomto príklade používame implementačnú techniku, ako je Open Hashing, aby sme predišli kolízii v hašovacej tabuľke. Pri otvorenom hašovaní alebo reťazení vytvárame prepojený zoznam na reťazenie hodnôt hašovacej tabuľky. Útržok kódu z tohto príkladu je priložený v nasledujúcom texte, ktorý popisuje techniku otvoreného hašovania:
#include#include
trieda HashTable {
súkromné :
statické konšt int tableSize = 10 ;
std :: zoznam < int > tableHas [ tableSize ] ;
int hashFunc ( int kľúč ) {
vrátiť kľúč % tableSize ;
}
verejnosti :
neplatné vložiť ( int kľúč ) {
int index = hashFunc ( kľúč ) ;
tableHas [ index ] . push_back ( kľúč ) ;
}
neplatné viewTable ( ) {
pre ( int i = 0 ; i < tableSize ; ++ i ) {
std :: cout << '[' << i << ']' ;
pre ( auto to = tableHas [ i ] . začať ( ) ; to ! = tableHas [ i ] . koniec ( ) ; ++ to ) {
std :: cout << ' ->' << * to ;
}
std :: cout << std :: endl ;
}
}
} ;
int Hlavná ( ) {
HashTable hasTable ;
hasTable. vložiť ( pätnásť ) ;
hasTable. vložiť ( 33 ) ;
hasTable. vložiť ( 23 ) ;
hasTable. vložiť ( 65 ) ;
hasTable. vložiť ( 3 ) ;
hasTable. viewTable ( ) ;
vrátiť 0 ;
}
Toto je veľmi zaujímavý príklad: vytvoríme prepojený zoznam a vložíme údaje do hašovacej tabuľky. V prvom rade definujeme knižnice pri štarte programu. The < zoznam > knižnica sa používa na implementáciu prepojeného zoznamu. Potom vytvoríme triedu s názvom „HashTable“ a vytvoríme atribúty triedy, ktoré sú súkromné, ako veľkosť tabuľky a pole tabuľky pomocou kľúčového slova „private:“. Pamätajte, že súkromné atribúty nie sú použiteľné mimo triedy. Tu berieme veľkosť tabuľky ako „10“. Pomocou toho inicializujeme hašovaciu metódu a vypočítame index hašovacej tabuľky. V hašovacej funkcii odovzdávame kľúč a veľkosť hašovacej tabuľky.
Vytvoríme niekoľko požadovaných funkcií a tieto funkcie zverejníme v triede. Pamätajte, že verejné funkcie sú použiteľné kdekoľvek mimo triedy. Na spustenie verejnej časti triedy používame kľúčové slovo „public:“. . Keďže chceme do hašovacej tabuľky pridať nové prvky, vytvoríme funkciu s názvom „InsertHash“ s kľúčom ako argumentom funkcie. Vo funkcii „insert“ inicializujeme premennú index. Hašovaciu funkciu odovzdáme do premennej index. Potom odovzdajte premennú indexu do tabuľky prepojeného zoznamu[]pomocou metódy „push“ na vloženie prvku do tabuľky.
Potom vytvoríme funkciu „viewHashTab“ na zobrazenie hašovacej tabuľky, aby sme videli novo vložené údaje. V tejto funkcii používame cyklus „for“, ktorý prehľadáva hodnoty až do konca hašovacej tabuľky. Uistite sa, že hodnoty sú uložené v rovnakom indexe, aký je vytvorený pomocou hašovacej funkcie. V slučke odovzdávame hodnoty pri ich príslušnom indexe a tu triedu ukončíme. Vo funkcii „main“ berieme objekt triedy s názvom „hasTable“. Pomocou tohto objektu triedy môžeme pristupovať k metóde vkladania odovzdaním kľúča v metóde. Kľúč, ktorý sme odovzdali vo funkcii „main“, sa vypočíta vo funkcii „insert“, ktorá vráti pozíciu indexu v tabuľke hash. Hašovaciu tabuľku sme zobrazili zavolaním funkcie „view“ pomocou objektu „Class“.
Výstup tohto kódu je pripojený v nasledujúcom texte:
Ako vidíme, hašovacia tabuľka je úspešne vytvorená pomocou prepojeného zoznamu v C++. Otvorené reťazenie sa používa na zamedzenie kolízie rovnakého indexu.
Záver
Nakoniec sme dospeli k záveru, že hašovacia tabuľka je najnovšia technika na ukladanie a získavanie kľúčov s pármi hodnôt na efektívne spracovanie obrovského množstva údajov. Pravdepodobnosť kolízie je v hašovacej tabuľke veľmi vysoká, čo zničí údaje a ich uloženie. Túto kolíziu môžeme prekonať pomocou rôznych techník riadenia hashovacích tabuliek. Vývojom hašovacej tabuľky v C++ môžu vývojári zvýšiť výkon pomocou najlepšej vhodnej techniky na ukladanie údajov do hašovacej tabuľky. Dúfame, že tento článok vám pomôže pochopiť hašovaciu tabuľku.