Original subtitles

غير معرف

[عزف الموسيقى]

غير معرف

>> دوغ لويد: الآن تعرف الكثير عن المصفوفات ،

وأنت تعرف الكثير عن القوائم المرتبطة.

وقد ناقشنا الإيجابيات والسلبيات ، لقد قمنا بذلك

ناقش أن القوائم المرتبطة يمكن أن تصبح أكبر وأصغر ،

لكنها تأخذ حجمًا أكبر.

المصفوفات أكثر سهولة في الاستخدام ، لكنها مقيدة في نفس القدر

حيث يتعين علينا ضبط حجم المصفوفة في البداية

ومن ثم نحن عالقون معها.

>> ولكن هذا ، لقد استنفدنا إلى حد كبير جميع موضوعاتنا

حول القوائم والمصفوفات المرتبطة.

أم لدينا؟

ربما يمكننا القيام بشيء أكثر إبداعًا.

وهذا النوع من فكرة جدول التجزئة.

>> لذلك في جدول التجزئة سنحاول دمج مصفوفة مع قائمة مرتبطة.

سنستفيد من مزايا المصفوفة ، مثل الوصول العشوائي ،

القدرة على الانتقال إلى عنصر المصفوفة 4 أو عنصر المصفوفة 8

دون الحاجة إلى تكرار ذلك عبر.

هذا سريع جدًا ، أليس كذلك؟

>> ولكننا نريد أيضًا أن تكون بنية بياناتنا قادرة على النمو والانكماش.

لسنا بحاجة ، لا نريد أن نكون مقيدين.

ونريد أن نكون قادرين على إضافة وإزالة الأشياء

بسهولة شديدة ، والتي إذا كنت تتذكرها ، فهي معقدة للغاية مع مصفوفة.

ويمكننا تسمية هذا الشيء الجديد بجدول التجزئة.

>> وإذا تم تنفيذها بشكل صحيح ، فإننا نوعا ما نأخذ

مزايا بنيتي البيانات التي رأيتها بالفعل ،

المصفوفات والقوائم المرتبطة.

يمكن أن يبدأ الإدراج في الميل نحو ثيتا 1.

ثيتا لم نناقشها حقًا ، لكن ثيتا هي مجرد حالة عادية ،

ما الذي سيحدث بالفعل.

لن يكون لديك دائمًا أسوأ سيناريو ،

ولن يكون لديك دائمًا أفضل سيناريو ، فما هو

السيناريو المتوسط؟

>> حسنًا ، متوسط ​​الإدراج في جدول التجزئة

يمكن أن تبدأ في الاقتراب من الوقت الثابت.

ويمكن أن يقترب الحذف من الوقت الثابت.

ويمكن أن يقترب البحث من الوقت الثابت.

هذا - ليس لدينا بنية بيانات حتى الآن يمكنها القيام بذلك ،

ولذا يبدو هذا بالفعل شيئًا رائعًا جدًا.

لقد قمنا بالفعل بتخفيف عيوب كل منها بمفردها.

>> للحصول على ترقية الأداء هذه ، نحن

بحاجة إلى إعادة التفكير في كيفية إضافة البيانات إلى الهيكل.

على وجه التحديد ، نريد أن تخبرنا البيانات نفسها

حيث يجب أن تذهب في الهيكل.

وإذا احتجنا بعد ذلك إلى معرفة ما إذا كان موجودًا في الهيكل ، وإذا أردنا العثور عليه ،

نريد أن ننظر إلى البيانات مرة أخرى وأن نكون قادرين على

باستخدام البيانات ، والوصول إليها بشكل عشوائي.

فقط من خلال النظر إلى البيانات التي يجب أن تكون لدينا

فكرة عن المكان الذي سنجده فيه بالضبط في جدول التجزئة.

>> الآن الجانب السلبي لجدول التجزئة هو أنهم حقًا

سيء جدًا في طلب البيانات أو فرزها.

وفي الواقع ، إذا بدأت في استخدامها للطلب أو الفرز

البيانات تفقد كل المزايا التي كنت تمتلكها سابقًا

كان من حيث الإدراج والحذف.

أصبح الوقت أقرب إلى ثيتا n ، ونحن في الأساس

تراجعت إلى قائمة مرتبطة.

