[موسیقی بجانے] ڈوگ لایڈ: اب تک آپ arrays کے بارے میں ایک بہت کچھ جانتے ہیں، اور آپ کو منسلک کی فہرست کے بارے میں ایک بہت کچھ جانتے ہیں. اور ہم کے بارے میں بات ہے پیشہ اور cons، ہم نے فہرستوں منسلک ہے کہ بات چیت کی بڑے اور چھوٹے حاصل کر سکتے ہیں، لیکن وہ زیادہ سائز تک کا وقت لگ. لڑیوں زیادہ براہ راست ہیں استعمال، لیکن وہ زیادہ سے زیادہ میں پابندیوں ہیں ہم کا سائز مقرر کرنے کے لئے ہے کے طور پر بہت شروع میں سرنی اور پھر ہم اس کے ساتھ پھنس گئے ہیں. 

لیکن ہے کہ ہم بہت زیادہ ہے، ہے ہمارے موضوعات کے تمام ختم منسلک کی فہرست اور arrays کے بارے میں. یا ہم ہیں؟ شاید ہم کچھ کر سکتے ہیں بھی زیادہ تخلیقی. اور ڈھال لیتا ہے اس طرح ایک ہیش ٹیبل کے خیال. 

تو ایک ہیش ٹیبل میں ہم کوشش کرنے جا رہے ہیں ایک لنک کی فہرست کے ساتھ ایک صف جمع. ہم فوائد لے جا رہے ہیں صف کے، رینڈم رسائی کی طرح، صرف صف میں جانے کے لئے کے قابل ہونے کی وجہ سے عنصر 4 یا سرنی عنصر 8 بھر iterate کرنے کے لئے بغیر. یہ ٹھیک ہے، بہت تیز ہے؟ 

لیکن ہم یہ بھی ہمارے اعداد و شمار حاصل کرنے کے لئے چاہتے ہیں ساخت بڑھنے اور سکڑ کرنے کے قابل ہو. ہم ایسا نہیں کرتے، کی ضرورت نہیں ہے محدود کرنا چاہتے ہیں. اور ہم قابل بننا چاہتا ہوں شامل کریں اور چیزوں کو دور کرنے بہت آسانی سے، جس سے آپ کو یاد تو، ایک سرنی کے ساتھ بہت پیچیدہ ہے. اور ہم نے اس کال کر سکتے ہیں نئی چیز ایک ہیش کی میز. 

اور اگر، صحیح طریقے سے نافذ ہم قسم کی لے جا رہے ہیں دونوں کے اعداد و شمار کے فوائد آپ نے پہلے ہی دیکھا ہے ڈھانچے، arrays اور منسلک فہرستوں. اندراج کے لئے شروع کر سکتے ہیں 1 تھیٹا کی طرف ہوتے ہیں. تھیٹا ہم واقعی بات چیت نہیں ہے، لیکن تھیٹا صرف اوسط معاملہ ہے، کیا اصل میں ہونے جا رہا ہے. تم ہمیشہ کے لئے نہیں جا رہے ہیں بدترین صورت ہے، اور آپ کو ہمیشہ کے لئے نہیں جا رہے ہیں بہترین دوسری صورت، تو کیا ہے اوسط منظر نامے؟ 

ویسے اوسط اندراج ایک ہیش ٹیبل میں بند مسلسل وقت حاصل کرنے کے لئے شروع کر سکتے ہیں. اور منسوخی حاصل کر سکتے ہیں مسلسل وقت کے قریب. اور تلاش حاصل کر سکتے ہیں مسلسل وقت کے قریب. That's-- ہم ایک ڈیٹا نہیں ہے ساخت تک کہ کر سکتے ہیں، اور تو اس کو پہلے ہی آواز ایک بہت عظیم چیز کی طرح. ہم واقعی کم ہے اپنے طور پر ہر کے نقصانات. 

اس کی کارکردگی حاصل کرنے کے لئے ، اگرچہ ہم اپ گریڈ ہم شامل ہیں کہ کس طرح پر نظر ثانی کرنے کی ضرورت ہے ڈھانچے میں اعداد و شمار. خاص طور پر ہم چاہتے ہیں ڈیٹا خود ہمیں بتانا جہاں اس کی ساخت میں جانا چاہئے. اور پھر ہم اس میں ہے تو دیکھنے کے لئے کی ضرورت ہے تو ساخت، ہم اسے تلاش کرنے کی ضرورت ہے، ہم اعداد و شمار کو دیکھنے کے لئے چاہتے ہیں پھر اور مؤثر طریقے سے کرنے کے قابل ہو، ڈیٹا کا استعمال کرتے ہوئے، تصادفی اس تک رسائی حاصل. بس دیکھ کر اعداد و شمار ہم ہونا چاہئے بالکل ہم ہیں جہاں ایک خیال ہیش ٹیبل میں اس کو تلاش کرنے کے لئے جا. 

