Hashed array tree
কম্পিউটার বিজ্ঞানে, হ্যাশড অ্যারে ট্রি (এইচএটি) হল 1996 সালে এডওয়ার্ড সিটারস্কি দ্বারা প্রকাশিত একটি গতিশীল অ্যারে ডেটা-স্ট্রাকচার, যা ডেটা উপাদানগুলি সংরক্ষণের জন্য পৃথক মেমরি টুকরোগুলির (বা "পাতাগুলি") একটি অ্যারে বজায় রাখে, সাধারণ গতিশীল অ্যারেগুলির বিপরীতে যা তাদের ডেটা বজায় রাখে একটি সংলগ্ন মেমরি এলাকায়। এর প্রাথমিক উদ্দেশ্য হল স্বয়ংক্রিয় অ্যারে রিসাইজিং ক্রিয়াকলাপের কারণে উপাদান অনুলিপির পরিমাণ হ্রাস করা এবং মেমরি ব্যবহারের ধরণ উন্নত করা। যেখানে জ্যামিতিক সম্প্রসারণ বর্জ্য রৈখিক (ω (n)) স্থানের উপর ভিত্তি করে সাধারণ গতিশীল অ্যারে, যেখানে n হল অ্যারের উপাদানগুলির সংখ্যা, হ্যাশড অ্যারে গাছগুলি কেবল O () সঞ্চয় স্থানের ক্রম অপচয় করে। অ্যালগরিদমের একটি অপ্টিমাইজেশন বর্জ্য স্থান বাড়ানোর ব্যয়ে ডেটা অনুলিপি সম্পূর্ণরূপে নির্মূল করার অনুমতি দেয়। এটি ধ্রুবক (ও (1)) সময়ে অ্যাক্সেস সম্পাদন করতে পারে, যদিও সাধারণ গতিশীল অ্যারেগুলির তুলনায় কিছুটা ধীর। একটি হ্যাশড অ্যারে গাছের শেষে বস্তুর একটি সিরিজ যুক্ত করার সময় অ্যালগরিদমের ও (1) অ্যামোর্টাইজড পারফরম্যান্স থাকে। এর নামের বিপরীতে, এটি হ্যাশ ফাংশন ব্যবহার করে না। সংজ্ঞা যেমন সিতারস্কি সংজ্ঞায়িত করেছেন, একটি হ্যাশ অ্যারে ট্রি-র একটি শীর্ষ-স্তরের ডিরেক্টরি থাকে যা দুটি সংখ্যক পাতার অ্যারে ধারণ করে। সমস্ত পাতার অ্যারেগুলি শীর্ষ-স্তরের ডিরেক্টরির সমান আকারের। এই কাঠামোটি উপরিভাগে অ্যারে-ভিত্তিক সংঘর্ষ শৃঙ্খল সহ একটি হ্যাশ টেবিলের অনুরূপ, যা হ্যাশড অ্যারে ট্রি নামের ভিত্তি। একটি পূর্ণ হ্যাশযুক্ত অ্যারে ট্রি m2 উপাদান ধারণ করতে পারে, যেখানে m হল শীর্ষ-স্তরের ডিরেক্টরির আকার। দুটির ক্ষমতার ব্যবহার ভাগফল এবং অবশিষ্টাংশের গাণিতিক ক্রিয়াকলাপের পরিবর্তে বিট ক্রিয়াকলাপের মাধ্যমে দ্রুত শারীরিক সম্বোধনকে সক্ষম করে এবং প্রসারিত হওয়ার সময় মাঝে মাঝে গ্লোবাল অ্যারে কপির উপস্থিতিতে অ্যাপেন্ড ক্রিয়াকলাপের ও (1) পরিশোধন কর্মক্ষমতা নিশ্চিত করে। সম্প্রসারণ এবং আকার হ্রাস একটি সাধারণ গতিশীল অ্যারে জ্যামিতিক সম্প্রসারণ পরিকল্পনায়, অ্যারেটি তার বর্তমান আকারের দ্বিগুণ নতুন আকারের সাথে মেমরির একটি সম্পূর্ণ ক্রমিক অংশ হিসাবে পুনরায় বরাদ্দ করা হয় (এবং পুরো ডেটা তারপর নতুন অবস্থানে স্থানান্তরিত হয়)। এটি ও (এন) নষ্ট জায়গার ব্যয়ে ও (1) পরিশোধিত ক্রিয়াকলাপগুলি নিশ্চিত করে, কারণ বর্ধিত অ্যারেটি তার নতুন ক্ষমতার অর্ধেক পূরণ করা হয়। যখন একটি হ্যাশড অ্যারে ট্রি পূর্ণ থাকে, তখন অতিরিক্ত সংযোজন ক্রিয়াকলাপের জন্য তার ডিরেক্টরি এবং পাতাগুলি অবশ্যই তাদের পূর্বের আকারের দ্বিগুণ পুনর্গঠন করতে হবে। পুরনো কাঠামোতে রাখা তথ্য তারপর নতুন জায়গায় স্থানান্তরিত করা হয়। তারপরে শুধুমাত্র একটি নতুন পাতা বরাদ্দ করা হয় এবং উপরের অ্যারেতে যুক্ত করা হয় যা এইভাবে তার নতুন ক্ষমতার মাত্র এক চতুর্থাংশ পূরণ হয়। সমস্ত অতিরিক্ত পাতা এখনও বরাদ্দ করা হয়নি, এবং শুধুমাত্র যখন প্রয়োজন হবে তখনই বরাদ্দ করা হবে, এইভাবে শুধুমাত্র ও () সঞ্চয় নষ্ট হবে। আকার হ্রাস করার জন্য একাধিক বিকল্প রয়েছেঃ যখন একটি হ্যাশড অ্যারে গাছ এক অষ্টমাংশ পূর্ণ হয়, তখন এটি একটি ছোট, অর্ধ-পূর্ণ হ্যাশড অ্যারে গাছে পুনর্গঠন করা যেতে পারে; আরেকটি বিকল্প হল পাতার আকার পরিবর্তন না করে শুধুমাত্র অব্যবহৃত পাতার অ্যারে মুক্ত করা। আরও অপ্টিমাইজেশনের মধ্যে রয়েছে প্রয়োজন অনুযায়ী ডিরেক্টরি অ্যারে বাড়ানোর সময় আকার পরিবর্তন না করে নতুন পাতা যোগ করা, সম্ভবত জ্যামিতিক সম্প্রসারণের মাধ্যমে। এটি একটি ছোট ধ্রুবক সহ বর্জ্য স্থানটিকে ও (এন) করার ব্যয়ে সম্পূর্ণরূপে ডেটা অনুলিপি করার প্রয়োজনীয়তা দূর করবে এবং শুধুমাত্র একটি নির্দিষ্ট প্রান্তিক ওভারহেডে পৌঁছলে পুনর্গঠন সম্পাদন করবে। সম্পর্কিত তথ্য কাঠামো ব্রডনিক এবং অন্যান্য। অ্যারে গাছগুলিকে হ্যাশ করার জন্য অনুরূপ স্থান অপচয় প্রোফাইল সহ একটি গতিশীল অ্যারে অ্যালগরিদম উপস্থাপন করেছেন। ব্রডনিকের বাস্তবায়ন হ্যাশড অ্যারে গাছের তুলনায় আরও জটিল ঠিকানা গণনার ফাংশন সহ পূর্বে বরাদ্দকৃত পাতার অ্যারে ধরে রেখেছে। আরও দেখুন ডায়নামিক অ্যারে আনরোল্ড লিঙ্কযুক্ত তালিকা বি-ট্রি রেফারেন্স অ্যারে