[عزف الموسيقى] DOUG لويد: عليك الآن أعرف الكثير عن المصفوفات، وأنت تعرف الكثير عن القوائم المرتبطة. ولقد بحث إيجابيات وسلبيات، لدينا ناقش أن القوائم المرتبطة يمكن الحصول على أكبر وأصغر، لكنها تناول المزيد من الحجم. المصفوفات هي أكثر وضوحا ل استخدام، ولكنها مقيدة في قدر كما لدينا لضبط حجم مجموعة في البداية ثم نحن عالقون معها. 

ولكن هذا، لدينا الى حد كبير استنفدوا جميع المواضيع لدينا حول القوائم المرتبطة والمصفوفات. أو لديك نحن؟ ربما نستطيع أن نفعل شيئا أكثر إبداعا. وهذا النوع من يقرض فكرة جدول تجزئة. 

حتى في جدول تجزئة ونحن في طريقنا لمحاولة الجمع بين مجموعة مع قائمة مرتبطة. ونحن في طريقنا لاتخاذ مزايا في المصفوفة، مثل الوصول العشوائي، أن تكون قادرة على اذهبوا الى مجموعة العنصر 4 أو مجموعة عنصر 8 دون الحاجة إلى تكرار عبر. هذا هو سريع جدا، أليس كذلك؟ 

لكننا نريد أيضا أن يكون بياناتنا هيكل تكون قادرة على النمو والانكماش. نحن لسنا بحاجة، ونحن لا تريد أن تكون مقيدة. ونحن نريد أن نكون قادرين لإضافة وإزالة الأشياء بسهولة جدا، والتي إذا كنت تذكر، غير معقدة للغاية مع مجموعة. ويمكننا أن نطلق على هذا الشيء الجديد جدول تجزئة. 

وإذا ما نفذت بشكل صحيح، نحن نوع من الأخذ مزايا كل من البيانات هياكل كنت قد رأيت بالفعل، المصفوفات والقوائم المرتبطة. الإدراج يمكن أن تبدأ ل تميل نحو ثيتا من 1. ثيتا لم نناقش حقا، ولكن ثيتا هو مجرد متوسط ​​الحال، ما يحدث في الواقع أن يحدث. أنت لن دائما ل يكون أسوأ سيناريو، وكنت لا دائما ستكون لدينا أفضل سيناريو، فما متوسط ​​السيناريو؟ 

حسنا متوسط ​​الإدراج في جدول تجزئة يمكن أن تبدأ في الاقتراب من وقت ثابت. ويمكن الحصول على الحذف إغلاق لوقت ثابت. ويمكن الحصول على بحث إغلاق لوقت ثابت. That's-- ليس لدينا بيانات هيكل بعد أن تستطيع أن تفعل ذلك، وحتى هذا يبدو بالفعل وكأنه شيء كبير جدا. لقد التخفيف حقا عيوب كل من تلقاء نفسها. 

للحصول على هذا الأداء ترقية على الرغم من أننا تحتاج إلى إعادة التفكير في كيفية أضفنا البيانات في هيكل. على وجه التحديد نريد البيانات نفسها أن تقول لنا حيث يجب ان تذهب في الهيكل. وإذا كنا بعد ذلك بحاجة الى ان نرى ما اذا كان في هيكل، إذا نحن بحاجة للعثور عليه، نحن نريد أن ننظر إلى البيانات مرة أخرى، ويكون قادرا على نحو فعال، باستخدام البيانات، والوصول عشوائيا ذلك. فقط من خلال النظر في البيانات يجب أن لدينا فكرة من أين بالضبط نحن الذهاب للعثور عليه في جدول التجزئة. 

الآن الجانب السلبي للتجزئة الجدول هو انهم حقا سيئة جدا في الطلب أو فرز البيانات. في واقع الأمر، إذا قمت بتشغيل لاستخدامها لطلب أو فرز البيانات التي تفقد كل من مزايا قمت مسبقا كان من حيث الإدراج والحذف. الوقت يصبح أقرب إلى ثيتا ن، ولقد الأساس تراجعت إلى قائمة مرتبطة. وهكذا نريد فقط لاستخدام تجزئة الجداول إذا كنا لا يهتمون سواء يتم فرز البيانات. لالسياق الذي عليك استخدامها في CS50 وربما كنت لا أهتم أن يتم فرز البيانات. 

