Hash függvény
Ebben a részben a hash függvényről fogunk beszélni, amely segít az adatszerkezetben lévő adatelem kapcsolódó kulcsának hash kódjának végrehajtásában, ahogyan az alábbiakban szerepel:
Int hashItem ( int kulcs ){
Visszatérés kulcs % asztalméret ;
}
A tömb indexének végrehajtási folyamatát kivonatolásnak nevezzük. Néha ugyanazt a kódot hajtják végre, hogy ugyanazt az indexet generálják ugyanazon kulcsok használatával, amelyeket ütközésnek neveznek, és amelyet különböző láncoláson (kapcsolt lista létrehozása) és nyílt címzési stratégiák megvalósításán keresztül kezelnek.
Hash tábla működése C++ nyelven
A valós értékekre mutató mutatókat a hash táblában tároljuk. Egy kulcs segítségével megkeresi egy tömb indexét, amelynél a kulcsokhoz viszonyított értékeket a kívánt helyen kell tárolni egy tömbben. A 10-es méretű hash-táblázatot az alábbiak szerint vettük:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Vegyünk véletlenszerűen bármilyen adatot a különböző kulcsokhoz, és tároljuk ezeket a kulcsokat egy hash táblában az index kiszámításával. Tehát az adatok a számított index kulcsaihoz képest egy hash függvény segítségével tárolódnak. Tegyük fel, hogy veszünk egy adatot = {14,25,42,55,63,84} és a kulcsokat =[ 15,9,5,25,66,75 ].
Számítsa ki ezen adatok indexét a hash függvény segítségével. Az index értéke a következőkben szerepel:
| Kulcs | tizenöt | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Számítsa ki az indexet | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Adat | 14 | 25 | 42 | 55 | 63 | 84 |
Egy tömb indexének létrehozása után helyezze el az adatokat a kulcshoz képest egy adott tömb pontos indexében, a korábban leírtak szerint.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Ezek után láthatjuk, hogy ütközés következik be, ha két vagy több kulcsnak ugyanaz a hash kódja, ami a tömb elemeinek azonos indexét eredményezi. Egyetlen megoldásunk van az ütközések elkerülésére: egy jó hash módszer kiválasztása és a pontos stratégiák megvalósítása.
Most beszéljük meg a különböző megvalósítási technikákat megfelelő példák segítségével.
Példa: Adatok hozzáadása egy hash-táblázathoz nyílt kivonatolási technikával
Ebben a példában egy olyan megvalósítási technikát veszünk, mint az Open Hashing, hogy elkerüljük az ütközést a hash táblában. Nyílt kivonatolásnál vagy láncolásnál létrehozunk egy linkelt listát a hash tábla értékeinek láncolásához. Ennek a példának a kódrészletét az alábbiakban csatoljuk, amely leírja a nyílt kivonatolási technikát:
#include#include
osztály HashTable {
magán :
statikus const int asztalméret = 10 ;
std :: lista < int > táblázatHas [ asztalméret ] ;
int hashFunc ( int kulcs ) {
Visszatérés kulcs % asztalméret ;
}
nyilvános :
üres betét ( int kulcs ) {
int index = hashFunc ( kulcs ) ;
táblázatHas [ index ] . visszavet ( kulcs ) ;
}
üres viewTable ( ) {
számára ( int én = 0 ; én < asztalméret ; ++ én ) {
std :: cout << '[' << én << ']' ;
számára ( auto azt = táblázatHas [ én ] . kezdődik ( ) ; azt ! = táblázatHas [ én ] . vége ( ) ; ++ azt ) {
std :: cout << ' -> ' << * azt ;
}
std :: cout << std :: endl ;
}
}
} ;
int fő- ( ) {
HashTable hasTable ;
hasTable. betét ( tizenöt ) ;
hasTable. betét ( 33 ) ;
hasTable. betét ( 23 ) ;
hasTable. betét ( 65 ) ;
hasTable. betét ( 3 ) ;
hasTable. viewTable ( ) ;
Visszatérés 0 ;
}
Ez egy nagyon érdekes példa: összeállítunk egy linkelt listát, és beillesztjük az adatokat a hash táblába. Mindenekelőtt a program elején definiáljuk a könyvtárakat. A < lista > könyvtárat használják a linkelt lista megvalósításához. Ezután felépítünk egy „HashTable” nevű osztályt, és létrehozzuk az osztály privát attribútumait, mint táblaméret és táblatömb a „private:” kulcsszó használatával. Ne feledje, hogy a privát attribútumok nem használhatók az osztályon kívül. Itt a táblázat méretét 10-nek vesszük. Ezzel inicializáljuk a hash módszert, és kiszámítjuk a hash tábla indexét. A hash függvényben átadjuk a hash tábla kulcsát és méretét.
Felépítünk néhány szükséges függvényt, és ezeket a függvényeket nyilvánossá tesszük az osztályban. Ne feledje, hogy a nyilvános funkciók az osztályon kívül bárhol használhatók. A „public:” kulcsszót használjuk az osztály nyilvános részének elindításához . Mivel új elemeket szeretnénk hozzáadni a hash táblához, létrehozunk egy „InsertHash” nevű függvényt a függvény argumentumaként egy kulccsal. Az „insert” függvényben inicializáljuk az indexváltozót. A hash függvényt átadjuk az indexváltozónak. Ezt követően adja át az indexváltozót a linkelt listának a tableHas[]a „push” metódussal egy elem beszúrásához a táblázatba.
Ezt követően felépítünk egy „viewHashTab” függvényt, amely megjeleníti a hash táblát az újonnan beillesztett adatok megtekintéséhez. Ebben a függvényben veszünk egy „for” ciklust, amely a hash tábla végéig keresi az értékeket. Győződjön meg arról, hogy az értékek ugyanazon az indexen vannak tárolva, mint a hash függvény segítségével. A ciklusban átadjuk az értékeket a megfelelő indexükön, és itt fejezzük be az osztályt. A „main” függvényben egy „hasTable” nevű osztály objektumát vesszük. Ennek az osztályobjektumnak a segítségével a metódusban lévő kulcs átadásával érhetjük el a beillesztés metódusát. A „fő” függvényben átadott kulcsot az „insert” függvény számítja ki, amely visszaadja az indexpozíciót a hash-táblázatban. A hash táblát a „view” függvény meghívásával jelenítettük meg egy „Class” objektum segítségével.
Ennek a kódnak a kimenete az alábbiakban található:
Amint látjuk, a hash tábla sikeresen létrejött a C++ linkelt listájával. A nyílt láncolást ugyanazon index ütközésének elkerülésére használják.
Következtetés
Végül arra a következtetésre jutottunk, hogy a hash-tábla a leginkább feltörekvő technika az értékpárokkal rendelkező kulcsok tárolására és lekérésére hatalmas mennyiségű adat hatékony kezeléséhez. A hash táblában nagyon nagy az ütközés esélye, ami tönkreteszi az adatokat és azok tárolását. Ezt az ütközést a hash tábla kezelésének különböző technikáival tudjuk legyőzni. A hash tábla C++ nyelven történő fejlesztésével a fejlesztők növelhetik a teljesítményt a legmegfelelőbb technikával az adatok tárolására a hash táblában. Reméljük, hogy ez a cikk segít a hash-táblázat megértésében.