ایک ہیش اب کمی ٹیبل وہ واقعی ہیں یہ ہے کہ حکم یا ڈیٹا چھانٹ رہا ہے پر بہت برا. اور حقیقت میں، آپ شروع تو حکم یا قسم پر ان کا استعمال کرنے کے لئے اعداد و شمار آپ کی تمام کھو فوائد پہلے آپ اندراج اور منسوخی کی شرائط میں تھا. وقت کے قریب ہو جاتا ہے (ن) کے تھیٹا، اور ہم نے بنیادی ہے ایک لنک کی فہرست میں پیچھے. اور اس طرح ہم صرف ہیش استعمال کرنا چاہتے ہیں میزیں ہم کے بارے میں پرواہ نہیں ہے تو ڈیٹا کے مطابق ہے یا نہیں. سیاق و سباق ہے جس میں آپ CS50 میں ان کا استعمال کریں گے آپ کو شاید کوئی پرواہ نہیں ڈیٹا کے مطابق ہے کہ. 

تو ایک ہیش ٹیبل کا ایک مجموعہ ہے دو الگ الگ ٹکڑوں میں جس کے ساتھ ہم واقف ہیں. سب سے پہلے ایک تقریب، ہے جو ہم عام طور پر ایک ہیش تقریب کہتے ہیں. اور یہ کہ ہیش تقریب کی جا رہی ہے ، کچھ غیر منفی صحیح عدد واپس جس ہم عام طور پر ٹھیک ہے، ایک hashcode کہتے ہیں؟ دوسرا ٹکڑا ہے جس میں ایک صف ہے، قسم ہم ذخیرہ کرنے کے اعداد و شمار کرنے کے قابل آنکڑا ڈھانچہ میں رکھنے کے لئے چاہتے. ہم پر دور منعقد کریں گے اب کے لئے فہرست عنصر منسلک اور صرف ایک کی مبادیات کے ساتھ شروع اس کے ارد گرد اپنے سر حاصل کرنے کے لئے میز ہیش، اور پھر ہم شاید اڑا دونگا آپ کے دماغ تھوڑا سا جب ہم ایک دوسرے کے ساتھ arrays اور لنک فہرستوں یکجا. 

بنیادی خیال اگرچہ ہم نے کچھ اعداد و شمار لے ہے. ہم نے اس کے اعداد و شمار کے ذریعے چلانے کے ہیش تقریب. اور اس طرح کے اعداد و شمار عملدرآمد کیا جاتا ہے اور یہ ٹھیک، ایک بڑی تعداد باہر spits؟ اور پھر اس کی تعداد کے ساتھ ہم صرف ڈیٹا ذخیرہ ہم میں محفوظ کرنا چاہتے ہیں اس مقام پر سرنی. لہذا مثال کے طور ہم شاید ہے ڈور کے اس ہیش ٹیبل. یہ اتنا، اس میں 10 عناصر ہے ہم اس میں 10 ڈور فٹ کر سکتے ہیں. 

ہم جان ہیش کرنا چاہتے ہیں کا کہنا ہے کہ. جان تو ڈیٹا کے طور پر ہم داخل کرنا چاہتے ہیں کہیں اس ہیش ٹیبل میں. ہم اسے کہاں رکھ سکتے ہیں؟ ویسے عام طور پر کے ساتھ ایک صف اب تک ہم شاید صف 0 مقام میں ڈال دیں گے. لیکن اب ہم اس نئے ہیش تقریب ہے. 

اور ہم جان چلانے کہنا ہے کہ دو اس ہیش تقریب کے ذریعے اور اس کے 4 باہر spits ہے. ہم ہیں جہاں ٹھیک ہے کہ ہے جان ڈال کرنا چاہتے ہیں کے لئے جا رہے. ہم صف جگہ میں جان ڈال کرنا چاہتے ہیں 4، ہم again-- جان ہیش کیونکہ اگر کی بعد ہم کا کہنا ہے کہ تلاش اور کو دیکھنے کے لئے چاہتے ہیں یوحنا نے اس ہیش میں موجود ہے ہم کیا کرنے کی ضرورت ہے تمام table-- اسی ہیش کے ذریعے چلایا جاتا ہے تقریب،، نمبر 4 سے باہر حاصل اور یوحنا کو تلاش کرنے کے قابل ہو جائے فوری طور پر ہمارے آنکڑا ڈھانچہ میں. یہ بہت اچھی بات ہے. 