ولذا فنحن نريد فقط استخدام جداول التجزئة إذا لم نهتم بذلك

سواء تم فرز البيانات.

للسياق الذي ستستخدمهم فيه في CS50

ربما لا تهتم بفرز البيانات.

>> إذن جدول التجزئة عبارة عن مزيج من قطعتين متميزتين

التي نعرفها.

الأولى هي دالة ، نسميها عادة دالة هاش.

وستقوم دالة التجزئة هذه بإرجاع بعض الأعداد الصحيحة غير السالبة ، والتي

نحن عادة نسمي رمز التجزئة ، حسنا؟

القطعة الثانية عبارة عن مصفوفة قادرة على تخزين البيانات من النوع نحن

تريد وضعها في بنية البيانات.

سنقوم بتأجيل عنصر القائمة المرتبطة في الوقت الحالي

وابدأ فقط بأساسيات جدول التجزئة لتجعلك تدور حوله ،

وبعد ذلك ربما نفجر عقلك قليلاً عندما نفعل ذلك

الجمع بين المصفوفات وربط القوائم معًا.

>> الفكرة الأساسية هي أننا نأخذ بعض البيانات.

نقوم بتشغيل تلك البيانات من خلال وظيفة التجزئة.

وهكذا تتم معالجة البيانات وتخرج رقمًا ، حسنًا؟

ثم باستخدام هذا الرقم ، نقوم فقط بتخزين البيانات

نريد تخزينها في المصفوفة في ذلك الموقع.

على سبيل المثال ، ربما يكون لدينا جدول تجزئة للسلاسل.

يحتوي على 10 عناصر فيه ، لذا يمكننا احتواء 10 سلاسل فيه.

>> لنفترض أننا نريد تجزئة جون.

إذن جون كالبيانات التي نريد إدراجها في جدول التجزئة هذا في مكان ما.

أين نضعها؟

حسنًا ، عادةً مع مصفوفة حتى الآن ربما

سيضعها في موقع الصفيف 0.

لكن لدينا الآن وظيفة التجزئة الجديدة هذه.

>> ولنفترض أننا نجحنا في تشغيل John من خلال دالة التجزئة هذه

وهو يبصق 4.

حسنًا ، هذا هو المكان الذي نريد وضع جون فيه.

نريد وضع John في موقع المصفوفة 4 ، لأننا إذا قمنا بتجزئة John مرة أخرى--

دعنا نقول لاحقًا أننا نريد البحث والاطلاع

إذا كان جون موجودًا في جدول التجزئة هذا - كل ما يتعين علينا القيام به

يتم تشغيله من خلال نفس دالة التجزئة ، والحصول على الرقم 4 ،

والتمكن من العثور على John على الفور في بنية البيانات لدينا.

انها فعلا جميلة.

>> لنفترض أننا نفعل ذلك الآن مرة أخرى ، نريد تجزئة بول.

نريد إضافة بول إلى جدول التجزئة هذا.

لنفترض أننا نجحنا هذه المرة في تشغيل Paul من خلال دالة التجزئة ،

كود التجزئة الذي تم إنشاؤه هو 6.

حسنًا ، يمكننا الآن وضع بول في موقع المصفوفة 6.

وإذا احتجنا إلى البحث عما إذا كان بول موجودًا في جدول التجزئة هذا ،

كل ما علينا فعله هو تشغيل Paul من خلال دالة التجزئة مرة أخرى

وسنخرج 6 مرة أخرى.

>> وبعد ذلك ننظر فقط إلى موقع المصفوفة 6.

هل بولس هناك؟

إذا كان الأمر كذلك ، فهو في طاولة التجزئة.

أليس بولس هناك؟

إنه ليس في طاولة التجزئة.

إنه أمر بسيط ومباشر.

>> الآن كيف تحدد دالة التجزئة؟

حسنًا ، ليس هناك حد لعدد وظائف التجزئة الممكنة.

في الواقع ، هناك عدد من الأشياء الجيدة حقًا على الإنترنت.

هناك عدد من الأشياء السيئة حقًا على الإنترنت.

من السهل أيضًا كتابة كلمة سيئة.

>> إذن ما الذي تتكون منه دالة تجزئة جيدة ، أليس كذلك؟

