హాషింగ్ కాన్సెప్ట్స్  


పరిచయం  

హాష్ ఫైల్ ఆర్గనైజేషన్ పద్ధతి హాష్ ఫంక్షన్‌ను ఉపయోగించి డేటా అడ్రస్‌ని డేటా బ్లాక్‌ల వద్ద నిల్వ చేస్తుంది. ఈ రికార్డులు నిల్వ చేయబడిన మెమరీ స్థానాన్ని డేటా బ్లాక్ లేదా డేటా బకెట్ అంటారు. ఈ డేటా బకెట్ ఒకటి లేదా అంతకంటే ఎక్కువ రికార్డులను నిల్వ చేయగలదు.

హాష్ ఫంక్షన్ చిరునామాను రూపొందించడానికి ఏదైనా కాలమ్ విలువను ఉపయోగించవచ్చు. ఎక్కువ సమయం, హాష్ ఫంక్షన్ డేటా బ్లాక్ యొక్క హాష్ ఇండెక్స్ - చిరునామాను రూపొందించడానికి ప్రాథమిక కీని ఉపయోగిస్తుంది. హాష్ ఫంక్షన్ ఏదైనా సంక్లిష్ట గణిత ఫంక్షన్కు సాధారణ గణిత ఫంక్షన్. మేము ప్రాధమిక కీని డేటా బ్లాక్ యొక్క చిరునామాగా కూడా పరిగణించవచ్చు. అంటే ప్రతి అడ్డు వరుస డేటా బ్లాక్ వద్ద నిల్వ చేయబడుతుంది, దీని చిరునామా ప్రాథమిక కీ వలె ఉంటుంది. డేటాబేస్లో హాష్ ఫంక్షన్ ఎంత సరళంగా ఉంటుందో ఇది సూచిస్తుంది.

పైన ఉన్న రేఖాచిత్రం డేటా బ్లాక్ చిరునామాను ప్రాధమిక కీ విలువ వలె వర్ణిస్తుంది. ఈ హాష్ ఫంక్షన్ మోడ్, సిన్, కాస్, ఎక్స్‌పోనెన్షియల్ వంటి సాధారణ గణిత ఫంక్షన్ కూడా కావచ్చు. డేటా బ్లాక్ యొక్క చిరునామాను నిర్ణయించడానికి మనకు హాష్ ఫంక్షన్ మోడ్ (5) గా ఉందని g హించుకోండి. కాబట్టి పై కేసుకు ఏమి జరుగుతుంది? ఇది ప్రాధమిక కీలపై మోడ్ (5) ను వర్తింపజేస్తుంది మరియు వరుసగా 3,3,1,4 మరియు 2 లను ఉత్పత్తి చేస్తుంది మరియు రికార్డులు ఆ డేటా బ్లాక్ చిరునామాలలో నిల్వ చేయబడతాయి.

పై రెండు రేఖాచిత్రాల నుండి హాష్ ఫంక్షన్ ఎలా పనిచేస్తుందో ఇప్పుడు స్పష్టమవుతుంది.

ఇది కూడ చూడు
DBMS యొక్క నిర్మాణం మరియు డేటాబేస్ నిర్వహణ వ్యవస్థ యొక్క డేటాబేస్ నిర్మాణం

హాష్ ఫైల్ సంస్థలలో రెండు రకాలు ఉన్నాయి - స్టాటిక్ మరియు డైనమిక్ హాషింగ్.

స్టాటిక్ హాషింగ్  

హాషింగ్ యొక్క ఈ పద్ధతిలో, ఫలిత డేటా బకెట్ చిరునామా ఎల్లప్పుడూ ఒకే విధంగా ఉంటుంది. అంటే, మేము మోడ్ (103) హాష్ ఫంక్షన్‌ను ఉపయోగించి EMP_ID = 5 కోసం చిరునామాను ఉత్పత్తి చేయాలనుకుంటే, ఇది ఎల్లప్పుడూ ఒకే బకెట్ చిరునామాకు దారి తీస్తుంది. ఇక్కడ బకెట్ చిరునామాలో ఎటువంటి మార్పులు ఉండవు. అందువల్ల ఈ స్టాటిక్ హాషింగ్ కోసం మెమరీలో డేటా బకెట్ల సంఖ్య అంతటా స్థిరంగా ఉంటుంది. మా ఉదాహరణలో, డేటాను నిల్వ చేయడానికి ఉపయోగించే మెమరీలో ఐదు డేటా బకెట్లు ఉంటాయి.

