ہیش فنکشن
اس سیکشن میں، ہم ہیش فنکشن کے بارے میں بات کریں گے جو ڈیٹا سٹرکچر میں ڈیٹا آئٹم کی متعلقہ کلید کے ہیش کوڈ کو عمل میں لانے میں مدد کرتا ہے جیسا کہ درج ذیل میں بتایا گیا ہے۔
انٹ ہیش آئٹم ( int چابی ){
واپسی چابی % ٹیبل سائز ;
}
ایک صف کے اشاریہ پر عمل کرنے کے عمل کو ہیشنگ کہا جاتا ہے۔ بعض اوقات، ایک ہی قسم کے کوڈ کو ایک ہی کیز کا استعمال کرتے ہوئے ایک ہی انڈیکس بنانے کے لیے عمل میں لایا جاتا ہے جسے collisions کہا جاتا ہے جسے مختلف چیننگ (لنک لسٹ تخلیق) اور اوپن ایڈریسنگ اسٹریٹجیز کے نفاذ کے ذریعے سنبھالا جاتا ہے۔
C++ میں ہیش ٹیبل کا کام کرنا
اصلی اقدار کی طرف اشارہ ہیش ٹیبل میں رکھا گیا ہے۔ یہ ایک سرنی کے اشاریہ کو تلاش کرنے کے لیے ایک کلید کا استعمال کرتا ہے جس پر کلیدوں کے خلاف اقدار کو ایک صف میں مطلوبہ مقام پر ذخیرہ کرنے کی ضرورت ہوتی ہے۔ ہم نے ہیش ٹیبل لیا جس کا سائز 10 ہے جیسا کہ درج ذیل میں بتایا گیا ہے۔
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
آئیے تصادفی طور پر مختلف کیز کے خلاف کوئی بھی ڈیٹا لیں اور ان کیز کو صرف انڈیکس کا حساب لگا کر ہیش ٹیبل میں محفوظ کریں۔ لہذا، ڈیٹا کو ہیش فنکشن کی مدد سے کیلکولیٹڈ انڈیکس میں کیز کے خلاف محفوظ کیا جاتا ہے۔ فرض کریں کہ ہم ڈیٹا = {14,25,42,55,63,84} اور کیز = [ 15,9,5,25,66,75] لیتے ہیں۔
ہیش فنکشن کا استعمال کرتے ہوئے ان ڈیٹا کے انڈیکس کا حساب لگائیں۔ انڈیکس کی قیمت درج ذیل میں بیان کی گئی ہے۔
| چابی | پندرہ | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| انڈیکس کا حساب لگائیں۔ | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| ڈیٹا | 14 | 25 | 42 | 55 | 63 | 84 |
ایک صف کا انڈیکس بنانے کے بعد، ڈیٹا کو کلید کے خلاف کسی دیے گئے ارے کے عین انڈیکس پر رکھیں جیسا کہ پہلے بیان کیا گیا ہے۔
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
اس کے بعد، ہم دیکھ سکتے ہیں کہ تصادم ہوتا ہے اگر دو یا دو سے زیادہ کیز میں ایک ہیش کوڈ ہو جس کے نتیجے میں صف میں موجود عناصر کا ایک ہی انڈیکس ہوتا ہے۔ تصادم کے امکانات سے بچنے کے لیے ہمارے پاس ایک حل ہے: ہیش کا ایک اچھا طریقہ منتخب کرنا اور درست حکمت عملیوں کو نافذ کرنا۔
اب، آئیے مناسب مثالوں کی مدد سے نفاذ کی مختلف تکنیکوں پر بات کرتے ہیں۔
مثال: اوپن ہیشنگ تکنیک کا استعمال کرتے ہوئے ہیش ٹیبل میں ڈیٹا شامل کریں۔
اس مثال میں، ہم ہیش ٹیبل میں تصادم سے بچنے کے لیے اوپن ہیشنگ جیسی نفاذ کی تکنیک لیتے ہیں۔ کھلی ہیشنگ یا چیننگ میں، ہم ہیش ٹیبل کی اقدار کو زنجیر بنانے کے لیے ایک منسلک فہرست بناتے ہیں۔ اس مثال کا کوڈ کا ٹکڑا درج ذیل میں منسلک ہے جو کھلی ہیشنگ تکنیک کو بیان کرتا ہے:
# شامل کریں# شامل کریں
کلاس ہیش ٹیبل {
نجی :
جامد const int میز کا سائز = 10 ;
std :: فہرست < int > ٹیبل ہے [ میز کا سائز ] ;
int hashFunc ( int چابی ) {
واپسی چابی % میز کا سائز ;
}
عوام :
باطل داخل کریں ( int چابی ) {
int انڈیکس = hashFunc ( چابی ) ;
میز ہے [ انڈیکس ] . پیچھے دھکیلا ( چابی ) ;
}
باطل ویو ٹیبل ( ) {
کے لیے ( int میں = 0 ; میں < میز کا سائز ; ++ میں ) {
std :: cout << '[' << میں << ']' ;
کے لیے ( آٹو یہ = ٹیبل ہے [ میں ] . شروع ( ) ; یہ ! = ٹیبل ہے [ میں ] . اختتام ( ) ; ++ یہ ) {
std :: cout << '->' << * یہ ;
}
std :: cout << std :: endl ;
}
}
} ;
int مرکزی ( ) {
ہیش ٹیبل ہے ٹیبل ;
ہے ٹیبل داخل کریں ( پندرہ ) ;
ہے ٹیبل داخل کریں ( 33 ) ;
ہے ٹیبل داخل کریں ( 23 ) ;
ہے ٹیبل داخل کریں ( 65 ) ;
ہے ٹیبل داخل کریں ( 3 ) ;
ہے ٹیبل ویو ٹیبل ( ) ;
واپسی 0 ;
}
یہ ایک بہت ہی دلچسپ مثال ہے: ہم ایک منسلک فہرست بناتے ہیں اور ڈیٹا کو ہیش ٹیبل میں داخل کرتے ہیں۔ سب سے پہلے، ہم پروگرام کے آغاز میں لائبریریوں کی تعریف کرتے ہیں۔ دی < فہرست > لائبریری کو منسلک فہرست کے نفاذ کے لیے استعمال کیا جاتا ہے۔ اس کے بعد، ہم 'ہیش ٹیبل' کے نام سے ایک کلاس بناتے ہیں اور 'پرائیویٹ:' کلیدی لفظ کا استعمال کرتے ہوئے کلاس کی صفات تخلیق کرتے ہیں جو کہ ٹیبل سائز اور ٹیبل ارے کے طور پر نجی ہیں۔ یاد رکھیں کہ نجی صفات کلاس سے باہر قابل استعمال نہیں ہیں۔ یہاں، ہم میز کے سائز کو '10' کے طور پر لیتے ہیں۔ ہم اسے استعمال کرتے ہوئے ہیش کا طریقہ شروع کرتے ہیں اور ہیش ٹیبل کے انڈیکس کا حساب لگاتے ہیں۔ ہیش فنکشن میں، ہم ہیش ٹیبل کی کلید اور سائز کو پاس کرتے ہیں۔
ہم چند مطلوبہ فنکشنز بناتے ہیں اور ان فنکشنز کو کلاس میں پبلک کرتے ہیں۔ یاد رکھیں کہ پبلک فنکشنز کلاس کے باہر کہیں بھی قابل استعمال ہیں۔ ہم کلاس کے عوامی حصے کو شروع کرنے کے لیے 'عوامی:' کلیدی لفظ استعمال کرتے ہیں۔ . چونکہ ہم ہیش ٹیبل میں نئے عناصر شامل کرنا چاہتے ہیں، اس لیے ہم فنکشن کی دلیل کے طور پر ایک کلید کے ساتھ 'InsertHash' نام کا فنکشن بناتے ہیں۔ 'insert' فنکشن میں، ہم انڈیکس متغیر کو شروع کرتے ہیں۔ ہم ہیش فنکشن کو انڈیکس متغیر میں منتقل کرتے ہیں۔ اس کے بعد، ٹیبل میں عنصر داخل کرنے کے لیے 'دھکا' طریقہ استعمال کرتے ہوئے انڈیکس متغیر کو منسلک فہرست ٹیبل پر منتقل کریں۔
اس کے بعد، ہم نئے داخل کردہ ڈیٹا کو دیکھنے کے لیے ہیش ٹیبل کو ظاہر کرنے کے لیے ایک 'viewHashTab' فنکشن بناتے ہیں۔ اس فنکشن میں، ہم ایک 'for' لوپ لیتے ہیں جو ہیش ٹیبل کے اختتام تک ویلیوز کو تلاش کرتا ہے۔ اس بات کو یقینی بنائیں کہ اقدار اسی انڈیکس میں محفوظ ہیں جو ہیش فنکشن کا استعمال کرتے ہوئے تیار کی گئی ہیں۔ لوپ میں، ہم اقدار کو ان کے متعلقہ انڈیکس سے پاس کرتے ہیں اور کلاس کو یہاں ختم کرتے ہیں۔ 'مین' فنکشن میں، ہم 'ہاس ٹیبل' نامی کلاس کا آبجیکٹ لیتے ہیں۔ اس کلاس آبجیکٹ کی مدد سے، ہم طریقہ میں کلید کو پاس کر کے اندراج کے طریقہ تک رسائی حاصل کر سکتے ہیں۔ جو کلید ہم نے 'مین' فنکشن میں پاس کی ہے اس کا حساب 'insert' فنکشن میں کیا جاتا ہے جو ہیش ٹیبل میں انڈیکس پوزیشن کو لوٹاتا ہے۔ ہم نے 'کلاس' آبجیکٹ کی مدد سے 'ویو' فنکشن کو کال کرکے ہیش ٹیبل کو ڈسپلے کیا۔
اس کوڈ کا آؤٹ پٹ درج ذیل میں منسلک ہے:
جیسا کہ ہم دیکھ سکتے ہیں، ہیش ٹیبل کو C++ میں لنک شدہ فہرست کا استعمال کرتے ہوئے کامیابی سے بنایا گیا ہے۔ ایک ہی انڈیکس کے تصادم سے بچنے کے لیے اوپن چیننگ کا استعمال کیا جاتا ہے۔
نتیجہ
بالآخر، ہم نے یہ نتیجہ اخذ کیا کہ ہیش ٹیبل بڑی مقدار میں ڈیٹا کو موثر طریقے سے سنبھالنے کے لیے ویلیو پیئرز کے ساتھ کیز کو ذخیرہ کرنے اور حاصل کرنے کی سب سے ابھرتی ہوئی تکنیک ہے۔ ہیش ٹیبل میں تصادم کے امکانات بہت زیادہ ہیں، جس سے ڈیٹا اور اس کا ذخیرہ تباہ ہو جاتا ہے۔ ہم ہیش ٹیبل مینجمنٹ کی مختلف تکنیکوں کا استعمال کرتے ہوئے اس تصادم پر قابو پا سکتے ہیں۔ C++ میں ہیش ٹیبل تیار کرکے، ڈویلپرز ہیش ٹیبل میں ڈیٹا کو ذخیرہ کرنے کے لیے بہترین موزوں تکنیک کا استعمال کرتے ہوئے کارکردگی کو بڑھا سکتے ہیں۔ ہم امید کرتے ہیں کہ یہ مضمون آپ کو ہیش ٹیبل کو سمجھنے کے لیے مددگار ثابت ہوگا۔