لذلك جدول التجزئة هو مزيج من قطعتين متميزة التي نعرفها. الأول هو وظيفة، التي نحن عادة استدعاء دالة البعثرة. وهذه الوظيفة التجزئة هو الذهاب الى عودة بعض عدد صحيح غير سالب، التي نحن عادة استدعاء hashcode، OK؟ القطعة الثانية عبارة عن صفيف، الذي هو قادرة على تخزين البيانات من النوع الذي تريد أن تضع في بنية البيانات. سنقوم صد على عنصر قائمة مرتبطة في الوقت الراهن ونبدأ مع أساسيات تجزئة الجدول للحصول على رأسك من حوله، ومن ثم فإننا سوف تهب ربما عقلك قليلا عندما كنا الجمع بين المصفوفات وقوائم الارتباط معا. 

على الرغم من أن الفكرة الأساسية غير أن نأخذ بعض البيانات. نحن تشغيل تلك البيانات من خلال وظيفة التجزئة. وحتى تتم معالجة البيانات ويبصق العدد، OK؟ ثم مع هذا العدد نحن فقط تخزين البيانات نحن نريد لتخزين في مجموعة في ذلك الموقع. هكذا على سبيل المثال لدينا ربما هذا الجدول تجزئة السلاسل. انها حصلت على 10 عناصر في ذلك، حتى نحن يمكن أن تناسب 10 السلاسل في ذلك. 

دعونا نقول أننا نريد أن تجزئة جون. حتى جون كبيانات نريد أن إدراج في هذا الجدول التجزئة في مكان ما. أين نضع ذلك؟ حسنا عادة مع مجموعة حتى الآن أننا ربما وضعه في مجموعة 0 موقع. ولكن الآن لدينا هذه الوظيفة تجزئة جديدة. 

ودعونا نقول اننا تشغيل جون من خلال هذه الوظيفة تجزئة وانه يبصق 4. حسنا هذا هو المكان الذي نحن تريد الذهاب الى وضع جون. نحن نريد ان نضع جون في موقع مجموعة 4، لأننا إذا تجزئة جون again-- دعونا نقول أننا في وقت لاحق تريد البحث ومعرفة إذا جون موجود في هذه البعثرة table-- كل ما عليك القيام به يتم تشغيله من خلال نفس تجزئة وظيفة، احصل على خروج عدد 4، وتكون قادرة على العثور جون على الفور في بنية البيانات لدينا. هذا أمر جيد جدا. 

دعونا نقول نقوم به الآن هذا مرة أخرى، نحن نريد أن تجزئة بول. نريد أن نضيف بول في هذا الجدول التجزئة. دعنا نقول أن هذا الوقت ونحن تشغيل بول من خلال وظيفة التجزئة، وhashcode الذي تم إنشاؤه هو 6. حسنا الآن يمكننا وضع بول في الموقع مجموعة 6. وإذا كنا بحاجة للبحث عن ما إذا كان بول هو في هذا الجدول التجزئة، ويدير كل ما عليك القيام به بول من خلال وظيفة تجزئة مرة أخرى ونحن في طريقنا للحصول على 6 من جديد. 

ثم نحن ننظر فقط في مجموعة موقع 6. هو بول هناك؟ إذا كان الأمر كذلك، وانه في جدول التجزئة. هو بولس لم يكن هناك؟ انه ليس في جدول التجزئة. انها واضحة جدا. 

الآن كيف يمكن تعريف دالة التجزئة؟ كذلك هناك حقا لا حدود ل عدد من الوظائف تجزئة الممكنة. في الواقع هناك عدد حقا، منها جيدة حقا على شبكة الانترنت. هناك عدد من الحقيقة، السيئة حقا على شبكة الانترنت. كما انه من السهل جدا لكتابة سيئة واحدة. 