ہم اب ایسا کہنے دو ایک بار پھر، ہم نے پال ہیش کرنا چاہتے ہیں. ہم نے پال شامل کرنا چاہتے ہیں اس ہیش ٹیبل میں. اس وقت ہم چلاتے کا کہنا ہے کہ ہیش تقریب کے ذریعے پال، پیدا کیا جاتا ہے کہ hashcode 6. ٹھیک ہے اب ہم نے پال ڈال کر سکتے ہیں سرنی مقام 6. اور ہم چاہے تلاش کرنے کے لئے کی ضرورت ہے تو پال اس ہیش ٹیبل میں ہے، ہم کیا کرنے کی ضرورت ہے تمام پال چلایا جاتا ہے ہیش تقریب ذریعے ایک بار پھر اور ہم پھر سے باہر 6 حاصل کرنے جا رہے ہیں. 

اور پھر ہم صرف نظر سرنی مقام 6. پال ہے؟ اگر ایسا ہے تو، وہ ہیش ٹیبل میں ہے. پال نہیں ہے؟ انہوں نے کہا کہ ہیش ٹیبل میں نہیں ہے. یہ بہت سیدھا ہے. 

اب آپ کو ایک ہیش تقریب کی وضاحت کرتے ہیں؟ اچھی طرح سے واقعی کوئی حد نہیں ہے ممکن ہیش افعال کی تعداد. اصل میں کی ایک بڑی تعداد، وہاں واقعی ہے انٹرنیٹ پر بہت اچھا ہیں. کی ایک بڑی تعداد، وہاں واقعی ہے انٹرنیٹ پر بہت برے لوگ. یہ بھی بہت آسان ہے ایک برا ایک لکھنے کے لئے. 

تو کیا ایک اچھا بناتا ہے ہیش تقریب، ٹھیک ہے؟ ایک اچھا ہیش تقریب ہونا چاہئے صرف اعداد و شمار سے hashed جا استعمال، اور اعداد و شمار کے تمام سے hashed جا رہا. تو ہم anything-- استعمال کرنا چاہتے ہیں نہیں ہے ہم کچھ شامل نہیں ہے ڈیٹا کے علاوہ اور. اور ہم نے اعداد و شمار کے تمام استعمال کرنا چاہتے ہیں. ہم صرف ایک ٹکڑا استعمال کرنے کے لئے نہیں کرنا چاہتے اس کے، ہم اس کا استعمال کرنا چاہتے ہیں. ایک ہیش تقریب ہونا چاہئے بھی نیتاتمک ہونا. اس کا کیا مطلب ہے؟ ویسے اس کا مطلب یہ ہے کہ ہر وقت ہم اعداد و شمار کے عین مطابق ایک ہی ٹکڑے کو منتقل ہیش تقریب میں ہم ہمیشہ اسی hashcode باہر حاصل. میں میں جان پاس کرجاتے ہیں تو ہیش تقریب میں 4 باہر حاصل. مجھے لگتا ہے کہ ایسا کرنے کے قابل ہونا چاہئے 10،000 بار اور میں نے ہمیشہ 4 ملے گی. تو کوئی بے ترتیب تعداد مؤثر طریقے سے ہماری ہیش میں شامل کیا جا سکتا tables-- ہماری ہیش افعال میں. 

ایک ہیش تقریب میں بھی ہونا چاہئے یکساں ڈیٹا کی تقسیم. ہر وقت آپ کے ذریعے ڈیٹا چلاتے ہیں ہیش تقریب میں آپ کو، hashcode 0 حاصل یہ ٹھیک ہے، شاید اتنا اچھا نہیں ہے؟ آپ نے شاید بڑا کرنا چاہتے ہیں ہیش کوڈ کی ایک رینج. بھی چیزیں پھیل جا سکتا ہے ٹیبل بھر میں. اور یہ بھی تو بہت اچھا ہو جائے گا جان اور جوناتھن کی طرح اسی طرح کے اعداد و شمار،، شاید وزن کرنے کے لئے باہر پھیل گیا ہیش ٹیبل میں مختلف مقامات پر. یہ ایک اچھا فائدہ ہو جائے گا. 

یہاں ایک ہیش تقریب کی ایک مثال ہے. میں نے پہلے اس سے ایک کو لکھا. یہ ایک خاص طور پر نہیں ہے اچھی ہیش تقریب واقعی نہیں ہے کہ وجوہات کی بنا پر اب میں جا برداشت. لیکن تم یہاں کیا ہو رہا ہے دیکھتے ہیں؟ ہم ایک متغیر کا اعلان کر رہے ہیں ایسا لگتا ہے رقم اور 0 کے برابر یہ قائم بلایا. اور پھر بظاہر میں کچھ کر رہا ہوں اتنی دیر strstr [J] کے برابر نہیں ہے کے طور پر 0 الٹا سلیش کے لئے. میں وہاں کیا کر رہا ہوں؟ 