రికార్డును శోధిస్తోంది

హాష్ ఫంక్షన్ ఉపయోగించి, హాష్ కీ కోసం డేటా బకెట్ చిరునామా ఉత్పత్తి అవుతుంది. రికార్డ్ ఆ స్థానం నుండి తిరిగి పొందబడుతుంది. అంటే; మేము ID 104 కోసం మొత్తం రికార్డును తిరిగి పొందాలనుకుంటే, మరియు ID లో హాష్ ఫంక్షన్ మోడ్ (5) అయితే, ఉత్పత్తి చేయబడిన చిరునామా 4 అవుతుంది. అప్పుడు మనం నేరుగా 4 చిరునామా చేసి, ID 104 కోసం మొత్తం రికార్డును తిరిగి పొందుతాము. ఇక్కడ ID హాష్ కీగా పనిచేస్తుంది.

రికార్డును చొప్పించడం

క్రొత్త రికార్డ్‌ను పట్టికలో చేర్చాల్సిన అవసరం వచ్చినప్పుడు, మేము దాని హాష్ కీ ఆధారంగా క్రొత్త రికార్డ్ కోసం చిరునామాను రూపొందిస్తాము. చిరునామా ఉత్పత్తి అయిన తర్వాత, రికార్డ్ ఆ ప్రదేశంలో నిల్వ చేయబడుతుంది.

రికార్డును తొలగించండి

హాష్ ఫంక్షన్‌ను ఉపయోగించి మేము మొదట తొలగించాల్సిన రికార్డును పొందుతాము. అప్పుడు మేము ఆ చిరునామా కోసం రికార్డులను మెమరీలో తొలగిస్తాము.

రికార్డును నవీకరించండి

నవీకరణ కోసం గుర్తించబడిన డేటా రికార్డ్ స్టాటిక్ హాష్ ఫంక్షన్ ఉపయోగించి శోధించబడుతుంది మరియు ఆ చిరునామాలో రికార్డ్ నవీకరించబడుతుంది.

ఇది కూడ చూడు
డేటాబేస్ యొక్క లక్షణాలు

 

మేము ఫైల్‌లో కొన్ని రికార్డులను చొప్పించాలని అనుకుందాం. కానీ హాష్ ఫంక్షన్ ద్వారా ఉత్పత్తి చేయబడిన డేటా బకెట్ చిరునామా నిండి ఉంది లేదా డేటా ఇప్పటికే ఆ చిరునామాలో ఉంది. మేము డేటాను ఎలా చొప్పించాలి? స్టాటిక్ హాషింగ్‌లోని ఈ పరిస్థితిని అంటారు బకెట్ ఓవర్ఫ్లో. ఈ పద్ధతిలో క్లిష్టమైన పరిస్థితులలో / లోపాలలో ఇది ఒకటి. ఈ సందర్భంలో మేము డేటాను ఎక్కడ సేవ్ చేస్తాము? మేము డేటాను కోల్పోలేము. ఈ పరిస్థితిని అధిగమించడానికి వివిధ పద్ధతులు ఉన్నాయి. సాధారణంగా ఉపయోగించే పద్ధతులు క్రింద ఇవ్వబడ్డాయి:

మూసివేసిన హాషింగ్

ఈ పద్ధతిలో మేము అదే చిరునామాతో క్రొత్త డేటా బకెట్‌ను పరిచయం చేస్తాము మరియు పూర్తి డేటా బకెట్ తర్వాత దాన్ని లింక్ చేస్తాము. బకెట్ ఓవర్ఫ్లోను అధిగమించే ఈ పద్ధతులను క్లోజ్డ్ హాషింగ్ లేదా అంటారు ఓవర్ఫ్లో చైనింగ్.