وذلك ما يجعل جيدا حتى وظيفة تجزئة، أليس كذلك؟ كذلك ينبغي دالة تجزئة جيدة استخدام البيانات التي يتم تجزئته فقط، وجميع البيانات التي يتم تجزئته. لذلك نحن لا نريد أن استخدام anything-- نحن لا تتضمن أي شيء آخر بخلاف البيانات. ونحن نريد استخدام كافة البيانات. نحن لا نريد أن استخدام مجرد قطعة من ذلك، ونحن نريد لاستخدام كل ذلك. ودالة البعثرة ينبغي كما تكون حتمية. ماذا يعني ذلك؟ حسنا هذا يعني أنه في كل مرة نحن تمرير نفس قطعة الدقيق للبيانات في دالة البعثرة ونحن دائما الحصول على نفس hashcode بها. إذا كنت تمر جون في وظيفة تجزئة أخرج 4. وأود أن تكون قادرة على القيام بذلك 10000 مرة وأنا دائما الحصول على 4. لذلك لا أرقام عشوائية بشكل فعال يمكن أن تشارك في تجزئة لدينا tables-- في وظائف التجزئة لدينا. 

وينبغي أن يكون وظيفة تجزئة أيضا موحد توزيع البيانات. إذا كنت في كل مرة تشغيل البيانات من خلال وظيفة تجزئة تحصل على hashcode 0، وهذا ربما ليست كبيرة، أليس كذلك؟ ربما كنت ترغب في كبيرة مجموعة من رموز التجزئة. كما يمكن أن ينتشر الأشياء من جميع أنحاء الجدول. وأيضا سيكون أمرا رائعا إذا حقا بيانات مشابهة، مثل جون وجوناثان، انتشرت ربما إلى تزن مواقع مختلفة في جدول التجزئة. من شأنه أن يكون ميزة لطيفة. 

وهنا مثال على وظيفة تجزئة. لقد كتبت هذا واحد في وقت سابق. انها ليست سيما وظيفة تجزئة جيدة وذلك لأسباب لا حقا تحمل الخوض في الوقت الحالي. ولكن هل ترى ما الذي يحدث هنا؟ يبدو وكأننا إعلان متغير دعا المبلغ ووضع ذلك يساوي 0. ومن ثم يبدو أنني أفعل شيئا طالما strstr [ي] لا تساوي إلى مائل 0. ماذا أفعل هناك؟ 

هذا هو في الأساس مجرد طريقة تنفيذ [؟ strl؟] وكشف عندما قمت وصلت إلى نهاية السلسلة. لذلك أنا لم يكن لديك فعلا حساب طول السلسلة، أنا فقط باستخدام عندما ضرب مائل 0 حرف أعرف لقد وصلنا إلى نهاية السلسلة. ثم انا ذاهب للحفاظ على بالتكرار عبر هذه السلسلة، مضيفا strstr [ي] وخلاصة القول، ثم في نهاية اليوم سوف تعود مبلغ زارة الدفاع HASH_MAX. 

أساسا كل هذا تجزئة وظيفة يقوم به هو إضافة ما يصل كافة القيم ASCII من سلسلة بلدي، وبعد ذلك انها إعادة بعض hashcode كتكوت من قبل HASH_MAX. من المحتمل أن يكون حجم من مجموعة بلدي، أليس كذلك؟ أنا لا أريد أن يكون الحصول على تجزئة رموز إذا مجموعة بلدي هي من حجم 10، أنا لا أريد أن يكون الحصول على رموز التجزئة خارج 11، 12، 13، وأنا لا يمكن أن نضع الأمور في تلك المواقع للمجموعة، أن ذلك سيكون غير قانوني. كنت تعاني من خطأ تجزئة. 

الآن هنا هو آخر جانبا سريعة. عموما كنت ربما لن أريد أن أكتب ظائف التجزئة الخاصة بك. هو في الواقع قليلا من فن وليس علما. وهناك الكثير الذي يذهب الى لهم. الإنترنت، كما قلت، هو الكامل وظائف تجزئة جيدة حقا، ويجب عليك استخدام شبكة الإنترنت ل العثور على وظائف التجزئة لأنه حقا مجرد نوع من لا لزوم لها مضيعة للوقت لخلق بنفسك. 