یہ بنیادی طور پر صرف ایک اور مثال ہے [کو لاگو کرنے کے طریقہ ہے؟ پریس Strl؟] آپ نے جب پتہ لگانے سٹرنگ کے اختتام تک پہنچ. تو میں نے اصل میں نہیں ہے سٹرنگ کی لمبائی کا حساب، میں مارا جب میں نے صرف استعمال کر رہا ہوں الٹا سلیش 0 کردار میں جانتا ہوں میں سٹرنگ کے آخر تک پہنچ گئے ہیں. اور پھر میں رکھنے کے لئے جا رہا ہوں اس سٹرنگ کے ذریعے iterating کر، strstr [J] انہوں نے مزید کہا تو خلاصہ، اور دن کے اختتام رقم جدید واپس جا HASH_MAX. 

بنیادی طور پر تمام اس ہیش تقریب اضافہ کر رہا ہے کر رہا ہے کے ASCII اقدار کے تمام میرے سٹرنگ، اور پھر یہ ہے کچھ hashcode آرہے ہیں HASH_MAX طرف modded. شاید یہ سائز ہے میرے صف کی، ٹھیک ہے؟ میں ہیش ہو رہی نہیں کرنا چاہتا کوڈ میری سرنی سائز 10 میں سے ہے، میں ہو رہی ہو نہیں کرنا چاہتا باہر ہیش کوڈ 11، 12، 13، مجھے میں چیزیں ڈال کر سکتے ہیں صف کے ان جگہوں، کہ غیر قانونی ہو گا. میں نے ایک انقطاع غلطی کا شکار تھا. 

اب یہاں ایک اور فوری ایک طرف ہے. عام طور پر آپ کو شاید نہیں جا رہے ہیں آپ کے اپنے ہیش افعال لکھنا چاہتا ہوں. یہ اصل میں کا تھوڑا سا ہے ایک آرٹ، ایک سائنس. اور ان میں چلا جاتا ہے کہ ایک بہت کچھ ہے. جیسے میں نے کہا انٹرنیٹ،، بھرا ہوا ہے بہت اچھا ہیش افعال میں سے، اور آپ کے لئے انٹرنیٹ کا استعمال کرنا چاہئے یہ واقعی ہے کیونکہ ہیش افعال صرف کی قسم کا ایک غیر ضروری وقت کی بربادی آپ کی اپنی تخلیق کرنے کے لئے. 

آپ سادہ ہیں لکھ سکتے ہیں جانچ کے مقاصد کے لئے. لیکن آپ کو اصل میں جا رہے ہیں جب ڈیٹا hashing کے اور ذخیرہ کرنے شروع تم ایک ہیش ٹیبل میں شاید کرنا چاہتے ہیں جا پیدا کیا گیا تھا کہ کچھ تقریب کو استعمال کرنے آپ کے لیے، کہ انٹرنیٹ پر موجود ہے. آپ کو صرف اس بات کا یقین کرتے ہیں تو اپنے ذرائع کا حوالہ دیتے ہیں. کوئی وجہ نہیں ہے یہاں کچھ چوری. 

کمپیوٹر سائنس کمیونٹی ہے یقینی طور پر اقدار سے بڑھتی ہوئی، اور واقعی اوپن سورس، اور یہ بہت ضروری ہے اپنے ذرائع کا حوالہ دیتے ہیں تاکہ لوگوں کے لئے انتساب حاصل کر سکتے ہیں وہ کر رہے ہیں کہ کام کمیونٹی کے فائدے کے لئے کام کر رہے. تو ہمیشہ sure-- ہو اور نہ صرف ہیش کے لئے افعال، لیکن عام طور پر جب آپ ایک باہر ذرائع سے کوڈ کا استعمال، ہمیشہ آپ کے منبع کا حوالہ دیتے ہیں. کیا جو شخص کے لئے کریڈٹ دینے کے کام میں سے کچھ تو آپ کی ضرورت نہیں ہے. 

ٹھیک ہے تو اس پر نظرثانی کی اجازت ایک سیکنڈ کے لئے ہیش ٹیبل. ہم نے چھوڑ دیا ہے جہاں یہ ہے ہم داخل بعد بند اس ہیش ٹیبل میں جان اور پال. آپ یہاں ایک مسئلہ نظر آتا ہے؟ آپ کے پاس دو دیکھ سکتا. لیکن خاص طور پر، آپ کو کیا کرنا یہ ممکن مسئلہ دیکھ رہے ہو؟ 

کیا میں رنگو ہیش، اور اگر بعد پروسیسنگ پتہ چلا ہے کہ ہیش تقریب کے ذریعے اس کے اعداد و شمار رنگو بھی hashcode 6 پیدا. میں نے پہلے ہی میں اعداد و شمار مل گیا ہے hashcode-- سرنی مقام 6. تو یہ شاید تھوڑا سا ہونے جا رہا ہے اب میرے لئے ایک مسئلہ کی، ٹھیک ہے؟ 

