Hashed array tree
கணினி அறிவியலில், ஒரு ஹாஷ் அரே ட்ரீ (எச்ஏடி) என்பது 1996 ஆம் ஆண்டில் எட்வர்ட் சிதார்ஸ்கியால் வெளியிடப்பட்ட ஒரு மாறும் வரிசை தரவு-கட்டமைப்பாகும், இது தரவு கூறுகளை சேமிக்க தனித்தனி நினைவக துண்டுகளின் (அல்லது "லீவ்ஸ்") வரிசையை பராமரிக்கிறது, இது எளிய மாறும் வரிசைகளைப் போலல்லாமல், அவற்றின் தரவை ஒரு தொடர்ச்சியான நினைவகப் பகுதியில் பராமரிக்கிறது. தானியங்கி வரிசை மறுஅளவிடுதல் செயல்பாடுகள் காரணமாக உறுப்பு நகலெடுப்பின் அளவைக் குறைப்பதும், நினைவக பயன்பாட்டு முறைகளை மேம்படுத்துவதும் இதன் முதன்மை நோக்கமாகும். அதேசமயம் வடிவியல் விரிவாக்க கழிவு நேரியல் (ω (n)) இடத்தை அடிப்படையாகக் கொண்ட எளிய மாறும் வரிசைகள், இங்கு n என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை, ஹாஷ் வரிசை மரங்கள் O () சேமிப்பு இடத்தை மட்டுமே வரிசைப்படுத்துகின்றன. வழிமுறையின் உகப்பாக்கம், வீணான இடத்தை அதிகரிக்கும் செலவில், தரவு நகலெடுப்பை முற்றிலுமாக அகற்ற அனுமதிக்கிறது. இது நிலையான (ஓ (1)) நேரத்தில் அணுகலைச் செய்ய முடியும், இருப்பினும் எளிய மாறும் வரிசைகளை விட சற்றே மெதுவாக இருக்கும். ஒரு ஹாஷ் வரிசை மரத்தின் முடிவில் தொடர்ச்சியான பொருள்களைச் சேர்க்கும்போது இந்த வழிமுறை O (1) கடனுதவி செயல்திறனைக் கொண்டுள்ளது. அதன் பெயருக்கு மாறாக, இது ஹாஷ் செயல்பாடுகளைப் பயன்படுத்துவதில்லை. வரையறைகள் சிதார்ஸ்கியால் வரையறுக்கப்பட்டுள்ளபடி, ஒரு ஹாஷ் வரிசை மரம் இரண்டு எண்ணிக்கையிலான இலை வரிசைகளின் சக்தியைக் கொண்ட ஒரு உயர்மட்ட அடைவைக் கொண்டுள்ளது. அனைத்து இலை வரிசைகளும் மேல் நிலை கோப்பகத்தின் அதே அளவு கொண்டவை. இந்த அமைப்பு மேலோட்டமாக வரிசை அடிப்படையிலான மோதல் சங்கிலிகளுடன் ஒரு ஹாஷ் அட்டவணையை ஒத்திருக்கிறது, இது ஹாஷ் வரிசை மரத்தின் பெயருக்கு அடிப்படையாகும். ஒரு முழு ஹாஷ் வரிசை மரம் m2 கூறுகளை வைத்திருக்க முடியும், அங்கு m என்பது மேல் நிலை கோப்பகத்தின் அளவு. இரண்டின் சக்திகளைப் பயன்படுத்துவது ஈவு மற்றும் மீதமுள்ள எண்கணித செயல்பாடுகளுக்குப் பதிலாக பிட் செயல்பாடுகள் மூலம் விரைவான இயற்பியல் முகவரியை செயல்படுத்துகிறது மற்றும் விரிவடையும் போது அவ்வப்போது உலகளாவிய வரிசை நகல் முன்னிலையில் இணைப்பு செயல்பாட்டின் O (1) கடன்தொகை செயல்திறனை உறுதி செய்கிறது. விரிவாக்கங்கள் மற்றும் அளவு குறைப்புகள் ஒரு வழக்கமான மாறும் வரிசை வடிவியல் விரிவாக்க திட்டத்தில், வரிசை அதன் தற்போதைய அளவை விட இரண்டு மடங்கு புதிய அளவுடன் நினைவகத்தின் முழு தொடர்ச்சியான பகுதியாக மறுசீரமைக்கப்படுகிறது (பின்னர் முழு தரவும் புதிய இடத்திற்கு நகர்த்தப்படுகிறது). விரிவாக்கப்பட்ட வரிசை அதன் புதிய திறனில் பாதிக்கு நிரப்பப்படுவதால், இது O (n) வீணடிக்கப்பட்ட இடத்தின் செலவில் O (1) கடனுதவி செய்யப்பட்ட செயல்பாடுகளை உறுதி செய்கிறது. ஒரு ஹேஷ் செய்யப்பட்ட வரிசை மரம் நிரம்பியிருக்கும் போது, கூடுதல் இணைப்பு செயல்பாடுகளுக்கு இடமளிக்க அதன் அடைவு மற்றும் இலைகள் அவற்றின் முந்தைய அளவை விட இரண்டு மடங்கு மறுசீரமைக்கப்பட வேண்டும். பழைய கட்டமைப்பில் வைக்கப்பட்டுள்ள தரவு பின்னர் புதிய இடங்களுக்கு மாற்றப்படுகிறது. ஒரு புதிய இலை மட்டுமே ஒதுக்கப்பட்டு மேல் வரிசையில் சேர்க்கப்படுகிறது, இதனால் அதன் புதிய திறனில் கால் பகுதி மட்டுமே நிரப்பப்படுகிறது. அனைத்து கூடுதல் இலைகளும் இன்னும் ஒதுக்கப்படவில்லை, மேலும் தேவைப்படும்போது மட்டுமே ஒதுக்கப்படும், இதனால் சேமிப்பில் O () மட்டுமே வீணாகும். அளவைக் குறைப்பதற்கு பல மாற்று வழிகள் உள்ளனஃ ஒரு ஹாஷ் வரிசை மரம் எட்டில் ஒரு பங்கு நிரம்பும்போது, அதை ஒரு சிறிய, அரை நிரம்பிய ஹாஷ் வரிசை மரமாக மறுசீரமைக்கலாம்; மற்றொரு வழி, இலைகளின் அளவை மாற்றாமல், பயன்படுத்தப்படாத இலை வரிசைகளை மட்டுமே விடுவிப்பதாகும். மேலும் உகப்பாக்குதல்களில் தேவைக்கேற்ப அடைவு வரிசையை வளர்க்கும் போது, வடிவியல் விரிவாக்கத்தின் மூலம், அளவை மாற்றாமல் புதிய இலைகளைச் சேர்ப்பது அடங்கும். இது வீணான இடத்தை ஓ (என்) ஆக மாற்றும் செலவில் தரவை முழுமையாக நகலெடுக்க வேண்டிய தேவையை அகற்றும், ஒரு சிறிய மாறிலியுடன், மற்றும் ஒரு செட் வாசல் மேல்நிலையை அடையும் போது மட்டுமே மறுசீரமைப்பைச் செய்யும். தொடர்புடைய தரவு கட்டமைப்புகள் ப்ரோட்னிக் மற்றும் பலர். ஹேஷ் செய்யப்பட்ட வரிசை மரங்களுக்கு ஒத்த இடத்தை வீணடிக்கும் சுயவிவரத்துடன் ஒரு மாறும் வரிசை வழிமுறையை வழங்கியது. ஹேஷ் வரிசை மரங்களுடன் ஒப்பிடும்போது மிகவும் சிக்கலான முகவரி கணக்கீட்டு செயல்பாட்டுடன், முன்பு ஒதுக்கப்பட்ட இலை வரிசைகளை ப்ராட்னிக் செயல்படுத்துகிறது. மேலும் காண்க டைனமிக் வரிசை பட்டியலிடப்படாத இணைக்கப்பட்ட பட்டியல் பி-மரம் குறிப்புகள் வரிசைகள்