మేము ఒక కొత్త రికార్డ్ R2 ని ఇన్సర్ట్ చేయాలని పరిగణించండి పట్టికలు. స్టాటిక్ హాష్ ఫంక్షన్ డేటా బకెట్ చిరునామాను 'AACDBF' గా రూపొందిస్తుంది. కానీ కొత్త డేటాను నిల్వ చేయడానికి ఈ బకెట్ నిండిపోయింది. ఈ సందర్భంలో చేసినది 'AACDBF' డేటా బకెట్ చివరలో కొత్త డేటా బకెట్ జోడించబడింది మరియు దానికి లింక్ చేయబడింది. అప్పుడు కొత్త రికార్డ్ R2 కొత్త బకెట్‌లోకి చేర్చబడుతుంది. అందువలన ఇది స్టాటిక్ హ్యాషింగ్ చిరునామాను నిర్వహిస్తుంది. ఇది నిండినప్పుడు, ఎన్ని కొత్త డేటా బకెట్లు అయినా జోడించవచ్చు.

ఓపెన్ హాషింగ్

ఈ పద్ధతిలో, క్రొత్తదాన్ని నమోదు చేయడానికి తదుపరి అందుబాటులో ఉన్న డేటా బ్లాక్ ఉపయోగించబడుతుంది, పాతదాన్ని ఓవర్రైట్ చేయడానికి బదులుగా. ఈ పద్ధతిని ఓపెన్ హాషింగ్ లేదా లీనియర్ ప్రోబింగ్.

దిగువ ఉదాహరణలో, R2 క్రొత్త రికార్డ్, ఇది చొప్పించాల్సిన అవసరం ఉంది. కానీ హాష్ ఫంక్షన్ చిరునామాను 237 గా ఉత్పత్తి చేస్తుంది. కానీ ఇది ఇప్పటికే నిండి ఉంది. కాబట్టి సిస్టమ్ తదుపరి అందుబాటులో ఉన్న డేటా బకెట్, 238 ను శోధిస్తుంది మరియు దానికి R2 ను కేటాయిస్తుంది.

ఇది కూడ చూడు
డేటాబేస్ యొక్క భాగాలు

లీనియర్ ప్రోబింగ్‌లో, పాత బకెట్ మరియు కొత్త బకెట్ మధ్య వ్యత్యాసం సాధారణంగా పరిష్కరించబడుతుంది మరియు ఇది చాలా సందర్భాలలో 1 అవుతుంది.

క్వాడ్రాటిక్ ప్రోబింగ్

ఇది లీనియర్ ప్రోబింగ్ మాదిరిగానే ఉంటుంది. కానీ ఇక్కడ, పాత మరియు క్రొత్త బకెట్ మధ్య వ్యత్యాసం సరళంగా ఉంటుంది. క్రొత్త బకెట్ చిరునామాను నిర్ణయించడానికి మేము క్వాడ్రాటిక్ ఫంక్షన్‌ను ఉపయోగిస్తాము.

డబుల్ హాషింగ్

ఇది లీనియర్ ప్రోబింగ్ యొక్క మరొక పద్ధతి. ఇక్కడ వ్యత్యాసం సరళ ప్రోబింగ్‌లో వలె పరిష్కరించబడింది, అయితే ఈ స్థిర వ్యత్యాసం మరొక హాష్ ఫంక్షన్‌ను ఉపయోగించి లెక్కించబడుతుంది. అందువల్ల పేరు డబుల్ హాషింగ్.

డైనమిక్ హాషింగ్  

స్టాటిక్ హాషింగ్ - బకెట్ ఓవర్ఫ్లో సమస్యలను అధిగమించడానికి ఈ హాషింగ్ పద్ధతి ఉపయోగించబడుతుంది. హాషింగ్ యొక్క ఈ పద్ధతిలో, రికార్డులు పెరుగుతున్నప్పుడు లేదా తగ్గినప్పుడు డేటా బకెట్లు పెరుగుతాయి లేదా తగ్గిపోతాయి. ఈ హాషింగ్ పద్ధతిని ఎక్స్‌టెన్డబుల్ హాషింగ్ పద్ధతి అని కూడా అంటారు. ఈ పద్ధతిని అర్థం చేసుకోవడానికి ఒక ఉదాహరణ చూద్దాం.

R1, R2 మరియు R4 మూడు రికార్డులు పట్టికలో ఉన్నాయని పరిగణించండి. ఈ రికార్డులు వరుసగా 100100, 010110 మరియు 110110 చిరునామాలను ఉత్పత్తి చేస్తాయి. నిల్వ చేసే ఈ పద్ధతి ఈ చిరునామాలో కొంత భాగాన్ని మాత్రమే పరిగణిస్తుంది - ముఖ్యంగా డేటాను నిల్వ చేయడానికి మొదటి ఒక బిట్ మాత్రమే. కనుక ఇది వాటిలో మూడు చిరునామా 0 మరియు 1 వద్ద లోడ్ చేయడానికి ప్రయత్నిస్తుంది.

