Hash-funktion
I det här avsnittet kommer vi att diskutera om hashfunktionen som hjälper till att exekvera hashkoden för den relaterade nyckeln för dataobjektet i datastrukturen som nämns i följande:
Int hashItem ( int nyckel ){
lämna tillbaka nyckel % tabellstorlek ;
}
Processen att exekvera indexet för en array kallas hashing. Ibland exekveras samma typ av kod för att generera samma index med samma nycklar som kallas kollisioner som hanteras genom olika kedja (skapande av länkade listor) och implementering av öppna adresseringsstrategier.
Arbeta med Hash Table i C++
Pekarna till de verkliga värdena hålls i hashtabellen. Den använder en nyckel för att söka upp indexet för en array där värdena mot nycklarna måste lagras på önskad plats i en array. Vi tog hashtabellen med storlek 10 som nämns i följande:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Låt oss slumpmässigt ta all data mot olika nycklar och lagra dessa nycklar i en hashtabell genom att bara beräkna indexet. Så, data lagras mot nycklarna i det beräknade indexet med hjälp av en hash-funktion. Anta att vi tar ett data = {14,25,42,55,63,84} och nycklar =[ 15,9,5,25,66,75 ].
Beräkna indexet för dessa data med hjälp av hash-funktionen. Indexvärdet nämns i följande:
| Nyckel | femton | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Beräkna index | 15 %10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Data | 14 | 25 | 42 | 55 | 63 | 84 |
Efter att ha skapat indexet för en array, placera data mot nyckeln på det exakta indexet för en given array som beskrivits tidigare.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Efter det kan vi se att en kollision uppstår om två eller flera nycklar har samma hash-kod vilket resulterar i samma index av elementen i arrayen. Vi har en lösning för att undvika riskerna för kollision: att välja en bra hashmetod och implementera korrekta strategier.
Låt oss nu diskutera de olika implementeringsteknikerna med hjälp av lämpliga exempel.
Exempel: Lägg till data i en hash-tabell med en öppen hash-teknik
I det här exemplet tar vi en implementeringsteknik som Open Hashing för att undvika kollision i hashtabellen. I öppen hashning eller kedja skapar vi en länkad lista för att kedja hashtabellens värden. Kodavsnittet i detta exempel bifogas i det följande som beskriver den öppna hashtekniken:
#include#inkludera
klass HashTable {
privat :
statisk konst int tabellstorlek = 10 ;
std :: lista < int > bordHar [ tabellstorlek ] ;
int hashFunc ( int nyckel ) {
lämna tillbaka nyckel % tabellstorlek ;
}
offentlig :
tomhet Föra in ( int nyckel ) {
int index = hashFunc ( nyckel ) ;
bordHar [ index ] . trycka tillbaka ( nyckel ) ;
}
tomhet visningstabell ( ) {
för ( int i = 0 ; i < tabellstorlek ; ++ i ) {
std :: cout << '[' << i << ']' ;
för ( bil Det = bordHar [ i ] . Börja ( ) ; Det ! = bordHar [ i ] . slutet ( ) ; ++ Det ) {
std :: cout << ' -> ' << * Det ;
}
std :: cout << std :: endl ;
}
}
} ;
int huvud ( ) {
HashTable hasTable ;
hasTable. Föra in ( femton ) ;
hasTable. Föra in ( 33 ) ;
hasTable. Föra in ( 23 ) ;
hasTable. Föra in ( 65 ) ;
hasTable. Föra in ( 3 ) ;
hasTable. visningstabell ( ) ;
lämna tillbaka 0 ;
}
Detta är ett mycket intressant exempel: vi bygger en länkad lista och infogar data i hashtabellen. Först och främst definierar vi biblioteken i början av programmet. De < lista > biblioteket används för implementeringen av den länkade listan. Efter det bygger vi en klass som heter 'HashTable' och skapar attributen för klassen som är privata som tabellstorlek och tabelluppsättning med nyckelordet 'private:'. Kom ihåg att de privata attributen inte är användbara utanför klassen. Här tar vi storleken på bordet som '10'. Vi initierar hashmetoden med detta och beräknar hashtabellens index. I hashfunktionen skickar vi nyckeln och storleken på hashtabellen.
Vi bygger några obligatoriska funktioner och gör dessa funktioner offentliga i klassen. Kom ihåg att offentliga funktioner är användbara utanför klassen var som helst. Vi använder nyckelordet 'public:' för att starta den offentliga delen av klassen . Eftersom vi vill lägga till nya element i hashtabellen skapar vi en funktion som heter 'InsertHash' med en nyckel som argument för funktionen. I funktionen 'infoga' initierar vi indexvariabeln. Vi skickar hashfunktionen till indexvariabeln. Efter det, skicka indexvariabeln till den länkade listtabellenHar[]med hjälp av 'push'-metoden för att infoga ett element i tabellen.
Efter det bygger vi en 'viewHashTab'-funktion för att visa hashtabellen för att se nyinfogad data. I den här funktionen tar vi en 'för'-loop som söker efter värdena till slutet av hashtabellen. Se till att värdena lagras i samma index som utvecklats med en hashfunktion. I slingan skickar vi värdena vid deras respektive index och avslutar klassen här. I 'main'-funktionen tar vi objektet för en klass som heter 'hasTable'. Med hjälp av detta klassobjekt kan vi komma åt metoden för insättning genom att skicka nyckeln i metoden. Nyckeln som vi skickade i 'main'-funktionen beräknas i 'insert'-funktionen som returnerar indexpositionen i hashtabellen. Vi visade hashtabellen genom att anropa 'view'-funktionen med hjälp av ett 'Class'-objekt.
Utdata från denna kod bifogas i följande:
Som vi kan se skapas hashtabellen framgångsrikt med den länkade listan i C++. Öppen kedja används för att undvika kollision av samma index.
Slutsats
Till slut drog vi slutsatsen att en hashtabell är den mest framväxande tekniken för att lagra och få nycklarna med värdepar för att hantera enorma mängder data effektivt. Risken för kollision är mycket stor i hashtabellen, vilket förstör data och dess lagring. Vi kan övervinna denna kollision med hjälp av olika tekniker för hashtabellhantering. Genom att utveckla hashtabellen i C++ kan utvecklarna öka prestandan med den bästa lämpliga tekniken för att lagra data i hashtabellen. Vi hoppas att den här artikeln är till hjälp för din förståelse av hashtabellen.