Retrieval Data Structure
کمپیوٹر سائنس میں، بازیافت ڈیٹا ڈھانچہ، جسے جامد فنکشن بھی کہا جاتا ہے، ایک خلائی موثر لغت جیسی ڈیٹا ٹائپ ہے جو (کلیدی، قدر) جوڑوں کے مجموعے پر مشتمل ہوتی ہے جو مندرجہ ذیل کارروائیوں کی اجازت دیتی ہے: (کلیدی، قدر) جوڑوں کے مجموعے سے تعمیر دی گئی کلید یا کسی بھی چیز سے وابستہ قدر کو دوبارہ حاصل کریں اگر کلیکشن میں کلید موجود نہیں ہے تو کلید (اختیاری) سے وابستہ قدر کو اپ ڈیٹ کریں انہیں کائنات کے لیے ایک فنکشن اور کلیدوں کے سیٹ کے طور پر بھی سوچا جا سکتا ہے جہاں بازیافت کو کسی بھی قدر اور بصورت دیگر صوابدیدی قدر کے لیے واپس آنا پڑتا ہے۔ جامد افعال کے برعکس، اے ایم کیو فلٹر (ممکنہ) رکنیت کے سوالات کی حمایت کرتے ہیں اور لغت اضافی طور پر کلیدوں کو درج کرنے یا کلید سے وابستہ قدر کو تلاش کرنے اور اگر کلید موجود نہیں ہے تو کسی اور علامت کو واپس کرنے جیسے کاموں کی اجازت دیتے ہیں۔ جیسا کہ کارروائیوں سے اخذ کیا جا سکتا ہے، اس ڈیٹا ڈھانچے کو چابیاں بالکل بھی ذخیرہ کرنے کی ضرورت نہیں ہے اور اصل میں کلیدی قدر کے جوڑوں کی سادہ فہرست کے لیے درکار جگہ سے کم جگہ استعمال کر سکتا ہے۔ یہ ان حالات میں اسے پرکشش بناتا ہے جہاں متعلقہ ڈیٹا چھوٹا ہوتا ہے (جیسے۔ چند بٹس) چابیاں کے مقابلے میں کیونکہ ہم چابیاں استعمال کرنے والی جگہ کو کم کر کے بہت کچھ بچا سکتے ہیں۔ ایک سادہ سی مثال دینے کے لیے فرض کریں کہ ویڈیو گیم کے ناموں کو بولین کے ساتھ بیان کیا گیا ہے جس سے یہ ظاہر ہوتا ہے کہ آیا اس گیم میں کوئی کتا ہے جسے پالتو کیا جا سکتا ہے۔ اس ڈیٹا بیس سے بنایا گیا ایک جامد فنکشن اصل سیٹ میں موجود تمام ناموں کے لیے متعلقہ پرچم کو دوبارہ پیش کر سکتا ہے اور دوسرے ناموں کے لیے من مانی پرچم کو۔ اس جامد فنکشن کے سائز کو چھوٹے کے لیے صرف بٹس بنایا جا سکتا ہے جو ظاہر ہے کہ کسی بھی جوڑے پر مبنی نمائندگی سے بہت کم ہے۔ مثالیں جامد فنکشن کی ایک معمولی مثال کلیدوں اور اقدار کی ایک ترتیب شدہ فہرست ہے جو مذکورہ بالا تمام کارروائیوں اور بہت سی دوسری چیزوں کو نافذ کرتی ہے۔ تاہم، فہرست پر بازیافت سست ہے اور ہم بہت سے غیر ضروری کارروائیوں کو نافذ کرتے ہیں جنہیں اصلاح کی اجازت دینے کے لیے ہٹایا جا سکتا ہے۔ مزید برآں، ہمیں کچرا واپس کرنے کی بھی اجازت ہے اگر پوچھ گچھ کی کلید موجود نہیں ہے جو ہم نے بالکل استعمال نہیں کی ہے۔ کامل ہیش افعال جامد فنکشن بنانے کی ایک اور آسان مثال ایک کامل ہیش فنکشن کا استعمال کرنا ہے: ہماری چابیاں کے لیے پی ایچ ایف بنانے کے بعد، متعلقہ اقدار کو کلید کے لیے صحیح پوزیشن پر محفوظ کریں۔ جیسا کہ دیکھا جا سکتا ہے، یہ نقطہ نظر متعلقہ اقدار کو اپ ڈیٹ کرنے کی بھی اجازت دیتا ہے، چابیاں جامد ہونی چاہئیں۔ درستگی کامل ہیش فنکشن کی درستگی سے ہوتی ہے۔ اگر متعلقہ اقدار نسبتا کم ہوں تو کم از کم کامل ہیش فنکشن کا استعمال ایک بڑی جگہ کی بہتری دیتا ہے۔ XOR-بازیافت ہیشڈ فلٹرز کو ان کے سوالات کے ذریعے OR، AND اور XOR-فلٹرز میں درجہ بند کیا جا سکتا ہے۔ مثال کے طور پر، بلوم فلٹر ایک AND-فلٹر ہے کیونکہ اگر تمام جانچ شدہ مقامات میل کھاتے ہیں تو یہ رکنیت کے استفسار کے لیے درست ہوتا ہے۔ ایکس او آر فلٹر صرف جامد بازیافت کے لیے کام کرتے ہیں اور انہیں مؤثر طریقے سے جگہ بنانے کے لیے سب سے زیادہ امید افزا ہیں۔ وہ ایک لکیری نظام کو حل کرکے بنائے جاتے ہیں جو اس بات کو یقینی بناتا ہے کہ ہر کلید کے لیے ایک استفسار درست ہو۔ تعمیر ایک ہیش فنکشن کو دیکھتے ہوئے جو ہر کلید کو لمبائی کے بٹ ویکٹر سے نقشہ بناتا ہے جہاں سب لکیری طور پر آزاد ہوتے ہیں لکیری مساوات کے درج ذیل نظام کا ایک حل ہوتا ہے: لہذا، جامد فنکشن اور اور جگہ کے استعمال کا غلبہ ہے جس کے ذریعہ تقریبا بٹس فی کلید ہے، ہیش فنکشن کو چھوٹا سمجھا جاتا ہے۔ کے لیے بازیافت کو تمام سیٹ بٹس کے لیے قطاروں کے بٹ وائز XOR کے طور پر ظاہر کیا جا سکتا ہے۔ مزید برآں، تیز سوالات کے لیے بہت کم ضرورت ہوتی ہے، اس طرح اس طریقہ کے لیے جن مسائل کو حل کرنے کی ضرورت ہے وہ ایک مناسب ہیش فنکشن تلاش کرنا اور پھر بھی لکیری مساوات کے نظام کو مؤثر طریقے سے حل کرنے کے قابل ہونا ہے۔ ربن کی بازیافت ایک غیر معمولی بے ترتیب میٹرکس کا استعمال کرتے ہوئے بازیافت کیشے کو غیر موثر بنا دیتا ہے کیونکہ وہ بے ترتیب غیر مقامی پیٹرن میں زیادہ تر رسائی حاصل کرتے ہیں۔ ہر ایک کو چوڑائی کا مسلسل "ربن" دے کر ربن کی بازیافت میں بہتری آتی ہے جس میں بٹس بے ترتیب طور پر سیٹ کیے جاتے ہیں۔ میٹرکس کی خصوصیات کا استعمال متوقع وقت میں کیا جا سکتا ہے: ربن حل کرنے کا کام صفوں کو پہلے ان کی ابتدائی پوزیشن کے مطابق ترتیب دینا ہے (مثال کے طور پر۔ گنتی کی قسم)۔ پھر، ایک REM فارم کو موجودہ قطار کے بالکل نیچے قطاروں پر صف آپریشن انجام دے کر، اس قطار کے پہلے 1-اندراج کے نیچے تمام کالموں میں تمام 1-اندراجات کو ختم کر کے بار بار بنایا جا سکتا ہے۔ صف کی کارروائیاں ربن سے باہر کوئی قدر پیدا نہیں کرتی ہیں اور بہت سستی ہوتی ہیں کیونکہ انہیں صرف بٹس کے ایکس او آر کی ضرورت ہوتی ہے جو رام پر وقت پر کیا جا سکتا ہے۔ یہ دکھایا جا سکتا ہے کہ قطار کی کارروائیوں کی متوقع مقدار ہے۔ آخر میں، حل بیک سبسٹیوشن کے ذریعے حاصل کیا جاتا ہے۔ ایپلی کیشنز لگ بھگ رکنیت ایک لگ بھگ رکنیت کے ڈیٹا ڈھانچے کی تعمیر کے لیے فنگر پرنٹنگ فنکشن کا استعمال کرتے ہیں۔ پھر ہماری چابیاں کے ڈومین تک محدود ایک جامد فنکشن بنائیں۔ کسی عنصر کی رکنیت کی جانچ اس کے ساتھ اندازہ لگا کر اور اگر واپس کی گئی قیمت برابر ہے تو درست واپس کرکے کی جاتی ہے۔ اگر، صحیح قیمت واپس کرتا ہے اور ہم درست واپس کرتے ہیں۔ بصورت دیگر، بے ترتیب قدر واپس کرتا ہے اور ہم غلط جواب دے سکتے ہیں۔ ہیش کی لمبائی غلط مثبت شرح کو کنٹرول کرنے کی اجازت دیتی ہے۔ اس ڈیٹا ڈھانچے کی کارکردگی بالکل بنیادی جامد فنکشن کی کارکردگی ہے۔ کامل ہیش افعال ایک بازیافت ڈیٹا ڈھانچہ ایک کامل ہیش فنکشن کی تعمیر کے لیے استعمال کیا جا سکتا ہے: پہلے ہیش افعال اور سائز 1 کی بالٹیوں کے ساتھ کوکل ہیش ٹیبل میں چابیاں داخل کریں۔ پھر، ہر کلیدی اسٹور کے لیے ہیش فنکشن کا انڈیکس جو-بٹ ریٹریول ڈیٹا ڈھانچے میں ہیش ٹیبل میں کلیدی کے داخل ہونے کا باعث بنتا ہے۔ کامل ہیش فنکشن کی طرف سے دیا جاتا ہے. حوالہ جات خلاصہ ڈیٹا کی اقسام ایسوسی ایٹیو صف