Hashed array tree
کمپیوٹر سائنس میں، ہیشڈ ایرے ٹری (ایچ اے ٹی) ایک متحرک ایرے ڈیٹا اسٹرکچر ہے جسے ایڈورڈ سیتارسکی نے 1996 میں شائع کیا تھا، جو ڈیٹا عناصر کو ذخیرہ کرنے کے لیے علیحدہ میموری کے ٹکڑوں (یا "پتے") کی ایک صف کو برقرار رکھتا ہے، سادہ متحرک صفوں کے برعکس جو اپنے ڈیٹا کو ایک متصل میموری ایریا میں برقرار رکھتے ہیں۔ اس کا بنیادی مقصد خودکار صف کے سائز میں تبدیلی کی کارروائیوں کی وجہ سے عنصر کی کاپی کی مقدار کو کم کرنا، اور میموری کے استعمال کے نمونوں کو بہتر بنانا ہے۔ جبکہ ہندسی توسیعی فضلہ لکیری (ω (n)) جگہ پر مبنی سادہ متحرک صف، جہاں n صف میں عناصر کی تعداد ہے، ہیشڈ صف کے درخت صرف آرڈر O () اسٹوریج کی جگہ کو ضائع کرتے ہیں۔ الگورتھم کی اصلاح ضائع شدہ جگہ کو بڑھانے کی قیمت پر ڈیٹا کی کاپی کو مکمل طور پر ختم کرنے کی اجازت دیتی ہے۔ یہ مستقل (O (1)) وقت میں رسائی انجام دے سکتا ہے، حالانکہ سادہ متحرک صفوں سے قدرے سست ہے۔ ہیشڈ ایرے ٹری کے آخر میں اشیاء کی ایک سیریز کو شامل کرتے وقت الگورتھم میں O (1) امورٹائزڈ کارکردگی ہوتی ہے۔ اس کے نام کے برعکس، یہ ہیش افعال استعمال نہیں کرتا ہے۔ تعریفیں جیسا کہ سیتارسکی نے بیان کیا ہے، ایک ہیشڈ ایرے ٹری میں ایک اعلی درجے کی ڈائرکٹری ہوتی ہے جس میں دو تعداد میں پتی کی صفوں کی طاقت ہوتی ہے۔ پتی کی تمام صفوں کا سائز اعلی درجے کی ڈائرکٹری کے برابر ہوتا ہے۔ یہ ڈھانچہ سطحی طور پر صف پر مبنی تصادم کی زنجیروں کے ساتھ ہیش ٹیبل سے ملتا جلتا ہے، جو ہیشڈ صف کے درخت کے نام کی بنیاد ہے۔ ایک مکمل ہیش والے صف کے درخت میں m2 عناصر ہو سکتے ہیں، جہاں m اعلی درجے کی ڈائرکٹری کا سائز ہے۔ دو کی طاقتوں کا استعمال حصص اور بقیہ کی ریاضی کی کارروائیوں کے بجائے بٹ آپریشنز کے ذریعے تیزی سے فزیکل ایڈریسنگ کو قابل بناتا ہے اور توسیع کے دوران کبھی کبھار عالمی صف کی کاپی کی موجودگی میں اپینڈ آپریشن کی O (1) امورٹائزڈ کارکردگی کو یقینی بناتا ہے۔ توسیع اور سائز میں کمی ایک معمول کی متحرک صف ہندسی توسیع اسکیم میں، صف کو میموری کے پورے ترتیب وار حصے کے طور پر نئے سائز کے ساتھ اس کے موجودہ سائز سے دوگنا (اور پھر پورے ڈیٹا کو نئے مقام پر منتقل کیا جاتا ہے) کے ساتھ دوبارہ مختص کیا جاتا ہے۔ یہ O (n) ضائع شدہ جگہ کی قیمت پر O (1) امورٹائزڈ آپریشنز کو یقینی بناتا ہے، کیونکہ بڑھا ہوا صف اپنی نئی صلاحیت کے نصف تک بھرا ہوا ہے۔ جب ایک ہیشڈ ایرے ٹری بھرا ہوا ہوتا ہے، تو اضافی ضمیمہ کارروائیوں کو ایڈجسٹ کرنے کے لیے اس کی ڈائرکٹری اور پتوں کو ان کے پہلے سائز سے دوگنا دوبارہ تشکیل دیا جانا چاہیے۔ پرانے ڈھانچے میں رکھے گئے ڈیٹا کو پھر نئے مقامات پر منتقل کیا جاتا ہے۔ اس کے بعد صرف ایک نیا پتی مختص کیا جاتا ہے اور اوپر کی صف میں شامل کیا جاتا ہے جو اس طرح اس کی نئی صلاحیت کے صرف ایک چوتھائی تک بھر جاتا ہے۔ تمام اضافی پتے ابھی مختص نہیں کیے گئے ہیں، اور صرف ضرورت پڑنے پر مختص کیے جائیں گے، اس طرح اسٹوریج کا صرف او () ضائع ہوتا ہے۔ سائز کو کم کرنے کے لیے متعدد متبادل موجود ہیں: جب ہیشڈ ایرے ٹری کا آٹھواں حصہ بھرا ہوتا ہے، تو اسے چھوٹے، آدھے بھرے ہیشڈ ایرے ٹری میں دوبارہ تشکیل دیا جا سکتا ہے ؛ دوسرا آپشن صرف غیر استعمال شدہ پتی کی صفوں کو آزاد کرنا ہے، بغیر پتوں کے سائز کو تبدیل کیے۔ مزید اصلاح میں ضرورت کے مطابق ڈائرکٹری کی صف کو بڑھاتے ہوئے بغیر سائز تبدیل کیے نئے پتے شامل کرنا شامل ہے، ممکنہ طور پر ہندسی توسیع کے ذریعے۔ یہ ضائع شدہ جگہ کو O (n) بنانے کی قیمت پر مکمل طور پر ڈیٹا کاپی کرنے کی ضرورت کو ختم کر دے گا، ایک چھوٹے سے مستقل کے ساتھ، اور صرف اس وقت تنظیم نو انجام دے گا جب ایک مقررہ حد تک پہنچ جائے۔ متعلقہ ڈیٹا ڈھانچے بروڈنک اور دیگر۔ ہیشڈ ایرے کے درختوں کے لیے اسی طرح کی جگہ ضائع کرنے والی پروفائل کے ساتھ ایک متحرک ایرے الگورتھم پیش کیا۔ بروڈنک کا نفاذ پہلے سے مختص شدہ پتی کی صفوں کو برقرار رکھتا ہے، جس میں ہیشڈ صف کے درختوں کے مقابلے میں ایڈریس کا حساب لگانا زیادہ پیچیدہ ہے۔ ڈائنامک ایرے انرولڈ لنکڈ لسٹ بی-ٹری ریفرنسز ایرے بھی دیکھیں