حسنًا ، يجب أن تستخدم دالة التجزئة الجيدة البيانات التي يتم تجزئتها فقط ،

وجميع البيانات التي يتم تجزئتها.

لذلك لا نريد استخدام أي شيء - نحن لا ندمج أي شيء

بخلاف البيانات.

ونريد استخدام كل البيانات.

لا نريد استخدام جزء منه فقط ، نريد استخدام كل ذلك.

يجب أن تكون دالة التجزئة حتمية أيضًا.

ماذا يعني ذلك؟

حسنًا ، هذا يعني أنه في كل مرة نمرر فيها نفس قطعة البيانات بالضبط

في وظيفة التجزئة ، نحصل دائمًا على نفس رمز التجزئة.

إذا قمت بتمرير John إلى دالة التجزئة ، سأخرج 4.

يجب أن أكون قادرًا على القيام بذلك 10000 مرة وسأحصل دائمًا على 4.

لذلك لا يمكن تضمين أي أرقام عشوائية بشكل فعال في جداول التجزئة لدينا--

في وظائف التجزئة لدينا.

>> يجب أن تقوم دالة التجزئة أيضًا بتوزيع البيانات بشكل موحد.

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

ربما هذا ليس رائعًا ، أليس كذلك؟

ربما تريد زيادة مجموعة أكواد التجزئة.

يمكن أيضًا توزيع الأشياء في جميع أنحاء الطاولة.

وسيكون رائعًا أيضًا إذا كانت البيانات المتشابهة حقًا ، مثل جون وجوناثان ،

ربما تم توزيعها لوزن مواقع مختلفة في جدول التجزئة.

سيكون ذلك ميزة جيدة.

>> هنا مثال لدالة التجزئة.

لقد كتبت هذا في وقت سابق.

إنها ليست دالة تجزئة جيدة بشكل خاص

لأسباب لا تحتمل الدخول في الوقت الحالي.

لكن هل ترى ما يحدث هنا؟

يبدو أننا نعلن عن متغير يسمى sum ونضبطه على 0.

ومن ثم يبدو أنني أفعل شيئًا طالما أن strstr [j] غير متساوٍ

للشرطة المائلة للخلف 0.

ماذا أفعل هناك؟

>> هذه في الأساس مجرد طريقة أخرى للتنفيذ [؟ strl؟]

واكتشاف وصولك إلى نهاية السلسلة.

لذلك لا يتعين علي حساب طول السلسلة ،

أنا أستخدم فقط عندما أصبت بشرطة مائلة عكسية 0 حرف أعرفه

لقد وصلت إلى نهاية السلسلة.

وبعد ذلك سأستمر في التكرار خلال تلك السلسلة ،

إضافة strstr [j] للمجموع ، ثم في نهاية اليوم ستعيد المجموع mod

HASH_MAX.

>> في الأساس كل ما تقوم به دالة التجزئة هو الجمع

كل قيم ASCII لسلسلتي ، وبعد ذلك

إرجاع بعض رمز التجزئة المعدل بواسطة HASH_MAX.

ربما يكون حجم صفيفتي ، أليس كذلك؟

لا أريد الحصول على أكواد التجزئة إذا كان حجم مصفوفي 10 ،

لا أريد الحصول على رموز التجزئة 11 ، 12 ،

13 ، لا يمكنني وضع الأشياء في تلك المواقع من المصفوفة ،

سيكون ذلك غير قانوني.

كنت أعاني من خطأ تجزئة.

>> الآن هنا جانب سريع آخر.

بشكل عام ، ربما لن ترغب في كتابة وظائف التجزئة الخاصة بك.

إنه في الواقع نوع من الفن وليس علمًا.

وهناك الكثير من الأمور التي تتعلق بهم.

الإنترنت ، كما قلت ، مليء بوظائف التجزئة الجيدة حقًا ،

ويجب عليك استخدام الإنترنت للعثور على وظائف التجزئة لأنها حقًا

مجرد نوع من مضيعة غير ضرورية للوقت لإنشاء وقتك الخاص.

>> يمكنك كتابة أشياء بسيطة لأغراض الاختبار.

ولكن عندما تبدأ بالفعل في تجزئة البيانات وتخزينها