ہم نے ایک تصادم کہتے. اور تصادم اس وقت ہوتی ہے جب دو اعداد و شمار کے ٹکڑے ٹکڑے ایک ہی ہیش کے ذریعے چلانے کے تقریب ایک ہی hashcode برآمد. شاید ہم اب بھی دونوں حاصل کرنا چاہتے ہیں ہیش ٹیبل میں اعداد و شمار کے ٹکڑے ٹکڑے، دوسری صورت میں ہم رنگو چلانے نہیں کیا جائے گا منمانے ہیش تقریب کے ذریعے. ہم شاید حاصل کرنا چاہتے ہیں اس صف میں رنگو. 

ہم اگرچہ ایسا کیسے، وہ تو اور پال دونوں پیداوار hashcode 6 ہم نے پال ادلیکھت نہیں کرنا چاہتا، ہم نے پال بھی بننا چاہتا ہوں. تو ہم حاصل کرنے کے لئے ایک راستہ تلاش کرنے کی ضرورت ہے ہیش ٹیبل میں عناصر اب بھی ہماری فوری محفوظ اندراج اور فوری نظر. اور اس سے نمٹنے کے لئے ایک طریقہ ہے تحقیقات لکیری بلایا کچھ کرنا. 

ہم ایک ہے تو یہ طریقہ استعمال کرتے ہوئے تصادم، اچھی طرح سے، ہم کیا کرتے ہیں؟ ویسے ہم صف جگہ میں ڈال دیا نہیں کیا جا سکتا 6، یا جو کچھ بھی hashcode پیدا کیا گیا تھا، کی hashcode پلس 1 میں اسے ڈال دو. اور یہ کہ مکمل چلو تو hashcode پلس 2 میں ڈال دیا. یہ وجود کا فائدہ وہ ہے تو بالکل نہیں ہم وہ ہے جہاں، اور ہم تلاش شروع کرنا پڑے، شاید ہم بہت دور جانے کی ضرورت نہیں ہے. ہو سکتا ہے کہ ہم تلاش کرنے کی ضرورت نہیں ہیش ٹیبل کے تمام این عناصر. شاید ہم تلاش کرنا پڑے ان میں سے ایک جوڑے. 

اور اس طرح ہم اب بھی کی طرف دیکھ بھال کر رہے ہیں اوسط کیس 1 کے قریب بمقابلہ کیا جا رہا ہے (ن) کے قریب، تو ہو سکتا ہے کہ کام کریں گے. تو یہ کس طرح دیکھتے ہیں حقیقت میں باہر کام کر سکتے ہیں. اور ہو سکتا ہے کا پتہ لگانے کر سکتے ہیں تو دیکھتے ہیں یہاں ہو سکتا ہے کہ مسئلہ. 

ہم بارٹ ہیش کا کہنا ہے کہ. تو اب ہم ایک نیا سیٹ کو چلانے کے لئے جا رہے ہیں ہیش تقریب کے ذریعے ڈور کی، اور ہم ہیش کے ذریعے بارٹ چلائیں تقریب، ہم hashcode 6 حاصل. ہم ایک نظر ڈالیں، ہم 6 دیکھیں خالی، تو ہم وہاں بارٹ ڈال کر سکتے ہیں. 

اب ہم لیزا اور اس ہیش بھی hashcode 6 پیدا. ٹھیک ہے اب ہم اس کا استعمال کر رہے ہیں کہ لکیری، ہم 6 سے شروع طریقہ تحقیقات ہم 6 بھرا ہوا ہے کہ دیکھیں. ہم نے 6 میں Lisa نہیں ڈال سکتا. تو ہم کہاں جاتے ہو؟ 7 میں چلتے ہیں. 7 کی خالی، تو کام کرتا ہے. تو وہاں لیزا ڈال دو. 

اب ہم ہومر ہیش اور ہم 7 حاصل. ٹھیک ہے اچھی طرح سے ہم جانتے ہیں 7 کی مکمل کہ اب، تو ہم وہاں ہومر نہیں ڈال سکتا. تو 8 جانے. 8 دستیاب ہے؟ جی ہاں، اور 7 سے 8 کے قریبی، اگر ایسا ہے تو ہم ہیں کی تلاش شروع کرنے کے لئے ہے بہت دور جانے کے لئے حاصل کرنے کے لئے نہیں جا رہا. اور اس طرح کے 8 میں ہومر ڈال دو. 

اب ہم ہیش Maggie اور 3 واپس، بھگوان کا شکر ہے ہم صرف وہاں ہے Maggie ڈال کرنے کے قابل ہو. ہم کسی کو ایسا کرنے کی ضرورت نہیں ہے قسم کی ہے کہ کے لئے تحقیقات. اب ہم Marge کے ہیش، اور Marge کے بھی 6 واپس. 