يمكنك كتابة تلك بسيطة لأغراض الاختبار. ولكن عندما كنت في الواقع ذاهبون ل بدء تجزئة البيانات وتخزينها في جدول تجزئة كنت ربما تريد الذهاب الى استخدام بعض الوظائف التي تم إنشاؤها بالنسبة لك، وهذا موجود على الإنترنت. إذا كنت لا يكون مجرد متأكد ذكر المصادر الخاصة بك. ليس هناك سبب ل تسرق أي شيء هنا. 

المجتمع العلمي الكمبيوتر تزايد بالتأكيد، وحقا القيم المصدر المفتوح، وأنه من المهم حقا إلى الاستشهاد بمصادر الخاص بك حتى يتمكن الناس يمكن الحصول على إسناد لل العمل انهم به لصالح المجتمع. لذا يجب دائما sure-- وليس فقط للتجزئة وظائف، ولكن عموما عند استخدام رمز من مصدر خارجي، يستشهد دائما المصدر. منح الائتمان للشخص الذي فعل بعض الأعمال لذلك لم يكن لديك ل. 

OK لذلك دعونا إعادة النظر في هذا جدول تجزئة لفترة ثانية. هذا هو المكان الذي غادرنا من بعد أن أدرجت جون وبول في هذا الجدول التجزئة. هل ترى المشكلة هنا؟ قد ترى اثنين. ولكن على وجه الخصوص، هل نرى هذه المشكلة المحتملة؟ 

ماذا لو تجزئة رينغو، وذلك تبين أنه بعد تجهيز أن البيانات من خلال دالة البعثرة وحققت رينغو وhashcode 6. لقد حصلت بالفعل على البيانات hashcode-- موقع مجموعة 6. ذلك انه سيكون على الارجح أن يكون قليلا مشكلة بالنسبة لي الآن، أليس كذلك؟ 

نحن نسمي هذا الاصطدام. ويحدث الاصطدام عندما اثنين قطعة من البيانات من خلال تشغيل نفس تجزئة وظيفة تدر نفس hashcode. يفترض أننا لا تزال ترغب في الحصول على كل قطعة من البيانات في جدول التجزئة، وإلا فإننا لن تكون قيد التشغيل رينغو تعسفا من خلال وظيفة التجزئة. نريد من المفترض أن يحصل رينغو إلى أن مجموعة. 

كيف لنا أن نفعل ذلك على الرغم من ذلك، إذا كان وبول كل من العائد hashcode 6؟ نحن لا نريد أن الكتابة بول، نريد بول أن يكون هناك أيضا. لذلك نحن بحاجة لايجاد وسيلة للحصول على العناصر في الجدول التجزئة التي لا يزال يحافظ على لدينا سريعة الإدراج ونظرة سريعة تصل. وطريقة واحدة للتعامل معها هي ل قيام ما يسمى خطية التحقيق. 

باستخدام هذه الطريقة إذا كان لدينا تصادم، حسنا، ماذا نفعل؟ حسنا نحن لا يمكن وضعه في موقع مجموعة 6، أو أيا كان hashcode تم إنشاؤها، دعونا نضع له في hashcode زائد 1. وإذا كان هذا هو كامل دعونا وضعت له في hashcode زائد 2. صالح هذا الكيان اذا كان ليس بالضبط أين نحن اعتقد انه هو، وعلينا أن نبدأ البحث، ربما لم يكن لدينا للذهاب بعيدا جدا. ربما لم يكن لدينا للبحث جميع العناصر ن من جدول التجزئة. ربما علينا أن بحث اثنين منهم. 

ولذا فإننا ما زلنا تميل نحو أن متوسط ​​حالة كونها قريبة إلى 1 مقابل بالقرب من ن، لذلك ربما هذا سوف يعمل. لذلك دعونا نرى كيف هذا قد عمل في الواقع. ودعونا نرى ما اذا كان ربما يمكننا الكشف عن المشكلة التي قد تحدث هنا. 

دعونا نقول أننا تجزئة بارت. وحتى الآن ونحن في طريقنا لتشغيل مجموعة جديدة سلاسل من خلال وظيفة التجزئة، ونحن تشغيل بارت من خلال تجزئة وظيفة، وحصلنا على hashcode 6. ونحن نلقي نظرة، ونحن نرى 6 هو فارغة، حتى نتمكن من وضع بارت هناك. 

