హాష్ ఫంక్షన్
ఈ విభాగంలో, కింది వాటిలో పేర్కొన్న విధంగా డేటా నిర్మాణంలో డేటా అంశం యొక్క సంబంధిత కీ యొక్క హాష్ కోడ్ను అమలు చేయడంలో సహాయపడే హాష్ ఫంక్షన్ గురించి మేము చర్చిస్తాము:
Int hashItem ( int కీ ){
తిరిగి కీ % పట్టిక పరిమాణం ;
}
శ్రేణి యొక్క సూచికను అమలు చేసే ప్రక్రియను హ్యాషింగ్ అంటారు. కొన్నిసార్లు, ఒకే రకమైన కోడ్ని ఒకే రకమైన ఇండెక్స్ని రూపొందించడానికి అమలు చేయబడుతుంది, ఇది ఘర్షణలు అని పిలువబడే ఒకే కీలను ఉపయోగించి వివిధ చైనింగ్ (లింక్డ్ లిస్ట్ క్రియేషన్) మరియు ఓపెన్ అడ్రసింగ్ స్ట్రాటజీస్ ఇంప్లిమెంటేషన్ ద్వారా నిర్వహించబడుతుంది.
C++లో Hash టేబుల్ పని చేస్తోంది
వాస్తవ విలువలకు సంబంధించిన పాయింటర్లు హాష్ పట్టికలో ఉంచబడతాయి. ఇది శ్రేణి యొక్క సూచికను శోధించడానికి కీని ఉపయోగిస్తుంది, దీనిలో కీలకు వ్యతిరేకంగా విలువలు శ్రేణిలో కావలసిన ప్రదేశంలో నిల్వ చేయబడాలి. మేము కింది వాటిలో పేర్కొన్న విధంగా 10 పరిమాణం కలిగి ఉన్న హాష్ పట్టికను తీసుకున్నాము:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
మేము యాదృచ్ఛికంగా వివిధ కీలకు వ్యతిరేకంగా ఏదైనా డేటాను తీసుకుంటాము మరియు సూచికను లెక్కించడం ద్వారా ఈ కీలను హాష్ పట్టికలో నిల్వ చేస్తాము. కాబట్టి, డేటా హ్యాష్ ఫంక్షన్ సహాయంతో లెక్కించిన ఇండెక్స్లోని కీలకు వ్యతిరేకంగా నిల్వ చేయబడుతుంది. మనం డేటా = {14,25,42,55,63,84} మరియు కీలు =[ 15,9,5,25,66,75 ] తీసుకుంటాము.
హాష్ ఫంక్షన్ని ఉపయోగించి ఈ డేటా యొక్క సూచికను లెక్కించండి. సూచిక విలువ క్రింది వాటిలో పేర్కొనబడింది:
కీ | పదిహేను | 9 | 29 | 43 | 66 | 71 |
---|---|---|---|---|---|---|
సూచికను లెక్కించండి | 15% 10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
సమాచారం | 14 | 25 | 42 | 55 | 63 | 84 |
శ్రేణి యొక్క సూచికను సృష్టించిన తర్వాత, గతంలో వివరించిన విధంగా ఇచ్చిన శ్రేణి యొక్క ఖచ్చితమైన సూచికపై కీకి వ్యతిరేకంగా డేటాను ఉంచండి.
25 | 84 | 55 | 14 | 63 | 42 | ||||
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
ఆ తర్వాత, రెండు లేదా అంతకంటే ఎక్కువ కీలు ఒకే హాష్ కోడ్ను కలిగి ఉంటే, శ్రేణిలోని మూలకాల యొక్క అదే సూచికలో ఫలితంగా తాకిడి ఏర్పడుతుందని మనం చూడవచ్చు. ఢీకొనే అవకాశాలను నివారించడానికి మాకు ఒక పరిష్కారం ఉంది: మంచి హాష్ పద్ధతిని ఎంచుకోవడం మరియు ఖచ్చితమైన వ్యూహాలను అమలు చేయడం.
ఇప్పుడు, సరైన ఉదాహరణల సహాయంతో వివిధ అమలు పద్ధతులను చర్చిద్దాం.
ఉదాహరణ: ఓపెన్ హ్యాషింగ్ టెక్నిక్ని ఉపయోగించి హ్యాష్ టేబుల్లో డేటాను జోడించండి
ఈ ఉదాహరణలో, మేము హాష్ పట్టికలో ఘర్షణను నివారించడానికి ఓపెన్ హ్యాషింగ్ వంటి అమలు సాంకేతికతను తీసుకుంటాము. ఓపెన్ హ్యాషింగ్ లేదా చైనింగ్లో, హాష్ టేబుల్ యొక్క విలువలను చైన్ చేయడానికి మేము లింక్ చేసిన జాబితాను సృష్టిస్తాము. ఈ ఉదాహరణ యొక్క కోడ్ స్నిప్పెట్ ఓపెన్ హ్యాషింగ్ టెక్నిక్ను వివరించే కింది వాటిలో జోడించబడింది:
##
- చేర్చండి
తరగతి హ్యాష్ టేబుల్ {
ప్రైవేట్ :
స్థిరమైన స్థిరంగా int పట్టిక పరిమాణం = 10 ;
std :: జాబితా < int > టేబుల్ ఉంది [ పట్టిక పరిమాణం ] ;
int hashFunc ( int కీ ) {
తిరిగి కీ % పట్టిక పరిమాణం ;
}
ప్రజా :
శూన్యం చొప్పించు ( int కీ ) {
int సూచిక = hashFunc ( కీ ) ;
టేబుల్ ఉంది [ సూచిక ] . వెనుకకు నెట్టడం ( కీ ) ;
}
శూన్యం వీక్షణ పట్టిక ( ) {
కోసం ( int i = 0 ; i < పట్టిక పరిమాణం ; ++ i ) {
std :: కోట్ << '[' << i << ']' ;
కోసం ( దానంతట అదే అది = టేబుల్ ఉంది [ i ] . ప్రారంభం ( ) ; అది ! = టేబుల్ ఉంది [ i ] . ముగింపు ( ) ; ++ అది ) {
std :: కోట్ << ' -> ' << * అది ;
}
std :: కోట్ << std :: endl ;
}
}
} ;
int ప్రధాన ( ) {
హ్యాష్ టేబుల్ ఉంది టేబుల్ ;
టేబుల్ ఉంది. చొప్పించు ( పదిహేను ) ;
టేబుల్ ఉంది. చొప్పించు ( 33 ) ;
టేబుల్ ఉంది. చొప్పించు ( 23 ) ;
టేబుల్ ఉంది. చొప్పించు ( 65 ) ;
టేబుల్ ఉంది. చొప్పించు ( 3 ) ;
టేబుల్ ఉంది. వీక్షణ పట్టిక ( ) ;
తిరిగి 0 ;
}
ఇది చాలా ఆసక్తికరమైన ఉదాహరణ: మేము లింక్ చేయబడిన జాబితాను రూపొందించాము మరియు హాష్ పట్టికలో డేటాను ఇన్సర్ట్ చేస్తాము. అన్నింటిలో మొదటిది, మేము ప్రోగ్రామ్ ప్రారంభంలో లైబ్రరీలను నిర్వచించాము. ది < జాబితా > లింక్ చేయబడిన జాబితా అమలు కోసం లైబ్రరీ ఉపయోగించబడుతుంది. ఆ తర్వాత, మేము 'HashTable' పేరుతో ఒక తరగతిని నిర్మిస్తాము మరియు 'ప్రైవేట్:' కీవర్డ్ని ఉపయోగించి టేబుల్ పరిమాణం మరియు పట్టిక శ్రేణి వలె ప్రైవేట్గా ఉండే తరగతి యొక్క లక్షణాలను సృష్టిస్తాము. ప్రైవేట్ అట్రిబ్యూట్లు తరగతి వెలుపల ఉపయోగించబడవని గుర్తుంచుకోండి. ఇక్కడ, మేము పట్టిక పరిమాణాన్ని '10' గా తీసుకుంటాము. మేము దీన్ని ఉపయోగించి హాష్ పద్ధతిని ప్రారంభించాము మరియు హాష్ పట్టిక యొక్క సూచికను గణిస్తాము. హాష్ ఫంక్షన్లో, మేము హాష్ టేబుల్ యొక్క కీ మరియు పరిమాణాన్ని పాస్ చేస్తాము.
మేము అవసరమైన కొన్ని ఫంక్షన్లను రూపొందించాము మరియు ఈ ఫంక్షన్లను తరగతిలో పబ్లిక్గా చేస్తాము. పబ్లిక్ ఫంక్షన్లు తరగతి వెలుపల ఎక్కడైనా ఉపయోగించవచ్చని గుర్తుంచుకోండి. మేము తరగతిలోని పబ్లిక్ భాగాన్ని ప్రారంభించడానికి “పబ్లిక్:” కీవర్డ్ని ఉపయోగిస్తాము . మేము హాష్ పట్టికకు కొత్త మూలకాలను జోడించాలనుకుంటున్నాము కాబట్టి, మేము ఫంక్షన్ యొక్క ఆర్గ్యుమెంట్గా కీతో “InsertHash” పేరుతో ఒక ఫంక్షన్ను సృష్టిస్తాము. 'ఇన్సర్ట్' ఫంక్షన్లో, మేము ఇండెక్స్ వేరియబుల్ని ప్రారంభిస్తాము. మేము హాష్ ఫంక్షన్ను ఇండెక్స్ వేరియబుల్కు పాస్ చేస్తాము. ఆ తర్వాత, పట్టికలో మూలకాన్ని చొప్పించడానికి “పుష్” పద్ధతిని ఉపయోగించి లింక్ చేయబడిన జాబితా పట్టికకు సూచిక వేరియబుల్ను పాస్ చేయండి.
ఆ తర్వాత, మేము కొత్తగా చొప్పించిన డేటాను చూడటానికి హాష్ పట్టికను ప్రదర్శించడానికి “viewHashTab” ఫంక్షన్ని నిర్మిస్తాము. ఈ ఫంక్షన్లో, మేము హాష్ టేబుల్ చివరి వరకు విలువలను శోధించే “ఫర్” లూప్ను తీసుకుంటాము. విలువలు హాష్ ఫంక్షన్ని ఉపయోగించి అభివృద్ధి చేయబడిన అదే సూచికలో నిల్వ చేయబడిందని నిర్ధారించుకోండి. లూప్లో, మేము వాటి సంబంధిత సూచికలో విలువలను పాస్ చేస్తాము మరియు తరగతిని ఇక్కడ ముగించాము. 'ప్రధాన' ఫంక్షన్లో, మేము 'hasTable' అనే తరగతి యొక్క వస్తువును తీసుకుంటాము. ఈ క్లాస్ ఆబ్జెక్ట్ సహాయంతో, మెథడ్లోని కీని పాస్ చేయడం ద్వారా మనం చొప్పించే పద్ధతిని యాక్సెస్ చేయవచ్చు. మేము 'ప్రధాన' ఫంక్షన్లో పాస్ చేసిన కీ, హాష్ పట్టికలో సూచిక స్థానాన్ని అందించే 'ఇన్సర్ట్' ఫంక్షన్లో గణించబడుతుంది. మేము 'క్లాస్' ఆబ్జెక్ట్ సహాయంతో 'వ్యూ' ఫంక్షన్ని కాల్ చేయడం ద్వారా హాష్ టేబుల్ని ప్రదర్శించాము.
ఈ కోడ్ యొక్క అవుట్పుట్ కింది వాటిలో జోడించబడింది:
మనం చూడగలిగినట్లుగా, C++లో లింక్ చేయబడిన జాబితాను ఉపయోగించి హ్యాష్ పట్టిక విజయవంతంగా సృష్టించబడుతుంది. అదే సూచిక యొక్క తాకిడిని నివారించడానికి ఓపెన్ చైనింగ్ ఉపయోగించబడుతుంది.
ముగింపు
అంతిమంగా, భారీ మొత్తంలో డేటాను సమర్ధవంతంగా నిర్వహించడానికి విలువ జతలతో కీలను నిల్వ చేయడానికి మరియు పొందడానికి హాష్ టేబుల్ అత్యంత అభివృద్ధి చెందుతున్న సాంకేతికత అని మేము నిర్ధారించాము. హాష్ పట్టికలో ఢీకొనే అవకాశాలు చాలా ఎక్కువగా ఉంటాయి, డేటా మరియు దాని నిల్వను నాశనం చేస్తాయి. మేము హాష్ టేబుల్ మేనేజ్మెంట్ యొక్క విభిన్న పద్ధతులను ఉపయోగించి ఈ తాకిడిని అధిగమించగలము. C++లో హాష్ టేబుల్ని డెవలప్ చేయడం ద్వారా, డెవలపర్లు హ్యాష్ టేబుల్లో డేటాను స్టోర్ చేయడానికి ఉత్తమమైన టెక్నిక్ని ఉపయోగించి పనితీరును పెంచుకోవచ్చు. హాష్ పట్టిక గురించి మీ అవగాహనకు ఈ కథనం ఉపయోగపడుతుందని మేము ఆశిస్తున్నాము.