ఇక్కడ R3 కి ఏమి జరుగుతుంది? R3 కోసం బకెట్ స్థలం లేదు. R3 కు అనుగుణంగా బకెట్ డైనమిక్‌గా పెరగాలి. కనుక ఇది చిరునామాను 2 బిట్ కంటే 1 బిట్స్ కలిగి మారుస్తుంది, ఆపై ఇది 2 బిట్ అడ్రస్ కలిగి ఉన్న డేటాను అప్‌డేట్ చేస్తుంది. అప్పుడు అది R3 కు అనుగుణంగా ప్రయత్నిస్తుంది.

క్రొత్త చిరునామాను ప్రతిబింబించేలా R1 మరియు R2 యొక్క చిరునామా మార్చబడిందని మరియు R3 కూడా చేర్చబడిందని ఇప్పుడు మనం చూడవచ్చు. డేటా పరిమాణం పెరిగేకొద్దీ, ఇది ఇప్పటికే ఉన్న బకెట్లలో చొప్పించడానికి ప్రయత్నిస్తుంది. బకెట్లు ఏవీ అందుబాటులో లేకపోతే, పెద్ద చిరునామాను పరిగణనలోకి తీసుకోవడానికి బిట్ల సంఖ్య పెరుగుతుంది మరియు అందువల్ల బకెట్లను పెంచుతుంది. మేము ఏదైనా రికార్డ్‌ను తొలగిస్తే మరియు డేటాలను తక్కువ బకెట్లతో నిల్వ చేయగలిగితే, అది బకెట్ పరిమాణాన్ని తగ్గిస్తుంది. ఇది మనం పైన చూసిన దానికి విరుద్ధంగా చేస్తుంది. డైనమిక్ హాషింగ్ ఈ విధంగా పనిచేస్తుంది. ప్రారంభంలో హాష్ ఫంక్షన్ ద్వారా ఉత్పత్తి చేయబడిన పాక్షిక సూచిక / చిరునామా మాత్రమే డేటాను నిల్వ చేయడానికి పరిగణించబడుతుంది. డేటా సంఖ్య పెరిగేకొద్దీ మరియు ఎక్కువ బకెట్ అవసరం ఉన్నందున, ఇండెక్స్‌లో ఎక్కువ భాగం డేటాను నిల్వ చేయడానికి పరిగణించబడుతుంది.

ఇది కూడ చూడు
డేటా స్వాతంత్ర్యం

డైనమిక్ హాషింగ్ యొక్క ప్రయోజనాలు  

  • సిస్టమ్‌లో డేటా పెరుగుతున్న కొద్దీ పనితీరు తగ్గదు. ఇది డేటాకు అనుగుణంగా మెమరీ పరిమాణాన్ని పెంచుతుంది.
  • ఇది పెరుగుతుంది మరియు డేటాతో తగ్గిపోతుంది కాబట్టి, మెమరీ బాగా ఉపయోగించబడుతుంది. ఉపయోగించని జ్ఞాపకశక్తి అబద్ధం ఉండదు.
  • డేటా పెరుగుతుంది మరియు తరచుగా తగ్గిపోయే డైనమిక్ డేటాబేస్‌లకు మంచిది.

 

డైనమిక్ హాషింగ్ యొక్క ప్రతికూలతలు  

  • డేటా పరిమాణం పెరిగేకొద్దీ బకెట్ పరిమాణం కూడా పెరుగుతుంది. ఈ చిరునామాలు బకెట్ చిరునామా పట్టికలలో నిర్వహించబడతాయి. ఎందుకంటే, బకెట్లు పెరుగుతున్నప్పుడు మరియు కుంచించుకుపోతున్నప్పుడు డేటా యొక్క చిరునామా మారుతూ ఉంటుంది. డేటాలో భారీ పెరుగుదల ఉన్నప్పుడు, ఈ బకెట్ చిరునామా పట్టికను నిర్వహించడం శ్రమతో కూడుకున్నది.
  • ఈ సందర్భంలో కూడా బకెట్ ఓవర్ఫ్లో పరిస్థితి ఏర్పడుతుంది. స్టాటిక్ హాషింగ్ కంటే ఈ పరిస్థితిని చేరుకోవడానికి తక్కువ సమయం పడుతుంది.