ونحن الآن تجزئة ليزا والتي كما يولد hashcode 6. حسنا الآن أن نستخدمه هذا خطي التحقيق طريقة نبدأ في 6، ونحن نرى أن 6 غير كامل. لا يمكننا وضع ليزا في 6. إذن، أين نذهب؟ دعونا نذهب إلى 7. 7 فارغة، لذلك يعمل. لذلك دعونا نضع ليزا هناك. 

ونحن الآن تجزئة هوميروس ونحصل على 7. موافق جيدا أننا نعلم أن كامل 7 ل الآن، لذلك نحن لا يمكن وضع هوميروس هناك. لذلك دعونا نذهب إلى 8. هو 8 المتاحة؟ نعم، و 8 الوطيدة 7، حتى إذا علينا أن نبدأ بالبحث نحن ليس لدينا للذهاب بعيدا جدا. وذلك دعونا نضع هوميروس في 8. 

ونحن الآن تجزئة ماجي و يعود 3، والحمد لله ونحن قادرون على مجرد وضع ماجي هناك. ليس لدينا للقيام بأي نوع من التحقيق لذلك. ونحن الآن تجزئة زبدة نباتية، و مارج أيضا إرجاع 6. 

حسنا 6 كامل، 7 كامل، 8 كامل، 9، أشكر جميع حق الله، 9 فارغ. يمكن أن أضع زبدة نباتية في 9. إذا يمكننا أن نرى أننا بدأنا لديك هذه المشكلة حيث نحن الآن بدأت تمتد أشياء النوع من بعيدا عن رموز التجزئة الخاصة بهم. وأن ثيتا 1، أن المتوسط حالة كونه وقت ثابت، وبدءا من الحصول على بعض الشيء more-- بدأت تميل قليلا أكثر نحو ثيتا ن. بدأنا نفقد ذلك الاستفادة من الجداول التجزئة. 

هذه المشكلة التي رأيناها فقط هو ما يسمى المجموعات. وما هو سيء حقا حول التكتل هو أنه بمجرد الآن دينا اثنين من العناصر التي هي جنبا الى جانب ذلك يجعله أكثر احتمالا، لديك ضعف فرصة، وأنت تسير لتصادم آخر مع هذه المجموعة، والكتلة سينمو بنسبة واحد. وسوف تستمر في النمو وتزايد احتمال إصابتك حادث تصادم. وفي النهاية انها مجرد بالسوء لا فرز البيانات على الإطلاق. 

والمشكلة الأخرى هي على الرغم من أننا لا يزال، وحتى الآن ما يصل الى هذه النقطة، كنا مجرد نوع من فهم ما هو جدول التجزئة، لا يزال لدينا فقط الغرفة لمدة 10 السلاسل. إذا أردنا أن نستمر في تجزئة المواطنين من سبرينغفيلد، يمكننا الحصول فقط 10 منهم هناك. وإذا حاولنا وإضافة 11TH أو 12TH، ليس لدينا مكان لوضعها. نحن يمكن أن يكون مجرد الغزل في جميع انحاء دوائر محاولة العثور على بقعة فارغة، ونحن ربما تتعثر في حلقة لا نهائية. 

لذلك هذا النوع من يضفي على فكرة من ما يسمى تسلسل. وهذا هو المكان الذي نحن ذاهبون لجلب القوائم المرتبطة مرة أخرى في الصورة. ماذا لو بدلا من تخزين فقط البيانات نفسها في مجموعة، كل عنصر من عناصر المصفوفة يمكن عقد أجزاء متعددة من البيانات؟ حسنا هذا لا معنى له، أليس كذلك؟ ونحن نعلم أن مجموعة يمكن فقط hold-- كل عنصر من عناصر مجموعة يمكن أن تعقد فقط قطعة واحدة بيانات من هذا النوع البيانات. 

ولكن ماذا لو أن نوع البيانات هي قائمة مرتبطة، أليس كذلك؟ وذلك ما إذا كان كل وكان عنصر من المصفوفة مؤشر إلى رأس قائمة مرتبطة؟ ومن ثم نتمكن من بناء تلك القوائم المرتبطة وتنمو لهم بشكل تعسفي، لأن القوائم المرتبطة تسمح لنا أن ينمو ويتقلص أكثر بكثير بمرونة من يفعل صفيف. حتى إذا ما نستخدمها الآن، نحن استفادة من هذا، أليس كذلك؟ نبدأ في زراعة هذه السلاسل من هذه المواقع مجموعة. 

