Open addressing
اوپن ایڈریسنگ، یا کلوزڈ ہیشنگ، ہیش ٹیبلز میں تصادم کے حل کا ایک طریقہ ہے۔ اس طریقہ کار کے ساتھ ہیش تصادم کو جانچ کر کے، یا صف (تحقیقات کی ترتیب) میں متبادل مقامات کے ذریعے تلاش کر کے حل کیا جاتا ہے جب تک کہ ہدف ریکارڈ نہ مل جائے، یا غیر استعمال شدہ صف سلاٹ نہ مل جائے، جو اس بات کی نشاندہی کرتا ہے کہ میز میں ایسی کوئی کلید نہیں ہے۔ معروف تحقیقات کے سلسلے میں شامل ہیں: لکیری تحقیقات جس میں تحقیقات کے درمیان وقفہ طے کیا جاتا ہے-اکثر 1 پر سیٹ کیا جاتا ہے۔ کواڈریٹک تحقیقات جس میں تحقیقات کے درمیان وقفہ کواڈریٹک طور پر بڑھتا ہے (اس لیے، اشاریہ جات کو کواڈریٹک فنکشن کے ذریعے بیان کیا جاتا ہے)۔ ڈبل ہیشنگ جس میں تحقیقات کے درمیان وقفہ ہر ریکارڈ کے لیے طے کیا جاتا ہے لیکن دوسرے ہیش فنکشن کے ذریعے شمار کیا جاتا ہے۔ ان طریقوں کے درمیان اہم تجارت یہ ہے کہ لکیری پروبنگ کی کیش کی بہترین کارکردگی ہوتی ہے لیکن یہ کلسٹرنگ کے لیے سب سے زیادہ حساس ہوتی ہے، جبکہ ڈبل ہیشنگ کی کیش کی کارکردگی ناقص ہوتی ہے لیکن عملی طور پر کوئی کلسٹرنگ ظاہر نہیں ہوتی ہے۔ دونوں علاقوں میں کواڈریٹک پروبنگ درمیان میں آتی ہے۔ ڈبل ہیشنگ کے لیے تحقیقات کی دیگر شکلوں کے مقابلے میں زیادہ گنتی کی بھی ضرورت پڑ سکتی ہے۔ ایڈریسنگ کے کچھ کھلے طریقے، جیسے ہاپسکچ ہیشنگ، رابن ہوڈ ہیشنگ، آخری بار آنے والے پہلے والے ہیشنگ اور کوکل ہیشنگ، نئی کلید کے لیے جگہ بنانے کے لیے صف میں موجود موجودہ چابیاں منتقل کرتے ہیں۔ یہ تحقیقات پر مبنی طریقوں کے مقابلے میں تلاش کا زیادہ سے زیادہ بہتر وقت فراہم کرتا ہے۔ اوپن ایڈریسنگ ہیش ٹیبل کی کارکردگی پر ایک اہم اثر لوڈ فیکٹر ہے ؛ یعنی استعمال ہونے والی صف میں سلاٹس کا تناسب۔ جیسے جیسے لوڈ فیکٹر 100% کی طرف بڑھتا ہے، دی گئی کلید کو تلاش کرنے یا داخل کرنے کے لیے درکار تحقیقات کی تعداد ڈرامائی طور پر بڑھ جاتی ہے۔ ایک بار ٹیبل بھر جانے کے بعد، تفتیشی الگورتھم ختم کرنے میں بھی ناکام ہو سکتے ہیں۔ یہاں تک کہ اچھے ہیش افعال کے ساتھ، لوڈ کے عوامل عام طور پر 80 ٪ تک محدود ہوتے ہیں۔ ایک ناقص ہیش فنکشن اہم کلسٹرنگ پیدا کرکے بہت کم بوجھ والے عوامل پر بھی ناقص کارکردگی کا مظاہرہ کر سکتا ہے، خاص طور پر آسان ترین لکیری ایڈریسنگ طریقہ کے ساتھ۔ عام طور پر زیادہ تر کھلے ایڈریسنگ طریقوں کے ساتھ عام بوجھ کے عوامل 50 ٪ ہوتے ہیں، جبکہ علیحدہ چیننگ عام طور پر 100% تک استعمال کر سکتی ہے۔ مثال سیوڈو کوڈ مندرجہ ذیل سیوڈو کوڈ لکیری پروبنگ اور سنگل سلاٹ اسٹیپنگ کے ساتھ ایک اوپن ایڈریسنگ ہیش ٹیبل کا نفاذ ہے، ایک عام نقطہ نظر جو مؤثر ہے اگر ہیش فنکشن اچھا ہے۔ تلاش، سیٹ اور ہٹانے والے افعال میں سے ہر ایک صف سلاٹ کا پتہ لگانے کے لیے ایک مشترکہ اندرونی فنکشن فائنڈ سلاٹ کا استعمال کرتا ہے جو یا تو دی گئی کلید پر مشتمل ہوتا ہے یا ہونا چاہیے۔ ریکارڈ جوڑی {کلید، قدر، قبضہ شدہ پرچم (ابتدائی طور پر غیر سیٹ)} ور جوڑی سلاٹ [0]، سلاٹ [1]، سلاٹ [num _ slot-1] فنکشن فائنڈ _ سلاٹ (کلید) i: = ہیش (کلید) ماڈیولو num _ slot// اس وقت تک تلاش کریں جب تک کہ ہمیں کلید نہ مل جائے، یا کوئی خالی سلاٹ نہ مل جائے۔ جبکہ (سلاٹ [i] پر قبضہ کر لیا گیا ہے) اور (سلاٹ [i]. کلیدی  ऒत्त کلید) i: = (i + 1) ماڈیولو نمبر سلاٹس ریٹرن آئی فنکشن لک اپ (کلید) i: = فائنڈ سلاٹ (کلید) اگر سلاٹ [i] پر قبضہ کر لیا گیا ہے// کلید ٹیبل ریٹرن سلاٹ میں ہے [i]. ویلیو دیگر// کلید ٹیبل ریٹرن میں نہیں ہے فنکشن سیٹ نہیں ملا (کلید، قیمت) i: = فائنڈ سلاٹ (کلید) اگر سلاٹ [i] پر قبضہ کر لیا گیا ہے// ہمیں اپنا کلیدی سلاٹ مل گیا ہے [i]. ویلیو = ویلیو ریٹرن اگر ٹیبل تقریبا مکمل ہو تو بڑی ٹیبل کو دوبارہ تعمیر کریں (نوٹ 1) i: = فائنڈ سلاٹ (کلیدی) مارک سلاٹ [i] بطور قبضہ شدہ سلاٹ [i] صف کے سائز میں تیزی سے اضافہ کرنا عام بات ہے، مثال کے طور پر پرانے صف کے سائز کو دوگنا کرکے۔ فنکشن ہٹائیں (کلید) i: = فائنڈ سلاٹ (کلید) اگر سلاٹ [i] غیر استعمال شدہ ریٹرن// کلید ٹیبل مارک سلاٹ [i] میں غیر استعمال شدہ جے کے طور پر نہیں ہے: = آئی لوپ (نوٹ 2) جے: = (جے + 1) ماڈیولو نمبر سلاٹس اگر سلاٹ [جے] غیر استعمال شدہ ایگزٹ لوپ کے ہے: = ہیش (سلاٹ [جے]. کلید) ماڈیولو نمبر سلاٹس// اس بات کا تعین کریں کہ آیا کے سائیکلکل طور پر (آئی، جے]// آئی ≤ جے:۔ آئی۔ کے۔ جے۔// آئی> جے:۔ کے۔ جے۔ آئی۔ یا۔ جے۔ جے۔ چھدم کوڈ میں اس مقام پر، ایک خالی سلاٹ ہے جو کلسٹر میں بعد کے ریکارڈ کے لیے اس پراپرٹی کو کالعدم قرار دے سکتا ہے۔ اس طرح کا ایک اگلا ریکارڈ ہے۔ یہ وہ خام ہیش ہے جہاں ریکارڈ قدرتی طور پر ہیش ٹیبل میں گر جائے گا اگر کوئی تصادم نہ ہو۔ یہ ٹیسٹ پوچھ رہا ہے کہ کیا کلسٹر کی مطلوبہ خصوصیات کے حوالے سے ریکارڈ کو غلط طریقے سے رکھا گیا ہے جو اب خالی ہے۔ ہٹانے کی ایک اور تکنیک صرف سلاٹ کو حذف شدہ کے طور پر نشان زد کرنا ہے۔ تاہم اس کے لیے بالآخر حذف شدہ ریکارڈ کو ہٹانے کے لیے میز کی تعمیر نو کی ضرورت ہوتی ہے۔ مندرجہ بالا طریقے O (1) فراہم کرتے ہیں کہ موجودہ ریکارڈ کو اپ ڈیٹ اور ہٹایا جائے، کبھی کبھار تعمیر نو کے ساتھ اگر میز کے سائز کا زیادہ پانی کا نشان بڑھتا ہے۔ اوپر O (1) ہٹانے کا طریقہ صرف واحد سلاٹ اسٹیپنگ کے ساتھ لکیری جانچ شدہ ہیش ٹیبلز میں ممکن ہے۔ ایسی صورت میں جہاں ایک آپریشن میں بہت سے ریکارڈز کو حذف کرنا ہے، حذف کرنے اور بعد میں تعمیر نو کے لیے سلاٹس کو نشان زد کرنا زیادہ موثر ہو سکتا ہے۔ سست حذف کرنا بھی دیکھیں-اوپن ایڈریسنگ کا استعمال کرتے ہوئے ہیش ٹیبل سے حذف کرنے کا ایک طریقہ۔ حوالہ جات ہیشنگ