Hashed array tree
કોમ્પ્યુટર વિજ્ઞાનમાં, હેશ્ડ એરે ટ્રી (એચ. એ. ટી.) એ 1996માં એડવર્ડ સિતાર્સ્કી દ્વારા પ્રકાશિત ડાયનેમિક એરે ડેટા-સ્ટ્રક્ચર છે, જે ડેટા તત્વોને સંગ્રહિત કરવા માટે અલગ મેમરી ફ્રેગમેન્ટ્સ (અથવા "લીવ્ઝ") ની શ્રેણી જાળવી રાખે છે, જે સરળ ડાયનેમિક એરેથી વિપરીત છે, જે તેમના ડેટાને એક સંલગ્ન મેમરી એરિયામાં જાળવી રાખે છે. તેનો પ્રાથમિક ઉદ્દેશ સ્વચાલિત એરે કદ બદલવાની કામગીરીને કારણે તત્વની નકલની માત્રાને ઘટાડવાનો અને મેમરી ઉપયોગની પેટર્નમાં સુધારો કરવાનો છે. જ્યારે ભૌમિતિક વિસ્તરણ કચરો રેખીય (ω (n)) જગ્યા પર આધારિત સરળ ગતિશીલ એરે, જ્યાં n એ એરેમાં તત્વોની સંખ્યા છે, હેશ એરે વૃક્ષો માત્ર ઓર્ડર O () સંગ્રહ જગ્યા બગાડે છે. અલ્ગોરિધમનું ઓપ્ટિમાઇઝેશન નકામી જગ્યાને વધારવાની કિંમત પર ડેટાની નકલને સંપૂર્ણપણે દૂર કરવાની મંજૂરી આપે છે. તે સતત (ઓ (1)) સમયમાં પ્રવેશ કરી શકે છે, જોકે તે સરળ ગતિશીલ શ્રેણીઓ કરતાં સહેજ ધીમી છે. હેશ એરે ટ્રીના અંતમાં વસ્તુઓની શ્રેણી ઉમેરતી વખતે અલ્ગોરિધમ O (1) એમોર્ટાઇઝ્ડ પ્રદર્શન ધરાવે છે. તેના નામથી વિપરીત, તે હેશ કાર્યોનો ઉપયોગ કરતું નથી. વ્યાખ્યાઓ સિતારસ્કી દ્વારા વ્યાખ્યાયિત કર્યા મુજબ, હેશ એરે વૃક્ષમાં ટોચના સ્તરની ડિરેક્ટરી હોય છે જેમાં બે સંખ્યામાં પર્ણ એરેની શક્તિ હોય છે. બધા લીફ એરે ટોચના સ્તરની ડિરેક્ટરી જેવા જ કદના હોય છે. આ માળખું ઉપરછલ્લી રીતે એરે-આધારિત અથડામણ સાંકળો સાથે હેશ ટેબલ જેવું લાગે છે, જે નામ હેશ એરે ટ્રી માટેનો આધાર છે. સંપૂર્ણ હેશ કરેલ એરે વૃક્ષ m2 તત્વોને પકડી શકે છે, જ્યાં m એ ટોચના સ્તરની ડિરેક્ટરીનું કદ છે. બેની શક્તિનો ઉપયોગ ભાગાકાર અને શેષની અંકગણિત કામગીરીને બદલે બીટ કામગીરી દ્વારા ઝડપી ભૌતિક સંબોધનને સક્ષમ કરે છે અને વિસ્તરણ કરતી વખતે પ્રસંગોપાત વૈશ્વિક એરે કોપીની હાજરીમાં એપેન્ડ કામગીરીના ઓ (1) ઋણમુક્ત પ્રદર્શનને સુનિશ્ચિત કરે છે. વિસ્તરણ અને કદમાં ઘટાડો સામાન્ય ગતિશીલ એરે ભૌમિતિક વિસ્તરણ યોજનામાં, એરેને તેના વર્તમાન કદના બમણા નવા કદ સાથે મેમરીના સંપૂર્ણ ક્રમિક ભાગ તરીકે ફરીથી ગોઠવવામાં આવે છે (અને પછી સમગ્ર ડેટાને નવા સ્થાન પર ખસેડવામાં આવે છે). આ ઓ (એન) નકામી જગ્યાના ખર્ચે ઓ (1) ઋણમુક્ત કામગીરીની ખાતરી કરે છે, કારણ કે વિસ્તૃત શ્રેણી તેની નવી ક્ષમતાના અડધા સુધી ભરવામાં આવે છે. જ્યારે હેશ્ડ એરે ટ્રી ભરેલું હોય, ત્યારે તેની ડિરેક્ટરી અને પાંદડાઓને વધારાના એપેન્ડ કામગીરીને સમાવવા માટે તેમના અગાઉના કદથી બમણું પુનર્ગઠન કરવું આવશ્યક છે. જૂના માળખામાં રાખવામાં આવેલી માહિતી પછી નવા સ્થળોએ ખસેડવામાં આવે છે. પછી માત્ર એક નવું પાન ફાળવવામાં આવે છે અને ટોચની શ્રેણીમાં ઉમેરવામાં આવે છે જે આમ તેની નવી ક્ષમતાના માત્ર એક ચતુર્થાંશ સુધી ભરાય છે. તમામ વધારાના પાંદડાઓ હજુ ફાળવવામાં આવ્યા નથી, અને જ્યારે જરૂર પડશે ત્યારે જ ફાળવવામાં આવશે, આમ સંગ્રહનો માત્ર ઓ () બગાડે છે. કદ ઘટાડવા માટે બહુવિધ વિકલ્પો છેઃ જ્યારે હેશ્ડ એરે વૃક્ષ આઠમો ભાગ ભરેલું હોય, ત્યારે તેને નાના, અડધા ભરેલા હેશ્ડ એરે વૃક્ષમાં પુનર્ગઠન કરી શકાય છે; બીજો વિકલ્પ માત્ર પાંદડાઓનું કદ બદલ્યા વિના, બિનઉપયોગી પર્ણ એરેને મુક્ત કરવાનો છે. વધુ ઓપ્ટિમાઇઝેશનમાં જરૂરિયાત મુજબ ડિરેક્ટરી એરેને વધારતી વખતે કદ બદલ્યા વિના નવા પાંદડા ઉમેરવાનો સમાવેશ થાય છે, સંભવતઃ ભૌમિતિક વિસ્તરણ દ્વારા. આ નકામી જગ્યાને ઓ (એન) બનાવવાની કિંમત પર સંપૂર્ણ રીતે ડેટાની નકલ કરવાની જરૂરિયાતને દૂર કરશે, નાના અચળાંક સાથે, અને જ્યારે નિર્ધારિત થ્રેશોલ્ડ ઓવરહેડ સુધી પહોંચી જશે ત્યારે જ પુનર્ગઠન કરશે. સંબંધિત ડેટા સ્ટ્રક્ચર્સ બ્રોડનિક એટ અલ. એરે વૃક્ષોને હેશ કરવા માટે સમાન જગ્યા બગાડ રૂપરેખા સાથે ડાયનેમિક એરે અલ્ગોરિધમ રજૂ કર્યું. બ્રોડનિકનું અમલીકરણ હેશ્ડ એરે વૃક્ષોની સરખામણીમાં વધુ જટિલ સરનામાની ગણતરી કાર્ય સાથે અગાઉ ફાળવવામાં આવેલા પર્ણ એરેને જાળવી રાખે છે. ડાયનેમિક એરે અનરોલ્ડ લિન્ક્ડ લિસ્ટ બી-ટ્રી રેફરન્સ એરે પણ જુઓ