ویسے 6، 8 بھرا ہوا ہے، 7 سے بھرا ہوا ہے، سے بھرا ہوا ہے 9، ٹھیک 9 خالی ہے، خدا کا شکر. میں 9 Marge کے ڈال کر سکتے ہیں. پہلے ہم شروع کر رہے ہیں دیکھ سکتے ہیں کہ ہم ہیں جہاں اب یہ مسئلہ ہے کے لئے قسم چیزوں بڑھاتے کرنے کے لئے شروع کے دور ان ہیش کوڈ سے. اور 1 کے کہ تھیٹا، اوسط مسلسل وقت کیا جا رہا ہے کی صورت، ایک چھوٹا سا more-- حاصل کرنے کے لئے شروع کر رہا ہے ایک چھوٹا سا زیادہ کرتے ہیں کرنے کے لئے شروع (ن) کے تھیٹا کی طرف. ہم اس سے محروم کرنے کے لئے شروع کر رہے ہیں ہیش میزیں کا فائدہ. 

ہم نے ابھی دیکھا ہے کہ یہ مسئلہ clustering کے کہا جاتا ہے کچھ ہے. اور کے بارے میں بہت برا کیا ہے clustering کے کہ آپ کو ایک بار ہے کی طرف سے ہیں کہ دو عناصر کی طرف سے ہے یہ اس سے بھی زیادہ ہونے کا امکان ہے کی طرف، آپ ڈبل ہے موقع، آپ جا رہے ہیں ایک تصادم حاصل کرنے کہ کلسٹر کے ساتھ، اور کلسٹر ایک کی طرف سے ہو جائے گا. اور آپ کو بڑھتی ہوئی اور بڑھتی ہوئی رکھیں گے ایک تصادم ہونے کے امکانات. اور آخر میں یہ صرف کے طور پر برا ہے کے طور پر تمام ڈیٹا چھانٹ رہا ہے نہیں. 

دوسرے مسئلہ اگرچہ ہم ہے اب بھی، اور اب تک اس نقطہ تک، ہم کسی طرح اسکے کیا گیا ہے ایک ہیش میز کیا سمجھنے، ہم ابھی تک صرف 10 ڈور کے لئے کمرے ہے. ہم ہیش جاری رکھنا چاہتے ہیں تو اسپرنگ فیلڈ کے شہریوں، ہم صرف وہاں میں ان میں سے 10 حاصل کر سکتے ہیں. اور ہم کوشش کریں اور ایک 11th یا 12th کے شامل تو ہم ڈال کرنے کے لئے ایک جگہ نہیں ہے. ہم صرف کے ارد گرد کتائی کیا جا سکتا ہے حلقوں، ایک خالی جگہ تلاش کرنے کی کوشش اور ہم شاید پھنس ایک لامتناہی لوپ میں. 

تو خیال کو ڈھال لیتا ہے اس طرح چیز کا جکڑا جانا ؟. بلایا. اور یہ کہ ہم میں لانے کے لئے کہاں جا رہے ہیں ہے واپس تصویر میں منسلک کی فہرست. اگر بجائے صرف ذخیرہ کرنے کی صف میں اعداد و شمار خود، صف کے ہر عنصر سکتا ایک سے زیادہ ٹکڑوں ڈیٹا کی پکڑ؟ ٹھیک ہے کہ حق، کوئی مطلب نہیں ہے؟ ہم ایک صف ہے جو صرف کر سکتے ہیں جانتے ہیں ایک صف کے ہر عنصر hold-- صرف ایک ٹکڑا پکڑ کر سکتے ہیں کہ اعداد و شمار کی قسم کے اعداد و شمار کے. 

لیکن کیا ہے کہ ڈیٹا کی قسم ایک لنک کی فہرست، ٹھیک ہے؟ تو کیا ہوا اگر ہر صف کے عنصر تھا ایک لنک کی فہرست کے سربراہ پوائنٹر؟ اور پھر ہم تعمیر کر سکتے ہیں ان سے منسلک کی فہرست اور، منمانے ان کے بڑھنے منسلک کی فہرست اجازت دیتے ہیں کیونکہ ہم اگاتے ہیں اور ایک سے زیادہ بہت چھوٹا کرنے ایک سرنی کرتا flexibly پر سے. تو کیا اب ہم استعمال کرتے ہیں تو، ہم صحیح، اس کا راستہ روک سکیں؟ ہم ان زنجیروں میں اضافہ کرنے کے لئے شروع ان سرنی مقامات سے باہر. 

اب ہم ایک لامتناہی فٹ کر سکتے ہیں ڈیٹا کی رقم، یا لامحدود نہیں، کی ایک صوابدیدی رقم ڈیٹا، ہماری ہیش ٹیبل میں کبھی میں چلانے کے بغیر تصادم کا مسئلہ. ہم بھی ختم ہے ایسا کرنے سے clustering کے. اور اچھی طرح سے ہم داخل جب جانتے ہیں کہ ایک لنک کی فہرست میں، آپ کو یاد ہے اکیلے، منسلک کی فہرست پر اپنے ویڈیو سے منسلک کی فہرست اور دوگنا منسلک کی فہرست، یہ ایک مسلسل وقت آپریشن ہے. ہم صرف سامنے اضافہ کر رہے ہیں. 