في جدول التجزئة الذي ربما تريده

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

إذا كنت تفعل ذلك فقط تأكد من الاستشهاد بمصادرك.

لا يوجد سبب لسرقة أي شيء هنا.

>> مجتمع علوم الكمبيوتر ينمو بالتأكيد ، ويقدر حقًا

مفتوح المصدر ، ومن المهم حقًا الاستشهاد بمصادرك حتى يتمكن الأشخاص من ذلك

يمكنهم الحصول على الإسناد للعمل الذي يقومون به

تفعل لصالح المجتمع.

لذلك تأكد دائمًا - وليس فقط للتجزئة

الوظائف ، ولكن بشكل عام عندما تستخدم رمزًا من مصدر خارجي ،

اذكر مصدرك دائمًا.

امنح الفضل للشخص الذي قام ببعض الأعمال حتى لا تضطر إلى ذلك.

>> حسنًا ، فلنراجع جدول التجزئة هذا لمدة ثانية.

هذا هو المكان الذي توقفنا فيه بعد أن أدخلنا

يوحنا وبولس في جدول التجزئة هذا.

هل ترى مشكلة هنا؟

قد ترى اثنين.

لكن على وجه الخصوص ، هل ترى هذه المشكلة المحتملة؟

>> ماذا لو قمت بتجزئة Ringo ، واتضح ذلك بعد المعالجة

تلك البيانات من خلال وظيفة التجزئة قام Ringo أيضًا بإنشاء رمز التجزئة 6.

لقد حصلت بالفعل على بيانات في رمز التجزئة - موقع الصفيف 6.

لذا من المحتمل أن تكون مشكلة بالنسبة لي الآن ، أليس كذلك؟

>> نسمي هذا تصادمًا.

ويحدث التصادم عندما يتم تشغيل قطعتين من البيانات عبر نفس التجزئة

وظيفة تؤدي إلى نفس رمز التجزئة.

من المفترض أننا ما زلنا نرغب في إدخال كلا الجزأين من البيانات في جدول التجزئة ،

وإلا فلن نقوم بتشغيل Ringo بشكل تعسفي من خلال وظيفة التجزئة.

من المفترض أننا نريد إدخال رينغو في تلك المجموعة.

>> كيف يمكننا القيام بذلك ، إذا قدم هو وبولس رمز التجزئة 6؟

لا نريد استبدال بول ، نريد أن يكون بولس هناك أيضًا.

لذلك نحن بحاجة إلى إيجاد طريقة لإدخال العناصر في جدول التجزئة

لا يزال يحافظ على الإدراج السريع والبحث السريع.

وإحدى طرق التعامل معها هي القيام بشيء يسمى التحقيق الخطي.

>> باستخدام هذه الطريقة إذا حدث تصادم ، حسنًا ، ماذا نفعل؟

حسنًا ، لا يمكننا وضعه في موقع المصفوفة 6 ، أو أي كود تجزئة تم إنشاؤه ،

دعنا نضعه في hashcode زائد 1.

وإذا كان هذا ممتلئًا ، فلنضعه في رمز التجزئة زائد 2.

فائدة هذا الوجود إذا لم يكن بالضبط حيث نعتقد أنه موجود ،

وعلينا أن نبدأ البحث ، ربما لا نضطر إلى الذهاب بعيدًا.

ربما لا يتعين علينا البحث في جميع العناصر n لجدول التجزئة.

ربما يتعين علينا البحث عن اثنين منهم.

>> ولذا فنحن ما زلنا نتجه نحو اقتراب متوسط ​​الحالة هذا من 1 مقابل

قريب من n ، لذلك ربما سيعمل ذلك.

لذلك دعونا نرى كيف يمكن أن يحدث هذا في الواقع.

ودعونا نرى ما إذا كان بإمكاننا اكتشاف المشكلة التي قد تحدث هنا.

>> دعنا نقول أننا هاش بارت.

سنقوم الآن بتشغيل مجموعة جديدة من السلاسل من خلال دالة التجزئة ،

ونقوم بتشغيل Bart من خلال دالة التجزئة ، نحصل على رمز التجزئة 6.

نلقي نظرة ، نرى 6 فارغة ، لذا يمكننا وضع بارت هناك.

