Double hashing
ڈبل ہیشنگ ایک کمپیوٹر پروگرامنگ تکنیک ہے جو ہیش ٹیبلز میں اوپن ایڈریسنگ کے ساتھ مل کر ہیش کے تصادم کو حل کرنے کے لیے استعمال ہوتی ہے، جب تصادم ہوتا ہے تو کلید کے ثانوی ہیش کو آفسیٹ کے طور پر استعمال کیا جاتا ہے۔ اوپن ایڈریسنگ کے ساتھ ڈبل ہیشنگ ایک میز پر کلاسیکی ڈیٹا ڈھانچہ ہے۔ ڈبل ہیشنگ تکنیک ایک ہیش ویلیو کو ٹیبل میں انڈیکس کے طور پر استعمال کرتی ہے اور پھر بار بار ایک وقفہ آگے بڑھاتی ہے جب تک کہ مطلوبہ قیمت موجود نہ ہو، ایک خالی مقام تک پہنچ جائے، یا پوری ٹیبل کو تلاش کیا جائے ؛ لیکن یہ وقفہ دوسرے، آزاد ہیش فنکشن کے ذریعہ مقرر کیا جاتا ہے۔ لکیری پروبنگ اور کواڈریٹک پروبنگ کے تصادم کے حل کے متبادل طریقوں کے برعکس، وقفہ ڈیٹا پر منحصر ہوتا ہے، تاکہ ایک ہی مقام پر نقشہ سازی کی اقدار میں بالٹی کے مختلف سلسلے ہوں۔ اس سے بار بار تصادم اور کلسٹرنگ کے اثرات کو کم سے کم کیا جاتا ہے۔ دو بے ترتیب، یکساں، اور آزاد ہیش افعال کو دیکھتے ہوئے اور بالٹیوں کی ہیش ٹیبل میں قدر کے لیے بالٹی کی ترتیب میں واں مقام یہ ہے: عام طور پر، اور یونیورسل ہیش افعال کے ایک سیٹ سے منتخب کیا جاتا ہے۔ ڈبل ہیشنگ بے ترتیب تقسیم کا تخمینہ لگاتا ہے۔ زیادہ واضح طور پر، جوڑی کے لحاظ سے آزاد ہیش افعال اس بات کا امکان پیدا کرتے ہیں کہ چابیاں کا کوئی بھی جوڑا ایک ہی بالٹی ترتیب کی پیروی کرے گا۔ ایچ 2 (کے) کا انتخاب ثانوی ہیش فنکشن میں کئی خصوصیات ہونی چاہئیں: اسے کبھی بھی صفر کا انڈیکس نہیں دینا چاہیے۔ اسے پورے ٹیبل میں چکر لگانا چاہیے۔ اس کا حساب لگانا بہت تیز ہونا چاہیے جوڑی کے لحاظ سے آزاد ہونا چاہیے۔ کی تقسیم کی خصوصیات غیر متعلقہ ہیں۔ یہ بے ترتیب نمبر والے جنریٹر کے مترادف ہے۔ سبھی |T | کے لیے نسبتا پرائم ہوں گے۔ عملی طور پر: اگر ڈویژن ہیشنگ کو دونوں افعال کے لیے استعمال کیا جاتا ہے، تو تقسیم کاروں کو پرائم کے طور پر منتخب کیا جاتا ہے۔ اگر T 2 کی طاقت ہے، تو عام طور پر پہلی اور آخری ضروریات کو ہمیشہ ایک عجیب نمبر واپس کرکے پورا کیا جاتا ہے۔ اس کا ضمنی اثر یہ ہے کہ ایک بٹ ضائع ہونے کی وجہ سے ٹکرانے کا امکان دوگنا ہو جاتا ہے۔ تجزیہ اس میں ذخیرہ شدہ عناصر کی تعداد ہونے دیں، پھر اس کا لوڈ فیکٹر ہے۔ یعنی بے ترتیب، یکساں اور آزادانہ طور پر دو عالمگیر ہیش افعال کو منتخب کرکے اور ڈبل ہیشنگ ٹیبل بنا کر شروع کریں۔ تمام عناصر کو اور کا استعمال کرتے ہوئے ڈبل ہیشنگ کے ذریعے ڈالا جاتا ہے۔ ایک کلید کو دیکھتے ہوئے،-1st ہیش لوکیشن کا حساب اس طرح لگایا جاتا ہے: آئیے فکسڈ لوڈ فیکٹر رکھیں۔ بریڈفورڈ اور کتےہاکس نے ناکام تلاش کے لیے تحقیقات کی متوقع تعداد دکھائی، پھر بھی ان ابتدائی طور پر منتخب کردہ ہیش افعال کا استعمال کرتے ہوئے، ان پٹ کی تقسیم سے قطع نظر ہے۔ ہیش افعال کی جوڑی کے لحاظ سے آزادی کافی ہے۔ اوپن ایڈریسنگ کی دیگر تمام شکلوں کی طرح، ڈبل ہیشنگ لکیری ہو جاتی ہے کیونکہ ہیش ٹیبل زیادہ سے زیادہ صلاحیت تک پہنچ جاتا ہے۔ ٹیبل کی لوڈنگ کو صلاحیت کے 75 فیصد تک محدود کرنا معمول کی تحقیق ہے۔ آخر کار، دوسرے تمام اوپن ایڈریسنگ اسکیموں کی طرح، بڑے سائز میں ری ہیشنگ ضروری ہوگی۔ متغیرات پیٹر ڈلنگر کا پی ایچ ڈی مقالہ بتاتا ہے کہ ڈبل ہیشنگ ناپسندیدہ مساوی ہیش افعال پیدا کرتی ہے جب ہیش افعال کو ایک سیٹ کے طور پر سمجھا جاتا ہے، جیسا کہ بلوم فلٹرز میں: اگر اور، پھر اور ہیش کے سیٹ ایک جیسے ہوتے ہیں۔ اس سے تصادم کا امکان متوقع سے دوگنا ہو جاتا ہے۔ اس کے علاوہ زیادہ تر اوور لیپنگ ہیش سیٹس کی ایک قابل ذکر تعداد موجود ہے۔ اگر اور پھر، اور اضافی ہیش ویلیوز کا موازنہ کرنا (کی حد کو بڑھانا) کوئی فائدہ نہیں ہے۔ ٹرپل ہیشنگ ہیش فنکشن میں کواڈریٹک ٹرم (ایک مثلث نمبر) یا یہاں تک کہ (ٹرپل ہیشنگ) شامل کرنے سے ہیش فنکشن میں کچھ بہتری آتی ہے لیکن یہ مسئلہ حل نہیں ہوتا ہے۔ اگر: اور پھر بہتر ڈبل ہیشنگ کیوبک ٹرم یا (ایک ٹیٹراہیڈرل نمبر) شامل کرنے سے مسئلہ حل ہوتا ہے، ایک تکنیک جسے بہتر ڈبل ہیشنگ کہا جاتا ہے۔ اس کا حساب فارورڈ تفریق کے ذریعے مؤثر طریقے سے کیا جا سکتا ہے: اسٹرک کلید ؛// اوپیک// ضرورت پڑنے پر ڈیٹا کی دیگر اقسام کا استعمال کریں۔ (ضمانت شدہ ریپنگ کے لیے غیر دستخط شدہ ہونا ضروری ہے۔) بیرونی غیر دستخط شدہ انٹیٹ ایچ 1 (اسٹرکچ کلیدی کانسٹ *)، ایچ 2 (اسٹرکچ کلیدی کانسٹ *) ؛// بہتر ڈبل ہیشنگ کا استعمال کرتے ہوئے دو بنیادی ہیش افعال// ایچ 1 () اور ایچ 2 () سے کے ہیش ویلیوز کا حساب لگائیں۔ واپسی پر،// ہیش [i] = h1 (x) + i * h2 (x) + (i * i * i-i)/6 ہوتا ہے۔ /// سی میں خودکار ریپنگ (ماڈیولر کمی)// غیر دستخط شدہ اقسام کا فائدہ اٹھاتا ہے۔ وایڈ ایکسٹ ڈی بی ایل ہیش (اسٹرک کلیدی کانسٹ * ایکس، غیر دستخط شدہ انٹ ہیش []، غیر دستخط شدہ انٹ این) {غیر دستخط شدہ انٹ اے = ایچ 1 (ایکس)، بی = ایچ 2 (ایکس)، آئی ؛ (آئی = 0 ؛ آئی <این ؛ آئی + +) [ہیش [آئی] = اے ؛ اے + = بی ؛/کیوبک بی + = آئی حاصل کرنے کے لیے کواڈریٹک فرق شامل کریں ؛// کواڈریٹک حاصل کرنے کے لیے لکیری فرق شامل کریں// آئی + + لکیری حاصل کرنے کے لیے مستقل فرق کا اضافہ کرتا ہے۔ کوکل ہیشنگ 2-چوائس ہیشنگ حوالہ جات بیرونی لنکس کیسے کیچنگ ہیشنگ کو متاثر کرتی ہے بذریعہ گریگوری ایل ہیلمین اور وینبن لوو 2005 بھی دیکھیں۔ ہیش ٹیبل اینیمیشن کلب اے سی لائبریری جس میں ڈبل ہیشنگ فعالیت شامل ہے۔ ہیشنگ الگورتھم تلاش کریں