اور نظر کے لئے، اچھی طرح سے ہم جانتے ہیں کہ ایک لنک کی فہرست میں نظر آتے ہیں صحیح، ایک مسئلہ ہو سکتا ہے؟ ہم کے ذریعے تلاش کرنے کے لئے ہے شروع سے اسے ختم کرنے. کوئی بے ترتیب نہیں ہے ایک لنک کی فہرست میں رسائی. لیکن اگر اس کی بجائے ایک ہونے سے منسلک ایک نظر دوڑائیں ن O ہو جائے گا جہاں فہرست، اب ہم 10 سے منسلک کی فہرست ہے، یا 1،000 منسلک کی فہرست، اب یہ 10 سے تقسیم ن O ہے، یا ن O 1،000 کی طرف سے تقسیم. 

اور ہم بات کر رہے تھے جبکہ نظریاتی طور پر پیچیدگی کے بارے میں ہم حقیقی میں، constants کی نظرانداز ان چیزوں کو اصل بات دنیا، ٹھیک ہے؟ ہم اصل میں محسوس کریں گے ایسا ہوتا ہے کہ 10 گنا تیزی سے چلانے کے لئے، یا 1،000 گنا تیزی، ہم طویل عرصے سے ایک تقسیم کر رہے ہیں کیونکہ 1،000 چھوٹے زنجیروں میں چین. اور اس طرح ہم نے ہر وقت تلاش کرنے کے لئے ہم کر سکتے ہیں ان زنجیروں میں سے ایک کے ذریعے ہم پرواہ نہیں کرتے 999 زنجیروں کو نظر انداز کے بارے میں، اور صرف اس ایک کی تلاش. 

جس میں اوسطا ہے 1،000 بار کم ہو. اور اس طرح ہم اب بھی قسم کے ہیں یہ اوسط کیس کی طرف دیکھ بھال کی مسلسل وقت، لیکن صرف ہم فائدہ کر رہے ہیں کیونکہ کچھ بڑی مسلسل پہلو کی طرف سے تقسیم. یہ کیسے ہو سکتا ہے چلو دیکھتے ہیں اصل میں اگرچہ نظر آتے ہیں. تو یہ ہم نے ہیش میز تھا ہم نے ایک ہیش میز اعلان اس سے پہلے کہ 10 ڈور ذخیرہ کرنے کے قابل تھا. ہم اب ایسا کرنے کے لئے نہیں جا رہے ہیں. ہم پہلے ہی جانتے اس طریقہ کار کی حدود. اب ہمارے ہیش کی میز پر جا رہا ہے 10 نوڈس، اشارہ کی ایک صف منسلک کی فہرست کے سربراہوں کو. 

اور اب یہ شہوت انگیز null ہے. ان 10 اشارہ میں سے ہر ایک، شہوت انگیز null ہے. کچھ بھی نہیں ہمارے میں نہیں ہے اب میز ہیش. 

اب کچھ ڈال کرنا شروع کر دیں اس ہیش ٹیبل میں چیزوں کو. اور ہم اس طریقہ ہے کس طرح دیکھتے ہیں ہمیں تھوڑا سا فائدہ ہو رہا. اب جای ہیش کرتے ہیں. ہم سٹرنگ جای ذریعے چلایا جائے گا کریں گے ایک ہیش تقریب اور ہم 6 واپس. ویسے ہم اب میں کیا کروں؟ 

ٹھیک ہے اب سے منسلک کی فہرست کے ساتھ کام، ہم arrays کے ساتھ کام نہیں کر رہے. اور ہم کام کر رہے ہیں جب منسلک کی فہرست کے ساتھ ہم ہم کو متحرک طور پر شروع کرنے کے لئے کی ضرورت ہے جگہ اور عمارت زنجیروں مختص. اس طرح کی ان بنیادی ہیں how-- ہے ایک لنک کی فہرست کی تعمیر کے عناصر. تو متحرک چلو جای کے لئے جگہ مختص، اور اس کے بعد کی چین کے لئے اس میں شامل ہیں. 

تو اب ہم نے کیا کیا نظر آتے ہیں. ہم جای ہیش جب ہم hashcode 6 ہے. سرنی مقام 6 اب پوائنٹر ایک لنک کی فہرست کے سربراہ کی طرف اشارہ ہے، اور اب یہ صرف ہے ایک لنک کی فہرست کے عنصر. اور اس میں نوڈ لنک کی فہرست جای ہے. 