ఆర్డర్డ్ ఇండెక్సింగ్ మరియు హాషింగ్ యొక్క పోలిక  

ఇండెక్సింగ్ చేయమని ఆదేశించారు

హ్యాషింగ్

కీ విలువ కోసం మెమరీలోని చిరునామాలు క్రమబద్ధీకరించబడతాయి. ఈ కీ విలువ ప్రాధమిక కీ లేదా పట్టికలోని ఏదైనా ఇతర కాలమ్ కావచ్చు. కీ విలువపై హాష్ ఫంక్షన్‌ను ఉపయోగించి చిరునామాలు ఉత్పత్తి చేయబడతాయి. ఈ కీ విలువ ప్రాధమిక కీ లేదా పట్టికలోని ఏదైనా ఇతర కాలమ్ కావచ్చు.
ఫైల్‌లో డేటా పెరిగేకొద్దీ ఈ పద్ధతి యొక్క పనితీరు తగ్గుతుంది. ఇది డేటాను క్రమబద్ధీకరించిన రూపంలో నిల్వ చేస్తుంది కాబట్టి, చొప్పించు / తొలగించు / నవీకరణ ఆపరేషన్ ఉన్నప్పుడు, రికార్డును క్రమబద్ధీకరించడానికి అదనపు ప్రయత్నం అవసరం. ఇది దాని పనితీరును తగ్గిస్తుంది. డేటాను తరచుగా చేర్చుకోవడం మరియు తొలగించడం ఉన్నప్పుడు డైనమిక్ హాషింగ్ యొక్క పనితీరు మంచిది. డేటాబేస్ చాలా పెద్దది అయితే, నిర్వహణ ఖరీదైనది.

రికార్డ్ సైజు ఐడి ఇంతకు ముందు తెలిసిన చిన్న డేటాబేస్‌లకు స్టాటిక్ హాషింగ్ మంచిది. డేటాలో పెరుగుదల ఉంటే, అది బకెట్ ఓవర్ఫ్లో వంటి తీవ్రమైన సమస్యలకు దారితీస్తుంది.

తొలగింపు / నవీకరణ ఆపరేషన్ కారణంగా ఉపయోగించని డేటా బ్లాక్‌లు ఉంటాయి. తిరిగి ఉపయోగించడానికి ఈ డేటా బ్లాక్స్ విడుదల చేయబడవు. అందువల్ల మెమరీ యొక్క ఆవర్తన నిర్వహణ అవసరం. లేకపోతే, జ్ఞాపకశక్తి వృధా అవుతుంది మరియు పనితీరు కూడా క్షీణిస్తుంది. జ్ఞాపకశక్తిని నిర్వహించడానికి ఇది ఓవర్ హెడ్ ఖర్చు అవుతుంది. స్టాటిక్ మరియు డైనమిక్ హాషింగ్ రెండింటిలోనూ, మెమరీ బాగా నిర్వహించబడుతుంది. స్టాటిక్ హాషింగ్‌లో బకెట్ ఓవర్‌ఫ్లో కూడా బాగా నిర్వహించబడుతుంది. డేటా బ్లాక్స్ డైనమిక్ హాషింగ్లో కుదించడానికి మరియు పెరగడానికి రూపొందించబడ్డాయి.

భారీ డేటాబేస్ పెరుగుదల ఉన్నప్పుడు డైనమిక్ హాషింగ్లో బకెట్ చిరునామా పట్టికను నిర్వహించడానికి ఓవర్ హెడ్ ఉంటుంది.

డేటా యొక్క పరిధిని తిరిగి పొందటానికి ఇష్టపడతారు- అంటే నిర్దిష్ట పరిధికి తిరిగి పొందే డేటా ఉన్నప్పుడు, ఈ పద్ధతి ఉత్తమంగా సరిపోతుంది. శోధన కీ ఆధారంగా ఒక నిర్దిష్ట రికార్డును తిరిగి పొందడానికి ఈ పద్ధతి అనుకూలంగా ఉంటుంది. శోధన కీలో హాష్ ఫంక్షన్ లేకపోతే అది మెరుగ్గా పనిచేయదు.
ఇది కూడ చూడు
OSI మోడల్