Hashed array tree
कंप्यूटर विज्ञान में, एक हैश्ड ऐरे ट्री (एच. ए. टी.) 1996 में एडवर्ड सितार्स्की द्वारा प्रकाशित एक गतिशील सरणी डेटा-संरचना है, जो डेटा तत्वों को संग्रहीत करने के लिए अलग-अलग मेमोरी टुकड़ों (या "लीव्स") की एक सरणी को बनाए रखती है, जो सरल गतिशील सरणी के विपरीत है जो अपने डेटा को एक सन्निहित मेमोरी क्षेत्र में बनाए रखती है। इसका प्राथमिक उद्देश्य स्वचालित सरणी आकार परिवर्तन संचालन के कारण तत्व प्रतिलिपि की मात्रा को कम करना और स्मृति उपयोग पैटर्न में सुधार करना है। जबकि ज्यामितीय विस्तार अपशिष्ट रैखिक (ω (n)) स्थान पर आधारित सरल गतिशील सरणियाँ, जहाँ n सरणी में तत्वों की संख्या है, हैश किए गए सरणी पेड़ केवल O () भंडारण स्थान के क्रम को बर्बाद करते हैं। एल्गोरिदम का एक अनुकूलन बर्बाद स्थान को बढ़ाने की कीमत पर डेटा की नकल को पूरी तरह से समाप्त करने की अनुमति देता है। यह स्थिर (ओ (1)) समय में पहुँच का प्रदर्शन कर सकता है, हालांकि सरल गतिशील सरणियों की तुलना में थोड़ा धीमा है। एक हैश सरणी वृक्ष के अंत में वस्तुओं की एक श्रृंखला को जोड़ते समय एल्गोरिथ्म में ओ (1) परिशोधन प्रदर्शन होता है। अपने नाम के विपरीत, यह हैश कार्यों का उपयोग नहीं करता है। परिभाषाएँ जैसा कि सितारस्की द्वारा परिभाषित किया गया है, एक हैश्ड सरणी वृक्ष में एक शीर्ष-स्तरीय निर्देशिका होती है जिसमें दो संख्या में पत्ती सरणी की शक्ति होती है। सभी पत्ती सरणियाँ शीर्ष-स्तरीय निर्देशिका के समान आकार की होती हैं। यह संरचना सतही रूप से सरणी-आधारित टकराव श्रृंखलाओं के साथ एक हैश टेबल से मिलती-जुलती है, जो हैश्ड सरणी पेड़ नाम का आधार है। एक पूर्ण हैश सरणी वृक्ष m2 तत्वों को धारण कर सकता है, जहाँ m शीर्ष-स्तरीय निर्देशिका का आकार है। दो की शक्तियों का उपयोग भागफल और शेष के अंकगणितीय संचालन के बजाय बिट संचालन के माध्यम से तेजी से भौतिक संबोधन को सक्षम बनाता है और विस्तार करते समय सामयिक वैश्विक सरणी प्रतिलिपि की उपस्थिति में परिशिष्ट संचालन के ओ (1) परिशोधन प्रदर्शन को सुनिश्चित करता है। विस्तार और आकार में कमी एक सामान्य गतिशील सरणी ज्यामितीय विस्तार योजना में, सरणी को स्मृति के एक पूरे अनुक्रमिक हिस्से के रूप में नए आकार के साथ उसके वर्तमान आकार के दोगुने के साथ पुनः आवंटित किया जाता है (और फिर पूरे डेटा को नए स्थान पर ले जाया जाता है)। यह ओ (एन) बर्बाद स्थान की कीमत पर ओ (1) परिशोधन संचालन सुनिश्चित करता है, क्योंकि विस्तारित सरणी अपनी नई क्षमता के आधे तक भरी जाती है। जब एक हैश्ड सरणी पेड़ भरा होता है, तो अतिरिक्त परिशिष्ट संचालन को समायोजित करने के लिए इसकी निर्देशिका और पत्तियों को उनके पूर्व आकार से दोगुना किया जाना चाहिए। पुरानी संरचना में रखे गए डेटा को फिर नए स्थानों पर ले जाया जाता है। इसके बाद केवल एक नया पत्ता आवंटित किया जाता है और शीर्ष सरणी में जोड़ा जाता है जो इस प्रकार अपनी नई क्षमता के केवल एक चौथाई तक भर जाता है। सभी अतिरिक्त पत्तियां अभी तक आवंटित नहीं की गई हैं, और केवल आवश्यकता पड़ने पर आवंटित की जाएंगी, इस प्रकार भंडारण का केवल ओ () बर्बाद होगा। आकार को कम करने के लिए कई विकल्प हैंः जब एक हैश्ड सरणी पेड़ एक आठवां भरा होता है, तो इसे एक छोटे, आधे भरे हैश्ड सरणी पेड़ में पुनर्गठित किया जा सकता है; एक अन्य विकल्प केवल अप्रयुक्त पत्ती सरणी को मुक्त करना है, पत्तियों का आकार बदले बिना। आगे के अनुकूलन में आवश्यकता के अनुसार निर्देशिका सरणी को बढ़ाते समय आकार बदलने के बिना नए पत्ते जोड़ना शामिल है, संभवतः ज्यामितीय विस्तार के माध्यम से। यह एक छोटे से स्थिरांक के साथ बर्बाद स्थान को ओ (एन) बनाने की कीमत पर पूरी तरह से डेटा की प्रतिलिपि बनाने की आवश्यकता को समाप्त कर देगा, और केवल एक निर्धारित सीमा ओवरहेड तक पहुंचने पर पुनर्गठन करेगा। संबंधित डेटा संरचना ब्रोडनिक एट अल। हैश किए गए सरणी पेड़ों के लिए एक समान स्थान अपव्यय प्रोफ़ाइल के साथ एक गतिशील सरणी एल्गोरिथ्म प्रस्तुत किया। ब्रोडनिक का कार्यान्वयन हैश्ड सरणी पेड़ों की तुलना में अधिक जटिल पता गणना कार्य के साथ पहले आवंटित पत्ती सरणी को बरकरार रखता है। डायनेमिक सरणी अनरोल्ड लिंक सूची बी-ट्री संदर्भ सरणी भी देखें।