>> الآن قمنا بتجزئة ليزا وهذا أيضًا يولد رمز التجزئة 6.

حسنًا ، بعد أن استخدمنا طريقة الفحص الخطية هذه ، نبدأ من 6 ،

نرى أن 6 ممتلئة.

لا يمكننا وضع ليزا في الرقم 6.

إذن، أين نذهب؟

دعنا ننتقل إلى 7.

رقم 7 فارغ ، لذلك يعمل.

لذلك دعونا نضع ليزا هناك.

>> الآن قمنا بتجزئة هومر ونحصل على 7.

حسنًا ، نعلم جيدًا أن الرقم 7 ممتلئ الآن ، لذا لا يمكننا وضع هومر هناك.

فلننتقل إلى 8.

8 متاح؟

نعم ، و 8 تقترب من 7 ، لذلك إذا كان علينا بدء البحث ، فنحن

لن تضطر إلى الذهاب بعيدا.

لذلك دعونا نضع هومر في المرتبة الثامنة.

>> الآن نقوم بتجزئة ماجي وإرجاع 3 ، الحمد لله

يمكننا فقط وضع ماجي هناك.

لا يتعين علينا القيام بأي نوع من التحقيق في ذلك.

الآن نقوم بتجزئة Marge ، وترجع Marge أيضًا 6.

>> حسنًا 6 ممتلئ ، 7 ممتلئ ، 8 ممتلئ ، 9 ، حسنًا الحمد لله ، 9 فارغ.

يمكنني وضع مارج في التاسعة.

بالفعل يمكننا أن نرى أننا بدأنا نواجه هذه المشكلة حيث نحن الآن

البدء في تمديد الأشياء بعيدًا عن أكواد التجزئة الخاصة بهم.

وأن ثيتا 1 ، تلك الحالة المتوسطة لكونها وقتًا ثابتًا ،

بدأ في الحصول على المزيد - بدأ يميل أكثر قليلاً

نحو ثيتا من ن.

لقد بدأنا نفقد ميزة جداول التجزئة.

>> هذه المشكلة التي رأيناها للتو تسمى التجميع.

والشيء السيئ حقًا في التجميع هو أنك مرة واحدة الآن

وجود عنصرين جنبًا إلى جنب مما يزيد من احتمالية حدوثه ،

لديك فرصة مضاعفة ، أنك ذاهب

لتصادم آخر مع تلك المجموعة ،

وسوف تنمو الكتلة بواحد.

وستستمر في النمو وزيادة احتمالية حدوث تصادم.

وفي النهاية يكون الأمر سيئًا مثل عدم فرز البيانات على الإطلاق.

>> لكن المشكلة الأخرى هي أننا ما زلنا ، وحتى الآن حتى هذه اللحظة ،

لقد فهمنا نوعًا ما ما هو جدول التجزئة ،

لا يزال لدينا متسع لـ 10 سلاسل فقط.

إذا أردنا الاستمرار في تجزئة مواطني سبرينغفيلد ،

يمكننا فقط الحصول على 10 منهم هناك.

وإذا حاولنا إضافة 11 أو 12 ، فليس لدينا مكان لوضعهما.

يمكننا فقط أن نلتف في دوائر نحاول إيجاد مكان فارغ ،

وربما نتعثر في حلقة لا نهائية.

>> لذا فإن هذا النوع من الإقراض لفكرة شيء يسمى التسلسل.

وهذا هو المكان الذي سنقوم فيه بإعادة القوائم المرتبطة إلى الصورة.

ماذا لو بدلاً من تخزين البيانات نفسها في المصفوفة ،

يمكن أن يحتوي كل عنصر من عناصر المصفوفة على أجزاء متعددة من البيانات؟

حسنًا ، هذا غير منطقي ، أليس كذلك؟

نحن نعلم أن المصفوفة يمكن أن تحتوي فقط - كل عنصر من عناصر المصفوفة

يمكن أن تحتوي على جزء واحد فقط من البيانات من هذا النوع من البيانات.

>> ولكن ماذا لو كان نوع البيانات هذا عبارة عن قائمة مرتبطة ، أليس كذلك؟

فماذا لو كان كل عنصر من عناصر المصفوفة

مؤشر إلى رأس قائمة مرتبطة؟

