Hash collision
کمپیوٹر سائنس میں، ہیش تصادم یا ہیش تصادم اس وقت ہوتا ہے جب ہیش ٹیبل میں ڈیٹا کے دو ٹکڑے ایک ہی ہیش ویلیو کا اشتراک کرتے ہیں۔ اس معاملے میں ہیش ویلیو ایک ہیش فنکشن سے حاصل کی جاتی ہے جو ڈیٹا ان پٹ لیتا ہے اور بٹس کی ایک مقررہ لمبائی واپس کرتا ہے۔ اگرچہ ہیش الگورتھم تصادم مزاحم ہونے کے ارادے سے بنائے گئے ہیں، پھر بھی وہ بعض اوقات مختلف ڈیٹا کو ایک ہی ہیش (کبوتر کے سوراخ کے اصول کی وجہ سے) میں نقشہ بنا سکتے ہیں۔ بدنیتی پر مبنی صارفین ڈیٹا کی نقل کرنے، رسائی حاصل کرنے یا اسے تبدیل کرنے کے لیے اس کا فائدہ اٹھا سکتے ہیں۔ ڈیٹا مینجمنٹ اور کمپیوٹر سیکیورٹی (خاص طور پر، کرپٹوگرافک ہیش افعال) میں ہیش تصادم کی ممکنہ منفی ایپلی کیشنز کی وجہ سے، تصادم سے بچنا کمپیوٹر سیکیورٹی میں ایک اہم موضوع بن گیا ہے۔ بیک گراؤنڈ ہیش کے تصادم ناگزیر ہو سکتے ہیں جو اس بات پر منحصر ہے کہ کسی سیٹ میں موجود اشیاء کی تعداد اور ان کی نقشہ بند بٹ سٹرنگ کی لمبائی کافی لمبی ہے یا نہیں۔ جب n اشیاء کا ایک مجموعہ ہوتا ہے، اگر n |R | سے بڑا ہے، جو اس صورت میں R ہیش ویلیو کی حد ہے، تو ہیش تصادم ہونے کا امکان 1 ہے، یعنی اس کے ہونے کی ضمانت ہے۔ ہیش کے تصادم کی ایک اور وجہ ممکنہ طور پر کسی وقت ریاضی میں برتھ ڈے پیراڈوکس کے خیال سے پیدا ہوتی ہے۔ یہ مسئلہ بے ترتیب طور پر منتخب کردہ دو لوگوں کے ایک سیٹ کے n تعداد میں سے ایک ہی سالگرہ کے امکان کو دیکھتا ہے۔ اس خیال کی وجہ سے اسے سالگرہ کا حملہ کہا گیا ہے۔ اس حملے کی بنیاد یہ ہے کہ ایسی سالگرہ تلاش کرنا مشکل ہے جو خاص طور پر آپ کی سالگرہ یا کسی مخصوص سالگرہ سے میل کھاتی ہو، لیکن ملنے والی سالگرہ کے ساتھ کسی بھی دو افراد کا مجموعہ تلاش کرنے کا امکان اس امکان کو بہت بڑھاتا ہے۔ خراب اداکار اس نقطہ نظر کو استعمال کر سکتے ہیں تاکہ ان کے لیے کسی مخصوص قدر کی تلاش کے بجائے کسی بھی دوسری ہیش قدر سے ٹکرانے والی ہیش اقدار کو تلاش کرنا آسان ہو۔ تصادم کا اثر درخواست پر منحصر ہوتا ہے۔ جب ہیش فنکشنز اور فنگر پرنٹس کو اسی طرح کے ڈیٹا کی شناخت کے لیے استعمال کیا جاتا ہے، جیسے کہ ہومولوگس ڈی این اے سیکوینسز یا اسی طرح کی آڈیو فائلیں، تو فنکشنز کو اس طرح ڈیزائن کیا جاتا ہے کہ مقامی حساس ہیشنگ جیسی تکنیکوں کا استعمال کرتے ہوئے الگ لیکن اسی طرح کے ڈیٹا کے درمیان تصادم کے امکان کو زیادہ سے زیادہ کیا جا سکے۔ دوسری طرف چیکسم، بہت مختلف ان پٹ کے درمیان تصادم کی پرواہ کیے بغیر، اسی طرح کے ان پٹ کے درمیان تصادم کے امکان کو کم کرنے کے لیے ڈیزائن کیے گئے ہیں۔ ایسی مثالیں جہاں برے اداکار ہیش تصادم پیدا کرنے یا تلاش کرنے کی کوشش کرتے ہیں انہیں تصادم کے حملے کہا جاتا ہے۔ عملی طور پر، سیکیورٹی سے متعلق ایپلی کیشنز کرپٹوگرافک ہیش الگورتھم کا استعمال کرتی ہیں، جو اس طرح ڈیزائن کیے گئے ہیں کہ بے ترتیب میچوں کا امکان کافی لمبا ہو، اتنا تیز ہو کہ انہیں کہیں بھی استعمال کیا جا سکے، اور اتنا محفوظ ہو کہ تصادم تلاش کرنا انتہائی مشکل ہو۔ ہیش کے تصادم کا امکان اتفاق سے ہو سکتا ہے اور بہت سے ہیش الگورتھم کے لیے جان بوجھ کر بنایا جا سکتا ہے۔ اس طرح ہیش تصادم کا امکان الگورتھم کے سائز، ہیش اقدار کی تقسیم، اور یہ کہ آیا یہ ریاضیاتی طور پر جانا جاتا ہے اور مخصوص تصادم پیدا کرنے کے لیے کمپیوٹیشنل طور پر قابل عمل ہے یا نہیں، پر منحصر ہے۔ مندرجہ ذیل ہیش الگورتھم-سی آر سی-32، ایم ڈی 5، اور ایس ایچ اے-1 کو مدنظر رکھیں۔ یہ عام ہیش الگورتھم ہیں جن میں تصادم کے خطرے کی مختلف سطحیں ہیں۔ سی آر سی-32 سی آر سی-32 ہیش تصادم کا سب سے زیادہ خطرہ ہے۔ یہ ہیش فنکشن عام طور پر استعمال کے لیے تجویز نہیں کیا جاتا ہے۔ اگر کسی ہب میں 77,163 ہیش ویلیوز ہوں، تو ہیش ٹکرانے کا امکان 50 فیصد ہے، جو دوسرے طریقوں کے مقابلے میں انتہائی زیادہ ہے۔ ایم ڈی 5 ایم ڈی 5 سب سے زیادہ استعمال ہوتا ہے اور جب دوسرے دو ہیش افعال کے مقابلے میں، یہ ہیش تصادم کے خطرے کے لحاظ سے درمیانی زمین کی نمائندگی کرتا ہے۔ ہیش ٹکرانے کا 50 فیصد امکان حاصل کرنے کے لیے، مرکز میں 5.06 ارب سے زیادہ ریکارڈ ہونے چاہئیں۔ ایس ایچ اے-1 ایس ایچ اے-1 ہیش تصادم کا سب سے کم خطرہ پیش کرتا ہے۔ ایس ایچ اے-1 فنکشن کے لیے کہ ہیش ٹکرانے کا 50 فیصد امکان ہو، مرکز میں 1.42x10 ریکارڈز ہونے چاہئیں۔ نوٹ کریں، ان مثالوں میں مذکور ریکارڈوں کی تعداد ایک ہی مرکز میں ہونی چاہیے۔ کم تعداد میں ریکارڈ کے ساتھ مرکز ہونے سے ان تمام ہیش افعال میں ہیش تصادم کے امکان کو کم کیا جا سکتا ہے، حالانکہ ہمیشہ ایک معمولی خطرہ موجود رہے گا، جو کہ ناگزیر ہے، جب تک کہ تصادم کے حل کی تکنیک کا استعمال نہ کیا جائے۔ تصادم کا حل چونکہ ہیش کے تصادم ناگزیر ہوتے ہیں، اس لیے ہیش ٹیبل میں ان سے نمٹنے کا طریقہ کار ہوتا ہے، جسے تصادم کے حل کے نام سے جانا جاتا ہے۔ دو سب سے عام حکمت عملی کھلی ایڈریسنگ اور علیحدہ چیننگ ہیں۔ کیش سے آگاہ تصادم کا حل ایک اور حکمت عملی ہے جس پر ماضی میں سٹرنگ ہیش ٹیبلز کے لیے تبادلہ خیال کیا گیا ہے۔ ہیش ٹیبل میں کھلے ایڈریسنگ سیل کو اس طریقہ کار میں تین میں سے ایک حالت تفویض کی جاتی ہے-قبضہ شدہ، خالی، یا حذف شدہ۔ اگر ہیش تصادم ہوتا ہے، تو ریکارڈ کو ایک متبادل سیل میں منتقل کرنے کے لیے ٹیبل کی جانچ کی جائے گی جسے خالی بتایا گیا ہے۔ تحقیقات کی مختلف قسمیں ہیں جو اس وقت ہوتی ہیں جب ہیش تصادم ہوتا ہے اور اس طریقہ کو نافذ کیا جاتا ہے۔ جانچ کی کچھ اقسام لکیری جانچ، ڈبل ہیشنگ، اور کواڈریٹک تحقیقات ہیں۔ اوپن ایڈریسنگ کو کلوزڈ ہیشنگ بھی کہا جاتا ہے۔ علیحدہ زنجیر بندی یہ حکمت عملی ایک سے زیادہ ریکارڈ کو ہیش ٹیبل کے خلیوں میں "زنجیر بند" کرنے کی اجازت دیتی ہے۔ اگر دو ریکارڈز کو ایک ہی سیل میں بھیجا جا رہا ہے، تو دونوں ایک منسلک فہرست کے طور پر اس سیل میں جائیں گے۔ یہ مؤثر طریقے سے ہیش تصادم کو ہونے سے روکتا ہے کیونکہ ایک ہی ہیش ویلیو والے ریکارڈ ایک ہی سیل میں جا سکتے ہیں، لیکن اس کے نقصانات ہیں۔ بہت سی فہرستوں کا سراغ لگانا مشکل ہے اور جو بھی ٹول استعمال کیا جا رہا ہے وہ بہت سست ہو سکتا ہے۔ علیحدہ چیننگ کو اوپن ہیشنگ بھی کہا جاتا ہے۔ اگرچہ پچھلے دو کے مقابلے میں بہت کم استعمال کیا گیا ہے، اس نے 2005 میں کیش سے آگاہ تصادم کے حل کا طریقہ تجویز کیا ہے۔ یہ علیحدہ زنجیروں کے طریقوں سے ملتا جلتا خیال ہے، حالانکہ اس میں تکنیکی طور پر زنجیروں والی فہرستیں شامل نہیں ہیں۔ اس صورت میں، جکڑی ہوئی فہرستوں کے بجائے، ہیش ویلیوز کو آئٹمز کی ملحقہ فہرست میں دکھایا جاتا ہے۔ یہ سٹرنگ ہیش ٹیبلز کے لیے بہتر موزوں ہے اور عددی اقدار کا استعمال ابھی تک نامعلوم ہے۔ یہ بھی دیکھیں ہیش فنکشن کی فہرست حوالہ جات بیرونی لنکس ہیشنگ