ہم جای تلاش کرنے کے لئے کی ضرورت ہے تو بعد میں، ہم صرف ایک بار پھر جای ہیش، ہم اپنے کی وجہ سے ایک بار پھر 6 حاصل ہیش تقریب نیتاتمک ہے. اور پھر ہم سر میں شروع لنک کی فہرست کے اشارہ سرنی محل وقوع کی طرف سے 6، اور ہم iterate کرسکتے ہیں جای تلاش کرنے کی کوشش ہے کہ اس پار. اور ہم تعمیر تو ہمارے مؤثر طریقے سے میز ہیش، اور ہماری ہیش تقریب مؤثر طریقے سے اچھی طرح سے ڈیٹا کی تقسیم کے لئے، اوسطا ان میں سے ہر ایک سے منسلک ہر صف مقام پر فہرستوں اگر سائز 1/10 ہو جائے گا ہم صرف ایک بڑی کے طور پر یہ تھا اس میں سب کچھ کے ساتھ منسلک فہرست. 

ہم نے بڑا منسلک ہے کہ تقسیم کریں تو 10 سے منسلک کی فہرست میں فہرست ہر ایک کی فہرست 1/10 سائز ہو جائے گا. اور اسی طرح 10 گنا تیز کے ذریعے تلاش کرنے. تو پھر ایسا کرنے دو. اب راس ہیش کرتے ہیں. 

اور ہم ایسا جب راس، کا کہنا ہے کہ ہم واپس حاصل ہیش کوڈ 2. ٹھیک ہے اب ہم کو متحرک طور پر ایک مختص نیا نوڈ، ہم، اس نوڈ میں Ross ڈال اور ہم صف مقام کہتے ہیں 2، شہوت انگیز null کی طرف اشارہ کی بجائے، ایک لنک کے سربراہ کی طرف اشارہ ہے جن کی صرف نوڈ فہرست راس ہے. اور اگر ہم اس سے زیادہ وقت کر سکتے ہیں راہیل ہیش اور hashcode 4 حاصل کر سکتے ہیں. راخل ڈال، ایک نیا نوڈ malloc نوڈ، اور ایک سرنی مقام کہتے ہیں 4 اب سر کی طرف اشارہ ہے جس کا ایک لنک کی فہرست کے صرف عنصر راہیل ہو. 

ٹھیک ہے لیکن کیا تو کیا ہوتا ہم نے ایک تصادم ہے؟ ہم collisions سے کس طرح نمٹنے دیکھتے ہیں علیحدہ جکڑا جانا؟ طریقہ استعمال کرتے ہوئے. کی ناو ہیش کرتے ہیں. ہم hashcode 6 حاصل. ہمارے گزشتہ مثال میں ہم صرف کر رہے تھے صف میں ڈور ذخیرہ. یہ ایک مسئلہ تھا. 

ہم clobber نہیں نہیں کرنا چاہتے جوی، اور ہم نے پہلے ہے ہم نے کچھ clustering کے حاصل کر سکتے ہیں کہ دیکھا مسائل ہم کوشش کریں تو اور قدم کے ذریعے اور تحقیقات. لیکن کیا اگر ہم صرف کی قسم یہ صحیح، اسی طرح کا علاج؟ یہ صرف ایک عنصر شامل کرنے کی طرح ہے ایک لنک کی فہرست کے سربراہ. ناو کے لئے صرف malloc کے خلائی دو. 

ہم ناو کے اگلے پوائنٹر پوائنٹس کہیں گے لنک کی فہرست کے پرانے سر پر، اور پھر 6 صرف کی طرف اشارہ ہے لنک کی فہرست کے نئے سربراہ. اور اب ہم میں ناو تبدیل کر دیا ہے، دیکھو. اب ہم دونوں محفوظ کر سکتے ہیں hashcode 6 کے ساتھ عناصر، اور ہم کسی بھی مسئلہ نہیں ہے. 

کہ بہت زیادہ سب جکڑا جانا کرنے کے لئے ہے. اور جکڑا جانا ضرور ہے ہے کہ طریقہ اگر آپ کے لئے سب سے زیادہ مؤثر ہونے جا رہا آپ کو ایک ہیش ٹیبل میں ڈیٹا ذخیرہ کرنے کر رہے ہیں. لیکن اس مجموعہ arrays اور منسلک فہرستوں ایک دوسرے کے ساتھ واقعی ایک ہیش ٹیبل بنانے کے لئے ڈرامائی طور پر آپ کی صلاحیت میں بہتری اعداد و شمار کی بڑی مقدار میں محفوظ، اور بہت تیزی سے اور مؤثر طریقے سے تلاش کہ اعداد و شمار کے ذریعے. 

ایک وہاں اب بھی ہے وہاں سے باہر آنکڑا ڈھانچہ یہاں تک کہ ایک تھوڑا سا ہو سکتا ہے ضمانت کے لحاظ سے بہتر کہ ہمارے اندراج، منسوخی، اور اوپر دیکھو بار بھی تیز ہیں. اور ہم کوشش کرتا ہے پر ایک ویڈیو میں دیکھیں گے کہ. میں ڈوگ لایڈ ہوں، اس CS50 ہے.