وبعد ذلك يمكننا بناء تلك القوائم المرتبطة

وتنميتها بشكل تعسفي ، لأن القوائم المرتبطة تسمح بذلك

علينا أن ننمو ونتقلص بمرونة أكبر بكثير من المصفوفة.

إذن ماذا لو استخدمنا الآن ، استفدنا من هذا ، أليس كذلك؟

نبدأ في تنمية هذه السلاسل خارج مواقع المصفوفة هذه.

>> يمكننا الآن استيعاب كمية لا حصر لها من البيانات ، أو غير محدودة ،

كمية عشوائية من البيانات ، في جدول التجزئة الخاص بنا

دون الوقوع في مشكلة الاصطدام.

لقد أزلنا أيضًا التجميع من خلال القيام بذلك.

ونعلم جيدًا أنه عندما ندرج في قائمة مرتبطة ، إذا كنت تتذكر

من الفيديو الخاص بنا في القوائم المرتبطة والقوائم المرتبطة بشكل فردي والقوائم المرتبطة بشكل مضاعف ،

إنها عملية زمنية ثابتة.

نحن فقط نضيف إلى المقدمة.

>> وللبحث ، نحن نعلم جيدًا أن البحث في قائمة مرتبطة

يمكن أن يكون مشكلة ، أليس كذلك؟

علينا البحث من خلاله من البداية إلى النهاية.

لا يوجد وصول عشوائي في قائمة مرتبطة.

ولكن إذا بدلاً من وجود قائمة مرتبطة واحدة حيث يكون البحث هو O لـ n ،

لدينا الآن 10 قوائم مرتبطة ، أو 1000 قائمة مرتبطة ،

الآن هو O لـ n مقسومًا على 10 ، أو O لـ n مقسومًا على 1000.

>> وبينما كنا نتحدث نظريًا عن التعقيد

نتجاهل الثوابت ، فهذه الأشياء مهمة في الواقع ،

الصحيح؟

في الواقع سوف نلاحظ أن هذا يحدث

لتشغيل أسرع 10 مرات ، أو 1000 مرة أسرع ،

لأننا نوزع سلسلة طويلة واحدة على 1000 سلسلة أصغر.

وهكذا في كل مرة يتعين علينا البحث من خلال واحدة من تلك السلاسل يمكننا ذلك

تجاهل 999 سلسلة لا نهتم بها ، وابحث فقط عن تلك السلسلة.

>> وهو في المتوسط ​​أقصر بـ 1000 مرة.

ولذا فإننا ما زلنا نميل نوعًا ما نحو هذه الحالة المتوسطة

من كوننا وقتًا ثابتًا ، ولكن فقط لأننا نستفيد

القسمة على عامل ثابت ضخم.

دعونا نرى كيف سيبدو هذا في الواقع.

لذلك كان هذا هو جدول التجزئة الذي كان لدينا قبل أن أعلنا عن جدول التجزئة

كان قادرًا على تخزين 10 سلاسل.

لن نفعل ذلك بعد الآن.

نحن نعلم بالفعل حدود هذه الطريقة.

الآن جدول التجزئة الخاص بنا سيكون مصفوفة من 10 عقد ، مؤشرات

لرؤساء القوائم المرتبطة.

>> وهو الآن لاغٍ.

كل واحدة من هذه المؤشرات العشر خالية.

لا يوجد شيء في جدول التجزئة لدينا الآن.

>> لنبدأ الآن في وضع بعض الأشياء في جدول التجزئة هذا.

ودعونا نرى كيف ستفيدنا هذه الطريقة قليلاً.

لنقم الآن بتجزئة جوي.

سنقوم بتشغيل السلسلة Joey من خلال دالة تجزئة وسنقوم بإرجاع 6.

حسنا ماذا نفعل الان؟

>> حسنًا ، نعمل الآن مع القوائم المرتبطة ، نحن لا نعمل مع المصفوفات.

وعندما نعمل مع القوائم المرتبطة نحن

نعلم أننا بحاجة إلى البدء ديناميكيًا في تخصيص المساحة وبناء السلاسل.

هذا نوع من الكيفية - هذه هي العناصر الأساسية لبناء قائمة مرتبطة.

لذلك دعونا نخصص مساحة ديناميكيًا لـ Joey ،