ونحن الآن يمكن أن يصلح لانهائي كمية البيانات، أو لا لانهائي، مبلغ التعسفي ل البيانات، إلى جدول التجزئة لدينا دون تشغيل أي وقت مضى إلى مشكلة التصادم. لقد ألغت أيضا تجمع من خلال ذلك. وكذلك نحن نعرف أننا عندما تضاف في قائمة مرتبطة، إذا كنتم تذكرون من لدينا شريط فيديو على القوائم المرتبطة، منفردة القوائم المرتبطة والقوائم المرتبطة على نحو مضاعف، انها عملية مستمرة الوقت. نحن فقط مضيفا أن الجبهة. 

ولننظر إلى أعلى، وأيضا نعرفه التي تبدو حتى في قائمة مرتبطة يمكن أن يكون مشكلة، أليس كذلك؟ لدينا للبحث عن طريق أنه من البداية إلى النهاية. لا يوجد عشوائي الوصول في قائمة مرتبطة. ولكن إذا بدلا من وجود واحد مرتبط قائمة حيث بحث سيكون O ن، لدينا الآن 10 القوائم المرتبطة، أو 1000 القوائم المرتبطة، الآن حان O ن مقسوما على 10، أو O ن مقسوما 1000. 

وبينما كنا نتحدث نظريا عن التعقيد تغاضينا الثوابت، في الحقيقية العالم هذه الأشياء يهم فعلا، الصحيح؟ ونحن في الواقع سيلاحظ أن هذا يحدث لتشغيل 10 مرات أسرع، أو 1000 مرات أسرع، لأننا توزيع واحد طويل سلسلة عبر 1000 سلاسل أصغر. وهكذا في كل مرة لدينا للبحث من خلال واحدة من تلك السلاسل وسعنا تجاهل 999 سلاسل نحن لا نهتم حول، ومجرد البحث أن واحدا. 

وهو في المتوسط ​​ل تكون أقصر 1000 مرات. ولذا فإننا لا تزال نوع من تميل نحو هذه الحالة متوسط يجري وقت ثابت، ولكن فقط لأننا الاستفادة قسمة بعض عاملا كبيرا المستمر. دعونا نرى كيف أن هذا قد في الواقع تبدو بالرغم من ذلك. لذلك كان هذا جدول التجزئة لدينا قبل أن أعلن أن جدول التجزئة كانت قادرة على تخزين 10 السلاسل. نحن لن نفعل ذلك مرة أخرى. كنا نعرف مسبقا القيود المفروضة على هذه الطريقة. الآن جدول التجزئة لدينا سيكون مجموعة من 10 عقد، مؤشرات إلى رؤساء القوائم المرتبطة. 

والآن انها فارغة. كل واحدة من تلك المؤشرات 10 لاغيا. لا يوجد شيء في منطقتنا تجزئة الجدول في الوقت الحالي. 

الآن دعونا نبدأ في وضع بعض الأمور في هذا الجدول التجزئة. ودعونا نرى كيف أن هذا الأسلوب هو الذهاب إلى تفيدنا قليلا. دعونا الآن تجزئة جوي. سنقوم سيتم تشغيل سلسلة جوي من خلال وظيفة تجزئة ونعود 6. حسنا ماذا نفعل الآن؟ 

كذلك تعمل الآن مع القوائم المرتبطة، نحن لا تعمل مع المصفوفات. وعندما كنا نعمل مع القوائم المرتبطة نحن نعلم أننا بحاجة للبدء حيوي تخصيص سلاسل الفضاء وبناء. هذا النوع من how-- تلك هي جوهر عناصر بناء قائمة مرتبطة. لذلك دعونا حيوي تخصيص مساحة لجوي، ثم دعونا نضيف إليه أن السلسلة. 

حتى ننظر الآن ما فعلناه. عندما كنا تجزئة جوي حصلنا على hashcode 6. الآن المؤشر في مجموعة موقع 6 يشير إلى رأس قائمة مرتبطة، والآن انها فقط عنصر من قائمة مرتبطة. والعقدة في ذلك قائمة مرتبطة هي جوي. 

حتى إذا كنا بحاجة للبحث عن جوي في وقت لاحق، ونحن فقط تجزئة جوي مرة أخرى، نحصل على 6 مرة أخرى لأن لدينا دالة البعثرة هي حتمية. ثم نبدأ في الرأس من القائمة المرتبطة أشار لحسب الموقع مجموعة 6، ويمكننا تكرار عبر تلك محاولة للعثور جوي. وإذا كان لنا أن نبني تجزئة الجدول على نحو فعال، وظيفة تجزئة بشكل فعال لتوزيع البيانات بشكل جيد، في المتوسط ​​كل من تلك المرتبطة القوائم في كل مكان مجموعة سيكون 1/10 من حجم إذا كنا فقط كان على أنها واحدة ضخمة قائمة مرتبطة مع كل شيء في ذلك. 

إذا نوزع التي ربطت ضخمة قائمة عبر 10 القوائم المرتبطة سيكون كل قائمة 1/10 الحجم. وهكذا 10 مرات أسرع للبحث عن طريق. لذلك دعونا نفعل ذلك مرة أخرى. دعونا الآن تجزئة روس. 

ودعونا نقول روس، عندما نفعل ذلك رمز تجزئة نعود هو 2. حسنا نحن الآن حيوي تخصيص عقدة جديدة، وضعنا روس في تلك العقدة، ونحن نقول الآن موقع مجموعة 2، بدلا من الإشارة إلى قيمة خالية، يشير إلى رأس مرتبطة قائمة الذين العقدة الوحيدة هي روس. ويمكننا أن نفعل ذلك أكثر مرة واحدة، ونحن يمكن تجزئة راشيل والحصول على hashcode 4. malloc عقدة جديدة، وطرح راشيل في العقدة، ويقول موقع مجموعة 4 يشير الآن إلى رئيس من قائمة مرتبطة الذي العنصر الوحيد يحدث أن تكون راشيل. 

موافق ولكن ماذا يحدث إذا لدينا الاصطدام؟ دعونا نرى كيف يمكننا التعامل مع الاصطدامات باستخدام طريقة تسلسل منفصل. دعونا تجزئة فيبي. نحصل على hashcode 6. في مثالنا السابق كنا فقط تخزين السلاسل في صفيف. وكانت هذه المشكلة. 

نحن لا نريد أن هزم جوي، وقمنا بالفعل رأينا أن نتمكن من الحصول على بعض المجموعات مشاكل لو كنا في محاولة وخطوة من خلال والتحقيق. ولكن ماذا لو كنا مجرد نوع من علاج هذا بنفس الطريقة، أليس كذلك؟ انها مجرد مثل إضافة عنصر لرئيس قائمة مرتبطة. دعونا الفضاء فقط malloc لفيبي. 

سنقول نقاط المؤشر القادمة فيبي في الرأس القديم من قائمة مرتبطة، ثم 6 نقاط فقط ل الرئيس الجديد للقائمة مرتبطة. ونتطلع الآن، قمنا بتغيير فيبي في. يمكننا الآن تخزين اثنين العناصر مع hashcode 6، وليس لدينا أي مشاكل. 

هذا الى حد كبير عن هناك لتسلسل. وتسلسل هو بالتأكيد الأسلوب الذي هو سيكون الأكثر فعالية بالنسبة لك إذا يتم تخزين البيانات في جدول تجزئة. ولكن هذا المزيج من المصفوفات والقوائم المرتبطة معا لتشكيل جدول تجزئة حقا يحسن بشكل كبير على قدرتك لتخزين كميات كبيرة من البيانات، و بسرعة كبيرة وكفاءة البحث من خلال تلك البيانات. 

لا يزال هناك أكثر من هيكل البيانات الى هناك قد يكون حتى قليلا أفضل من حيث ضمان أن لدينا الإدراج أو الحذف، و بحث عن الأوقات حتى أسرع. وسنرى ذلك في شريط فيديو على محاولات. أنا دوغ ويد، وهذا هو CS50.