ثم نضيفه إلى السلسلة.

>> لذا انظر الآن إلى ما فعلناه.

عندما قمنا بتجزئة جوي ، حصلنا على رمز التجزئة 6.

الآن يشير المؤشر في موقع الصفيف 6 إلى رأس قائمة مرتبطة ،

وهو الآن العنصر الوحيد في القائمة المرتبطة.

والعقدة في تلك القائمة المرتبطة هي Joey.

>> لذا إذا احتجنا إلى البحث عن Joey لاحقًا ، فسنقوم بتجزئة Joey مرة أخرى ،

نحصل على 6 مرة أخرى لأن دالة التجزئة لدينا حتمية.

وبعد ذلك نبدأ على رأس القائمة المرتبطة المشار إليها

إلى عن طريق موقع المصفوفة 6 ، ويمكننا التكرار

عبر محاولة العثور على جوي.

وإذا قمنا ببناء جدول التجزئة الخاص بنا بشكل فعال ،

ووظيفة التجزئة لدينا بشكل فعال لتوزيع البيانات بشكل جيد ،

في المتوسط ​​، كل من تلك القوائم المرتبطة في كل موقع مصفوفة

سيكون حجمه 1/10 إذا كان لدينا واحد ضخم

قائمة مرتبطة بكل شيء بداخلها.

>> إذا وزعنا تلك القائمة المرتبطة الضخمة عبر 10 قوائم مرتبطة

ستكون كل قائمة بحجم 1/10.

وبالتالي أسرع 10 مرات في البحث.

لذلك دعونا نفعل هذا مرة أخرى.

دعونا الآن تجزئة روس.

>> ولنفترض أن روس ، عندما نفعل ذلك كود التجزئة الذي نحصل عليه هو 2.

حسنًا ، نخصص عقدة جديدة ديناميكيًا ، ونضع روس في تلك العقدة ،

ونقول الآن موقع المصفوفة 2 ، بدلاً من الإشارة إلى الصفر ،

يشير إلى رأس قائمة مرتبطة العقدة الوحيدة هي روس.

ويمكننا القيام بذلك مرة أخرى ، يمكننا تجزئة راشيل والحصول على رمز التجزئة 4.

malloc عقدة جديدة ، ضع راشيل في العقدة ، وقل موقع مصفوفة

4 يشير الآن إلى رأس القائمة المرتبطة التي

العنصر الوحيد هو راشيل.

>> حسنًا ولكن ماذا يحدث إذا حدث تصادم؟

دعونا نرى كيف نتعامل مع الاصطدامات باستخدام طريقة التسلسل المنفصلة.

دعونا نقسم فيبي.

نحصل على رمز التجزئة 6.

في مثالنا السابق كنا نقوم فقط بتخزين السلاسل في المصفوفة.

كانت هذه مشكلة.

>> لا نريد ضرب جوي ، وقد فعلنا ذلك بالفعل

رأينا أنه يمكننا الحصول على بعض مشاكل التجميع إذا حاولنا خطوة

من خلال والتحقيق.

ولكن ماذا لو تعاملنا مع هذا النوع بنفس الطريقة ، أليس كذلك؟

إنه يشبه تمامًا إضافة عنصر إلى رأس قائمة مرتبطة.

دعونا فقط مساحة malloc لفيبي.

>> سنقول أن مؤشر فيبي التالي يشير إلى الرأس القديم للقائمة المرتبطة ،

ثم 6 يشير فقط إلى الرئيس الجديد للقائمة المرتبطة.

والآن انظر ، لقد غيرنا فيبي في.

يمكننا الآن تخزين عنصرين باستخدام رمز التجزئة 6 ،

وليس لدينا أي مشاكل.

>> هذا إلى حد كبير كل ما في السلاسل.

And chaining is definitely the method that's

going to be most effective for you if you are storing data in a hash table.

But this combination of arrays and linked lists

together to form a hash table really dramatically improves your ability

to store large amounts of data, and very quickly and efficiently search

through that data.

>> There's still one more data structure out there

that might even be a bit better in terms of guaranteeing

that our insertion, deletion, and look up times are even faster.

And we'll see that in a video on tries.

I'm Doug Lloyd, this is CS50.

undefined