Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
00:00:00,000 --> 00:00:00,500
غير معرف
2
00:00:00,500 --> 00:00:01,900
[عزف الموسيقى]
3
00:00:01,900 --> 00:00:05,710
غير معرف
4
00:00:05,710 --> 00:00:09,150
>> دوغ لويد: الآن تعرف الكثير عن المصفوفات ،
5
00:00:09,150 --> 00:00:11,610
وأنت تعرف الكثير عن القوائم المرتبطة.
6
00:00:11,610 --> 00:00:13,650
وقد ناقشنا الإيجابيات والسلبيات ، لقد قمنا بذلك
7
00:00:13,650 --> 00:00:16,620
ناقش أن القوائم المرتبطة يمكن أن تصبح أكبر وأصغر ،
8
00:00:16,620 --> 00:00:18,630
لكنها تأخذ حجمًا أكبر.
9
00:00:18,630 --> 00:00:22,359
المصفوفات أكثر سهولة في الاستخدام ، لكنها مقيدة في نفس القدر
10
00:00:22,359 --> 00:00:24,900
حيث يتعين علينا ضبط حجم المصفوفة في البداية
11
00:00:24,900 --> 00:00:26,910
ومن ثم نحن عالقون معها.
12
00:00:26,910 --> 00:00:30,470
>> ولكن هذا ، لقد استنفدنا إلى حد كبير جميع موضوعاتنا
13
00:00:30,470 --> 00:00:33,040
حول القوائم والمصفوفات المرتبطة.
14
00:00:33,040 --> 00:00:34,950
أم لدينا؟
15
00:00:34,950 --> 00:00:37,720
ربما يمكننا القيام بشيء أكثر إبداعًا.
16
00:00:37,720 --> 00:00:40,950
وهذا النوع من فكرة جدول التجزئة.
17
00:00:40,950 --> 00:00:46,680
>> لذلك في جدول التجزئة سنحاول دمج مصفوفة مع قائمة مرتبطة.
18
00:00:46,680 --> 00:00:49,520
سنستفيد من مزايا المصفوفة ، مثل الوصول العشوائي ،
19
00:00:49,520 --> 00:00:53,510
القدرة على الانتقال إلى عنصر المصفوفة 4 أو عنصر المصفوفة 8
20
00:00:53,510 --> 00:00:55,560
دون الحاجة إلى تكرار ذلك عبر.
21
00:00:55,560 --> 00:00:57,260
هذا سريع جدًا ، أليس كذلك؟
22
00:00:57,260 --> 00:01:00,714
>> ولكننا نريد أيضًا أن تكون بنية بياناتنا قادرة على النمو والانكماش.
23
00:01:00,714 --> 00:01:02,630
لسنا بحاجة ، لا نريد أن نكون مقيدين.
24
00:01:02,630 --> 00:01:04,588
ونريد أن نكون قادرين على إضافة وإزالة الأشياء
25
00:01:04,588 --> 00:01:08,430
بسهولة شديدة ، والتي إذا كنت تتذكرها ، فهي معقدة للغاية مع مصفوفة.
26
00:01:08,430 --> 00:01:11,650
ويمكننا تسمية هذا الشيء الجديد بجدول التجزئة.
27
00:01:11,650 --> 00:01:15,190
>> وإذا تم تنفيذها بشكل صحيح ، فإننا نوعا ما نأخذ
28
00:01:15,190 --> 00:01:18,150
مزايا بنيتي البيانات التي رأيتها بالفعل ،
29
00:01:18,150 --> 00:01:19,880
المصفوفات والقوائم المرتبطة.
30
00:01:19,880 --> 00:01:23,070
يمكن أن يبدأ الإدراج في الميل نحو ثيتا 1.
31
00:01:23,070 --> 00:01:26,207
ثيتا لم نناقشها حقًا ، لكن ثيتا هي مجرد حالة عادية ،
32
00:01:26,207 --> 00:01:27,540
ما الذي سيحدث بالفعل.
33
00:01:27,540 --> 00:01:29,680
لن يكون لديك دائمًا أسوأ سيناريو ،
34
00:01:29,680 --> 00:01:32,555
ولن يكون لديك دائمًا أفضل سيناريو ، فما هو
35
00:01:32,555 --> 00:01:33,900
السيناريو المتوسط؟
36
00:01:33,900 --> 00:01:36,500
>> حسنًا ، متوسط الإدراج في جدول التجزئة
37
00:01:36,500 --> 00:01:39,370
يمكن أن تبدأ في الاقتراب من الوقت الثابت.
38
00:01:39,370 --> 00:01:41,570
ويمكن أن يقترب الحذف من الوقت الثابت.
39
00:01:41,570 --> 00:01:44,440
ويمكن أن يقترب البحث من الوقت الثابت.
40
00:01:44,440 --> 00:01:48,600
هذا - ليس لدينا بنية بيانات حتى الآن يمكنها القيام بذلك ،
41
00:01:48,600 --> 00:01:51,180
ولذا يبدو هذا بالفعل شيئًا رائعًا جدًا.
42
00:01:51,180 --> 00:01:57,010
لقد قمنا بالفعل بتخفيف عيوب كل منها بمفردها.
43
00:01:57,010 --> 00:01:59,160
>> للحصول على ترقية الأداء هذه ، نحن
44
00:01:59,160 --> 00:02:03,580
بحاجة إلى إعادة التفكير في كيفية إضافة البيانات إلى الهيكل.
45
00:02:03,580 --> 00:02:07,380
على وجه التحديد ، نريد أن تخبرنا البيانات نفسها
46
00:02:07,380 --> 00:02:09,725
حيث يجب أن تذهب في الهيكل.
47
00:02:09,725 --> 00:02:12,850
وإذا احتجنا بعد ذلك إلى معرفة ما إذا كان موجودًا في الهيكل ، وإذا أردنا العثور عليه ،
48
00:02:12,850 --> 00:02:16,610
نريد أن ننظر إلى البيانات مرة أخرى وأن نكون قادرين على
49
00:02:16,610 --> 00:02:18,910
باستخدام البيانات ، والوصول إليها بشكل عشوائي.
50
00:02:18,910 --> 00:02:20,700
فقط من خلال النظر إلى البيانات التي يجب أن تكون لدينا
51
00:02:20,700 --> 00:02:25,890
فكرة عن المكان الذي سنجده فيه بالضبط في جدول التجزئة.
52
00:02:25,890 --> 00:02:28,770
>> الآن الجانب السلبي لجدول التجزئة هو أنهم حقًا
53
00:02:28,770 --> 00:02:31,770
سيء جدًا في طلب البيانات أو فرزها.
54
00:02:31,770 --> 00:02:34,970
وفي الواقع ، إذا بدأت في استخدامها للطلب أو الفرز
55
00:02:34,970 --> 00:02:37,990
البيانات تفقد كل المزايا التي كنت تمتلكها سابقًا
56
00:02:37,990 --> 00:02:40,710
كان من حيث الإدراج والحذف.
57
00:02:40,710 --> 00:02:44,060
أصبح الوقت أقرب إلى ثيتا n ، ونحن في الأساس
58
00:02:44,060 --> 00:02:45,530
تراجعت إلى قائمة مرتبطة.
59
00:02:45,530 --> 00:02:48,850
ولذا فنحن نريد فقط استخدام جداول التجزئة إذا لم نهتم بذلك
60
00:02:48,850 --> 00:02:51,490
سواء تم فرز البيانات.
61
00:02:51,490 --> 00:02:54,290
للسياق الذي ستستخدمهم فيه في CS50
62
00:02:54,290 --> 00:02:58,900
ربما لا تهتم بفرز البيانات.
63
00:02:58,900 --> 00:03:03,170
>> إذن جدول التجزئة عبارة عن مزيج من قطعتين متميزتين
64
00:03:03,170 --> 00:03:04,980
التي نعرفها.
65
00:03:04,980 --> 00:03:07,930
الأولى هي دالة ، نسميها عادة دالة هاش.
66
00:03:07,930 --> 00:03:11,760
وستقوم دالة التجزئة هذه بإرجاع بعض الأعداد الصحيحة غير السالبة ، والتي
67
00:03:11,760 --> 00:03:14,870
نحن عادة نسمي رمز التجزئة ، حسنا؟
68
00:03:14,870 --> 00:03:20,230
القطعة الثانية عبارة عن مصفوفة قادرة على تخزين البيانات من النوع نحن
69
00:03:20,230 --> 00:03:22,190
تريد وضعها في بنية البيانات.
70
00:03:22,190 --> 00:03:24,310
سنقوم بتأجيل عنصر القائمة المرتبطة في الوقت الحالي
71
00:03:24,310 --> 00:03:27,810
وابدأ فقط بأساسيات جدول التجزئة لتجعلك تدور حوله ،
72
00:03:27,810 --> 00:03:30,210
وبعد ذلك ربما نفجر عقلك قليلاً عندما نفعل ذلك
73
00:03:30,210 --> 00:03:32,920
الجمع بين المصفوفات وربط القوائم معًا.
74
00:03:32,920 --> 00:03:35,590
>> الفكرة الأساسية هي أننا نأخذ بعض البيانات.
75
00:03:35,590 --> 00:03:37,860
نقوم بتشغيل تلك البيانات من خلال وظيفة التجزئة.
76
00:03:37,860 --> 00:03:41,980
وهكذا تتم معالجة البيانات وتخرج رقمًا ، حسنًا؟
77
00:03:41,980 --> 00:03:44,890
ثم باستخدام هذا الرقم ، نقوم فقط بتخزين البيانات
78
00:03:44,890 --> 00:03:48,930
نريد تخزينها في المصفوفة في ذلك الموقع.
79
00:03:48,930 --> 00:03:53,990
على سبيل المثال ، ربما يكون لدينا جدول تجزئة للسلاسل.
80
00:03:53,990 --> 00:03:57,350
يحتوي على 10 عناصر فيه ، لذا يمكننا احتواء 10 سلاسل فيه.
81
00:03:57,350 --> 00:03:59,320
>> لنفترض أننا نريد تجزئة جون.
82
00:03:59,320 --> 00:04:02,979
إذن جون كالبيانات التي نريد إدراجها في جدول التجزئة هذا في مكان ما.
83
00:04:02,979 --> 00:04:03,770
أين نضعها؟
84
00:04:03,770 --> 00:04:05,728
حسنًا ، عادةً مع مصفوفة حتى الآن ربما
85
00:04:05,728 --> 00:04:07,610
سيضعها في موقع الصفيف 0.
86
00:04:07,610 --> 00:04:09,960
لكن لدينا الآن وظيفة التجزئة الجديدة هذه.
87
00:04:09,960 --> 00:04:13,180
>> ولنفترض أننا نجحنا في تشغيل John من خلال دالة التجزئة هذه
88
00:04:13,180 --> 00:04:15,417
وهو يبصق 4.
89
00:04:15,417 --> 00:04:17,500
حسنًا ، هذا هو المكان الذي نريد وضع جون فيه.
90
00:04:17,500 --> 00:04:22,050
نريد وضع John في موقع المصفوفة 4 ، لأننا إذا قمنا بتجزئة John مرة أخرى--
91
00:04:22,050 --> 00:04:23,810
دعنا نقول لاحقًا أننا نريد البحث والاطلاع
92
00:04:23,810 --> 00:04:26,960
إذا كان جون موجودًا في جدول التجزئة هذا - كل ما يتعين علينا القيام به
93
00:04:26,960 --> 00:04:30,310
يتم تشغيله من خلال نفس دالة التجزئة ، والحصول على الرقم 4 ،
94
00:04:30,310 --> 00:04:33,929
والتمكن من العثور على John على الفور في بنية البيانات لدينا.
95
00:04:33,929 --> 00:04:34,720
انها فعلا جميلة.
96
00:04:34,720 --> 00:04:36,928
>> لنفترض أننا نفعل ذلك الآن مرة أخرى ، نريد تجزئة بول.
97
00:04:36,928 --> 00:04:39,446
نريد إضافة بول إلى جدول التجزئة هذا.
98
00:04:39,446 --> 00:04:42,070
لنفترض أننا نجحنا هذه المرة في تشغيل Paul من خلال دالة التجزئة ،
99
00:04:42,070 --> 00:04:44,600
كود التجزئة الذي تم إنشاؤه هو 6.
100
00:04:44,600 --> 00:04:47,340
حسنًا ، يمكننا الآن وضع بول في موقع المصفوفة 6.
101
00:04:47,340 --> 00:04:50,040
وإذا احتجنا إلى البحث عما إذا كان بول موجودًا في جدول التجزئة هذا ،
102
00:04:50,040 --> 00:04:53,900
كل ما علينا فعله هو تشغيل Paul من خلال دالة التجزئة مرة أخرى
103
00:04:53,900 --> 00:04:55,830
وسنخرج 6 مرة أخرى.
104
00:04:55,830 --> 00:04:57,590
>> وبعد ذلك ننظر فقط إلى موقع المصفوفة 6.
105
00:04:57,590 --> 00:04:58,910
هل بولس هناك؟
106
00:04:58,910 --> 00:05:00,160
إذا كان الأمر كذلك ، فهو في طاولة التجزئة.
107
00:05:00,160 --> 00:05:01,875
أليس بولس هناك؟
108
00:05:01,875 --> 00:05:03,000
إنه ليس في طاولة التجزئة.
109
00:05:03,000 --> 00:05:05,720
إنه أمر بسيط ومباشر.
110
00:05:05,720 --> 00:05:07,770
>> الآن كيف تحدد دالة التجزئة؟
111
00:05:07,770 --> 00:05:11,460
حسنًا ، ليس هناك حد لعدد وظائف التجزئة الممكنة.
112
00:05:11,460 --> 00:05:14,350
في الواقع ، هناك عدد من الأشياء الجيدة حقًا على الإنترنت.
113
00:05:14,350 --> 00:05:17,560
هناك عدد من الأشياء السيئة حقًا على الإنترنت.
114
00:05:17,560 --> 00:05:21,080
من السهل أيضًا كتابة كلمة سيئة.
115
00:05:21,080 --> 00:05:23,760
>> إذن ما الذي تتكون منه دالة تجزئة جيدة ، أليس كذلك؟
116
00:05:23,760 --> 00:05:27,280
حسنًا ، يجب أن تستخدم دالة التجزئة الجيدة البيانات التي يتم تجزئتها فقط ،
117
00:05:27,280 --> 00:05:29,420
وجميع البيانات التي يتم تجزئتها.
118
00:05:29,420 --> 00:05:32,500
لذلك لا نريد استخدام أي شيء - نحن لا ندمج أي شيء
119
00:05:32,500 --> 00:05:35,560
بخلاف البيانات.
120
00:05:35,560 --> 00:05:37,080
ونريد استخدام كل البيانات.
121
00:05:37,080 --> 00:05:39,830
لا نريد استخدام جزء منه فقط ، نريد استخدام كل ذلك.
122
00:05:39,830 --> 00:05:41,710
يجب أن تكون دالة التجزئة حتمية أيضًا.
123
00:05:41,710 --> 00:05:42,550
ماذا يعني ذلك؟
124
00:05:42,550 --> 00:05:46,200
حسنًا ، هذا يعني أنه في كل مرة نمرر فيها نفس قطعة البيانات بالضبط
125
00:05:46,200 --> 00:05:50,040
في وظيفة التجزئة ، نحصل دائمًا على نفس رمز التجزئة.
126
00:05:50,040 --> 00:05:52,870
إذا قمت بتمرير John إلى دالة التجزئة ، سأخرج 4.
127
00:05:52,870 --> 00:05:56,110
يجب أن أكون قادرًا على القيام بذلك 10000 مرة وسأحصل دائمًا على 4.
128
00:05:56,110 --> 00:06:00,810
لذلك لا يمكن تضمين أي أرقام عشوائية بشكل فعال في جداول التجزئة لدينا--
129
00:06:00,810 --> 00:06:02,750
في وظائف التجزئة لدينا.
130
00:06:02,750 --> 00:06:05,750
>> يجب أن تقوم دالة التجزئة أيضًا بتوزيع البيانات بشكل موحد.
131
00:06:05,750 --> 00:06:09,700
إذا في كل مرة تقوم فيها بتشغيل البيانات من خلال وظيفة التجزئة ، تحصل على رمز التجزئة 0 ،
132
00:06:09,700 --> 00:06:11,200
ربما هذا ليس رائعًا ، أليس كذلك؟
133
00:06:11,200 --> 00:06:14,600
ربما تريد زيادة مجموعة أكواد التجزئة.
134
00:06:14,600 --> 00:06:17,190
يمكن أيضًا توزيع الأشياء في جميع أنحاء الطاولة.
135
00:06:17,190 --> 00:06:23,210
وسيكون رائعًا أيضًا إذا كانت البيانات المتشابهة حقًا ، مثل جون وجوناثان ،
136
00:06:23,210 --> 00:06:26,320
ربما تم توزيعها لوزن مواقع مختلفة في جدول التجزئة.
137
00:06:26,320 --> 00:06:28,750
سيكون ذلك ميزة جيدة.
138
00:06:28,750 --> 00:06:31,250
>> هنا مثال لدالة التجزئة.
139
00:06:31,250 --> 00:06:33,150
لقد كتبت هذا في وقت سابق.
140
00:06:33,150 --> 00:06:35,047
إنها ليست دالة تجزئة جيدة بشكل خاص
141
00:06:35,047 --> 00:06:37,380
لأسباب لا تحتمل الدخول في الوقت الحالي.
142
00:06:37,380 --> 00:06:41,040
لكن هل ترى ما يحدث هنا؟
143
00:06:41,040 --> 00:06:44,420
يبدو أننا نعلن عن متغير يسمى sum ونضبطه على 0.
144
00:06:44,420 --> 00:06:50,010
ومن ثم يبدو أنني أفعل شيئًا طالما أن strstr [j] غير متساوٍ
145
00:06:50,010 --> 00:06:52,490
للشرطة المائلة للخلف 0.
146
00:06:52,490 --> 00:06:54,870
ماذا أفعل هناك؟
147
00:06:54,870 --> 00:06:57,440
>> هذه في الأساس مجرد طريقة أخرى للتنفيذ [؟ strl؟]
148
00:06:57,440 --> 00:06:59,773
واكتشاف وصولك إلى نهاية السلسلة.
149
00:06:59,773 --> 00:07:02,480
لذلك لا يتعين علي حساب طول السلسلة ،
150
00:07:02,480 --> 00:07:05,640
أنا أستخدم فقط عندما أصبت بشرطة مائلة عكسية 0 حرف أعرفه
151
00:07:05,640 --> 00:07:07,185
لقد وصلت إلى نهاية السلسلة.
152
00:07:07,185 --> 00:07:09,560
وبعد ذلك سأستمر في التكرار خلال تلك السلسلة ،
153
00:07:09,560 --> 00:07:15,310
إضافة strstr [j] للمجموع ، ثم في نهاية اليوم ستعيد المجموع mod
154
00:07:15,310 --> 00:07:16,200
HASH_MAX.
155
00:07:16,200 --> 00:07:18,700
>> في الأساس كل ما تقوم به دالة التجزئة هو الجمع
156
00:07:18,700 --> 00:07:23,450
كل قيم ASCII لسلسلتي ، وبعد ذلك
157
00:07:23,450 --> 00:07:26,390
إرجاع بعض رمز التجزئة المعدل بواسطة HASH_MAX.
158
00:07:26,390 --> 00:07:29,790
ربما يكون حجم صفيفتي ، أليس كذلك؟
159
00:07:29,790 --> 00:07:33,160
لا أريد الحصول على أكواد التجزئة إذا كان حجم مصفوفي 10 ،
160
00:07:33,160 --> 00:07:35,712
لا أريد الحصول على رموز التجزئة 11 ، 12 ،
161
00:07:35,712 --> 00:07:38,690
13 ، لا يمكنني وضع الأشياء في تلك المواقع من المصفوفة ،
162
00:07:38,690 --> 00:07:39,790
سيكون ذلك غير قانوني.
163
00:07:39,790 --> 00:07:42,130
كنت أعاني من خطأ تجزئة.
164
00:07:42,130 --> 00:07:45,230
>> الآن هنا جانب سريع آخر.
165
00:07:45,230 --> 00:07:48,470
بشكل عام ، ربما لن ترغب في كتابة وظائف التجزئة الخاصة بك.
166
00:07:48,470 --> 00:07:50,997
إنه في الواقع نوع من الفن وليس علمًا.
167
00:07:50,997 --> 00:07:52,580
وهناك الكثير من الأمور التي تتعلق بهم.
168
00:07:52,580 --> 00:07:55,288
الإنترنت ، كما قلت ، مليء بوظائف التجزئة الجيدة حقًا ،
169
00:07:55,288 --> 00:07:58,470
ويجب عليك استخدام الإنترنت للعثور على وظائف التجزئة لأنها حقًا
170
00:07:58,470 --> 00:08:03,230
مجرد نوع من مضيعة غير ضرورية للوقت لإنشاء وقتك الخاص.
171
00:08:03,230 --> 00:08:05,490
>> يمكنك كتابة أشياء بسيطة لأغراض الاختبار.
172
00:08:05,490 --> 00:08:08,323
ولكن عندما تبدأ بالفعل في تجزئة البيانات وتخزينها
173
00:08:08,323 --> 00:08:10,780
في جدول التجزئة الذي ربما تريده
174
00:08:10,780 --> 00:08:14,580
لاستخدام بعض الوظائف التي تم إنشاؤها من أجلك ، والموجودة على الإنترنت.
175
00:08:14,580 --> 00:08:17,240
إذا كنت تفعل ذلك فقط تأكد من الاستشهاد بمصادرك.
176
00:08:17,240 --> 00:08:21,740
لا يوجد سبب لسرقة أي شيء هنا.
177
00:08:21,740 --> 00:08:25,370
>> مجتمع علوم الكمبيوتر ينمو بالتأكيد ، ويقدر حقًا
178
00:08:25,370 --> 00:08:28,796
مفتوح المصدر ، ومن المهم حقًا الاستشهاد بمصادرك حتى يتمكن الأشخاص من ذلك
179
00:08:28,796 --> 00:08:30,670
يمكنهم الحصول على الإسناد للعمل الذي يقومون به
180
00:08:30,670 --> 00:08:32,312
تفعل لصالح المجتمع.
181
00:08:32,312 --> 00:08:34,020
لذلك تأكد دائمًا - وليس فقط للتجزئة
182
00:08:34,020 --> 00:08:37,270
الوظائف ، ولكن بشكل عام عندما تستخدم رمزًا من مصدر خارجي ،
183
00:08:37,270 --> 00:08:38,299
اذكر مصدرك دائمًا.
184
00:08:38,299 --> 00:08:43,500
امنح الفضل للشخص الذي قام ببعض الأعمال حتى لا تضطر إلى ذلك.
185
00:08:43,500 --> 00:08:46,720
>> حسنًا ، فلنراجع جدول التجزئة هذا لمدة ثانية.
186
00:08:46,720 --> 00:08:48,780
هذا هو المكان الذي توقفنا فيه بعد أن أدخلنا
187
00:08:48,780 --> 00:08:53,300
يوحنا وبولس في جدول التجزئة هذا.
188
00:08:53,300 --> 00:08:55,180
هل ترى مشكلة هنا؟
189
00:08:55,180 --> 00:08:58,410
قد ترى اثنين.
190
00:08:58,410 --> 00:09:02,240
لكن على وجه الخصوص ، هل ترى هذه المشكلة المحتملة؟
191
00:09:02,240 --> 00:09:06,770
>> ماذا لو قمت بتجزئة Ringo ، واتضح ذلك بعد المعالجة
192
00:09:06,770 --> 00:09:14,000
تلك البيانات من خلال وظيفة التجزئة قام Ringo أيضًا بإنشاء رمز التجزئة 6.
193
00:09:14,000 --> 00:09:16,810
لقد حصلت بالفعل على بيانات في رمز التجزئة - موقع الصفيف 6.
194
00:09:16,810 --> 00:09:22,000
لذا من المحتمل أن تكون مشكلة بالنسبة لي الآن ، أليس كذلك؟
195
00:09:22,000 --> 00:09:23,060
>> نسمي هذا تصادمًا.
196
00:09:23,060 --> 00:09:26,460
ويحدث التصادم عندما يتم تشغيل قطعتين من البيانات عبر نفس التجزئة
197
00:09:26,460 --> 00:09:29,200
وظيفة تؤدي إلى نفس رمز التجزئة.
198
00:09:29,200 --> 00:09:32,850
من المفترض أننا ما زلنا نرغب في إدخال كلا الجزأين من البيانات في جدول التجزئة ،
199
00:09:32,850 --> 00:09:36,330
وإلا فلن نقوم بتشغيل Ringo بشكل تعسفي من خلال وظيفة التجزئة.
200
00:09:36,330 --> 00:09:40,870
من المفترض أننا نريد إدخال رينغو في تلك المجموعة.
201
00:09:40,870 --> 00:09:46,070
>> كيف يمكننا القيام بذلك ، إذا قدم هو وبولس رمز التجزئة 6؟
202
00:09:46,070 --> 00:09:49,520
لا نريد استبدال بول ، نريد أن يكون بولس هناك أيضًا.
203
00:09:49,520 --> 00:09:52,790
لذلك نحن بحاجة إلى إيجاد طريقة لإدخال العناصر في جدول التجزئة
204
00:09:52,790 --> 00:09:56,550
لا يزال يحافظ على الإدراج السريع والبحث السريع.
205
00:09:56,550 --> 00:10:01,350
وإحدى طرق التعامل معها هي القيام بشيء يسمى التحقيق الخطي.
206
00:10:01,350 --> 00:10:04,170
>> باستخدام هذه الطريقة إذا حدث تصادم ، حسنًا ، ماذا نفعل؟
207
00:10:04,170 --> 00:10:08,580
حسنًا ، لا يمكننا وضعه في موقع المصفوفة 6 ، أو أي كود تجزئة تم إنشاؤه ،
208
00:10:08,580 --> 00:10:10,820
دعنا نضعه في hashcode زائد 1.
209
00:10:10,820 --> 00:10:13,670
وإذا كان هذا ممتلئًا ، فلنضعه في رمز التجزئة زائد 2.
210
00:10:13,670 --> 00:10:17,420
فائدة هذا الوجود إذا لم يكن بالضبط حيث نعتقد أنه موجود ،
211
00:10:17,420 --> 00:10:20,850
وعلينا أن نبدأ البحث ، ربما لا نضطر إلى الذهاب بعيدًا.
212
00:10:20,850 --> 00:10:23,900
ربما لا يتعين علينا البحث في جميع العناصر n لجدول التجزئة.
213
00:10:23,900 --> 00:10:25,790
ربما يتعين علينا البحث عن اثنين منهم.
214
00:10:25,790 --> 00:10:30,680
>> ولذا فنحن ما زلنا نتجه نحو اقتراب متوسط الحالة هذا من 1 مقابل
215
00:10:30,680 --> 00:10:34,280
قريب من n ، لذلك ربما سيعمل ذلك.
216
00:10:34,280 --> 00:10:38,010
لذلك دعونا نرى كيف يمكن أن يحدث هذا في الواقع.
217
00:10:38,010 --> 00:10:41,460
ودعونا نرى ما إذا كان بإمكاننا اكتشاف المشكلة التي قد تحدث هنا.
218
00:10:41,460 --> 00:10:42,540
>> دعنا نقول أننا هاش بارت.
219
00:10:42,540 --> 00:10:45,581
سنقوم الآن بتشغيل مجموعة جديدة من السلاسل من خلال دالة التجزئة ،
220
00:10:45,581 --> 00:10:48,460
ونقوم بتشغيل Bart من خلال دالة التجزئة ، نحصل على رمز التجزئة 6.
221
00:10:48,460 --> 00:10:52,100
نلقي نظرة ، نرى 6 فارغة ، لذا يمكننا وضع بارت هناك.
222
00:10:52,100 --> 00:10:55,410
>> الآن قمنا بتجزئة ليزا وهذا أيضًا يولد رمز التجزئة 6.
223
00:10:55,410 --> 00:10:58,330
حسنًا ، بعد أن استخدمنا طريقة الفحص الخطية هذه ، نبدأ من 6 ،
224
00:10:58,330 --> 00:10:59,330
نرى أن 6 ممتلئة.
225
00:10:59,330 --> 00:11:00,990
لا يمكننا وضع ليزا في الرقم 6.
226
00:11:00,990 --> 00:11:02,090
إذن، أين نذهب؟
227
00:11:02,090 --> 00:11:03,280
دعنا ننتقل إلى 7.
228
00:11:03,280 --> 00:11:04,610
رقم 7 فارغ ، لذلك يعمل.
229
00:11:04,610 --> 00:11:06,510
لذلك دعونا نضع ليزا هناك.
230
00:11:06,510 --> 00:11:10,200
>> الآن قمنا بتجزئة هومر ونحصل على 7.
231
00:11:10,200 --> 00:11:13,380
حسنًا ، نعلم جيدًا أن الرقم 7 ممتلئ الآن ، لذا لا يمكننا وضع هومر هناك.
232
00:11:13,380 --> 00:11:14,850
فلننتقل إلى 8.
233
00:11:14,850 --> 00:11:15,664
8 متاح؟
234
00:11:15,664 --> 00:11:18,330
نعم ، و 8 تقترب من 7 ، لذلك إذا كان علينا بدء البحث ، فنحن
235
00:11:18,330 --> 00:11:20,020
لن تضطر إلى الذهاب بعيدا.
236
00:11:20,020 --> 00:11:22,860
لذلك دعونا نضع هومر في المرتبة الثامنة.
237
00:11:22,860 --> 00:11:25,151
>> الآن نقوم بتجزئة ماجي وإرجاع 3 ، الحمد لله
238
00:11:25,151 --> 00:11:26,650
يمكننا فقط وضع ماجي هناك.
239
00:11:26,650 --> 00:11:29,070
لا يتعين علينا القيام بأي نوع من التحقيق في ذلك.
240
00:11:29,070 --> 00:11:32,000
الآن نقوم بتجزئة Marge ، وترجع Marge أيضًا 6.
241
00:11:32,000 --> 00:11:39,560
>> حسنًا 6 ممتلئ ، 7 ممتلئ ، 8 ممتلئ ، 9 ، حسنًا الحمد لله ، 9 فارغ.
242
00:11:39,560 --> 00:11:41,600
يمكنني وضع مارج في التاسعة.
243
00:11:41,600 --> 00:11:45,280
بالفعل يمكننا أن نرى أننا بدأنا نواجه هذه المشكلة حيث نحن الآن
244
00:11:45,280 --> 00:11:48,780
البدء في تمديد الأشياء بعيدًا عن أكواد التجزئة الخاصة بهم.
245
00:11:48,780 --> 00:11:52,960
وأن ثيتا 1 ، تلك الحالة المتوسطة لكونها وقتًا ثابتًا ،
246
00:11:52,960 --> 00:11:56,560
بدأ في الحصول على المزيد - بدأ يميل أكثر قليلاً
247
00:11:56,560 --> 00:11:58,050
نحو ثيتا من ن.
248
00:11:58,050 --> 00:12:01,270
لقد بدأنا نفقد ميزة جداول التجزئة.
249
00:12:01,270 --> 00:12:03,902
>> هذه المشكلة التي رأيناها للتو تسمى التجميع.
250
00:12:03,902 --> 00:12:06,360
والشيء السيئ حقًا في التجميع هو أنك مرة واحدة الآن
251
00:12:06,360 --> 00:12:09,606
وجود عنصرين جنبًا إلى جنب مما يزيد من احتمالية حدوثه ،
252
00:12:09,606 --> 00:12:11,480
لديك فرصة مضاعفة ، أنك ذاهب
253
00:12:11,480 --> 00:12:13,516
لتصادم آخر مع تلك المجموعة ،
254
00:12:13,516 --> 00:12:14,890
وسوف تنمو الكتلة بواحد.
255
00:12:14,890 --> 00:12:19,640
وستستمر في النمو وزيادة احتمالية حدوث تصادم.
256
00:12:19,640 --> 00:12:24,470
وفي النهاية يكون الأمر سيئًا مثل عدم فرز البيانات على الإطلاق.
257
00:12:24,470 --> 00:12:27,590
>> لكن المشكلة الأخرى هي أننا ما زلنا ، وحتى الآن حتى هذه اللحظة ،
258
00:12:27,590 --> 00:12:30,336
لقد فهمنا نوعًا ما ما هو جدول التجزئة ،
259
00:12:30,336 --> 00:12:31,960
لا يزال لدينا متسع لـ 10 سلاسل فقط.
260
00:12:31,960 --> 00:12:37,030
إذا أردنا الاستمرار في تجزئة مواطني سبرينغفيلد ،
261
00:12:37,030 --> 00:12:38,790
يمكننا فقط الحصول على 10 منهم هناك.
262
00:12:38,790 --> 00:12:42,619
وإذا حاولنا إضافة 11 أو 12 ، فليس لدينا مكان لوضعهما.
263
00:12:42,619 --> 00:12:45,660
يمكننا فقط أن نلتف في دوائر نحاول إيجاد مكان فارغ ،
264
00:12:45,660 --> 00:12:49,000
وربما نتعثر في حلقة لا نهائية.
265
00:12:49,000 --> 00:12:51,810
>> لذا فإن هذا النوع من الإقراض لفكرة شيء يسمى التسلسل.
266
00:12:51,810 --> 00:12:55,790
وهذا هو المكان الذي سنقوم فيه بإعادة القوائم المرتبطة إلى الصورة.
267
00:12:55,790 --> 00:13:01,300
ماذا لو بدلاً من تخزين البيانات نفسها في المصفوفة ،
268
00:13:01,300 --> 00:13:04,471
يمكن أن يحتوي كل عنصر من عناصر المصفوفة على أجزاء متعددة من البيانات؟
269
00:13:04,471 --> 00:13:05,970
حسنًا ، هذا غير منطقي ، أليس كذلك؟
270
00:13:05,970 --> 00:13:09,280
نحن نعلم أن المصفوفة يمكن أن تحتوي فقط - كل عنصر من عناصر المصفوفة
271
00:13:09,280 --> 00:13:12,930
يمكن أن تحتوي على جزء واحد فقط من البيانات من هذا النوع من البيانات.
272
00:13:12,930 --> 00:13:16,750
>> ولكن ماذا لو كان نوع البيانات هذا عبارة عن قائمة مرتبطة ، أليس كذلك؟
273
00:13:16,750 --> 00:13:19,830
فماذا لو كان كل عنصر من عناصر المصفوفة
274
00:13:19,830 --> 00:13:22,790
مؤشر إلى رأس قائمة مرتبطة؟
275
00:13:22,790 --> 00:13:24,680
وبعد ذلك يمكننا بناء تلك القوائم المرتبطة
276
00:13:24,680 --> 00:13:27,120
وتنميتها بشكل تعسفي ، لأن القوائم المرتبطة تسمح بذلك
277
00:13:27,120 --> 00:13:32,090
علينا أن ننمو ونتقلص بمرونة أكبر بكثير من المصفوفة.
278
00:13:32,090 --> 00:13:34,210
إذن ماذا لو استخدمنا الآن ، استفدنا من هذا ، أليس كذلك؟
279
00:13:34,210 --> 00:13:37,760
نبدأ في تنمية هذه السلاسل خارج مواقع المصفوفة هذه.
280
00:13:37,760 --> 00:13:40,740
>> يمكننا الآن استيعاب كمية لا حصر لها من البيانات ، أو غير محدودة ،
281
00:13:40,740 --> 00:13:44,170
كمية عشوائية من البيانات ، في جدول التجزئة الخاص بنا
282
00:13:44,170 --> 00:13:47,760
دون الوقوع في مشكلة الاصطدام.
283
00:13:47,760 --> 00:13:50,740
لقد أزلنا أيضًا التجميع من خلال القيام بذلك.
284
00:13:50,740 --> 00:13:54,380
ونعلم جيدًا أنه عندما ندرج في قائمة مرتبطة ، إذا كنت تتذكر
285
00:13:54,380 --> 00:13:57,779
من الفيديو الخاص بنا في القوائم المرتبطة والقوائم المرتبطة بشكل فردي والقوائم المرتبطة بشكل مضاعف ،
286
00:13:57,779 --> 00:13:59,070
إنها عملية زمنية ثابتة.
287
00:13:59,070 --> 00:14:00,710
نحن فقط نضيف إلى المقدمة.
288
00:14:00,710 --> 00:14:04,400
>> وللبحث ، نحن نعلم جيدًا أن البحث في قائمة مرتبطة
289
00:14:04,400 --> 00:14:05,785
يمكن أن يكون مشكلة ، أليس كذلك؟
290
00:14:05,785 --> 00:14:07,910
علينا البحث من خلاله من البداية إلى النهاية.
291
00:14:07,910 --> 00:14:10,460
لا يوجد وصول عشوائي في قائمة مرتبطة.
292
00:14:10,460 --> 00:14:15,610
ولكن إذا بدلاً من وجود قائمة مرتبطة واحدة حيث يكون البحث هو O لـ n ،
293
00:14:15,610 --> 00:14:19,590
لدينا الآن 10 قوائم مرتبطة ، أو 1000 قائمة مرتبطة ،
294
00:14:19,590 --> 00:14:24,120
الآن هو O لـ n مقسومًا على 10 ، أو O لـ n مقسومًا على 1000.
295
00:14:24,120 --> 00:14:26,940
>> وبينما كنا نتحدث نظريًا عن التعقيد
296
00:14:26,940 --> 00:14:30,061
نتجاهل الثوابت ، فهذه الأشياء مهمة في الواقع ،
297
00:14:30,061 --> 00:14:30,560
الصحيح؟
298
00:14:30,560 --> 00:14:33,080
في الواقع سوف نلاحظ أن هذا يحدث
299
00:14:33,080 --> 00:14:36,610
لتشغيل أسرع 10 مرات ، أو 1000 مرة أسرع ،
300
00:14:36,610 --> 00:14:41,570
لأننا نوزع سلسلة طويلة واحدة على 1000 سلسلة أصغر.
301
00:14:41,570 --> 00:14:45,090
وهكذا في كل مرة يتعين علينا البحث من خلال واحدة من تلك السلاسل يمكننا ذلك
302
00:14:45,090 --> 00:14:50,290
تجاهل 999 سلسلة لا نهتم بها ، وابحث فقط عن تلك السلسلة.
303
00:14:50,290 --> 00:14:53,220
>> وهو في المتوسط أقصر بـ 1000 مرة.
304
00:14:53,220 --> 00:14:56,460
ولذا فإننا ما زلنا نميل نوعًا ما نحو هذه الحالة المتوسطة
305
00:14:56,460 --> 00:15:01,610
من كوننا وقتًا ثابتًا ، ولكن فقط لأننا نستفيد
306
00:15:01,610 --> 00:15:03,730
القسمة على عامل ثابت ضخم.
307
00:15:03,730 --> 00:15:05,804
دعونا نرى كيف سيبدو هذا في الواقع.
308
00:15:05,804 --> 00:15:08,720
لذلك كان هذا هو جدول التجزئة الذي كان لدينا قبل أن أعلنا عن جدول التجزئة
309
00:15:08,720 --> 00:15:10,270
كان قادرًا على تخزين 10 سلاسل.
310
00:15:10,270 --> 00:15:11,728
لن نفعل ذلك بعد الآن.
311
00:15:11,728 --> 00:15:13,880
نحن نعلم بالفعل حدود هذه الطريقة.
312
00:15:13,880 --> 00:15:20,170
الآن جدول التجزئة الخاص بنا سيكون مصفوفة من 10 عقد ، مؤشرات
313
00:15:20,170 --> 00:15:22,120
لرؤساء القوائم المرتبطة.
314
00:15:22,120 --> 00:15:23,830
>> وهو الآن لاغٍ.
315
00:15:23,830 --> 00:15:26,170
كل واحدة من هذه المؤشرات العشر خالية.
316
00:15:26,170 --> 00:15:29,870
لا يوجد شيء في جدول التجزئة لدينا الآن.
317
00:15:29,870 --> 00:15:32,690
>> لنبدأ الآن في وضع بعض الأشياء في جدول التجزئة هذا.
318
00:15:32,690 --> 00:15:35,440
ودعونا نرى كيف ستفيدنا هذه الطريقة قليلاً.
319
00:15:35,440 --> 00:15:36,760
لنقم الآن بتجزئة جوي.
320
00:15:36,760 --> 00:15:40,210
سنقوم بتشغيل السلسلة Joey من خلال دالة تجزئة وسنقوم بإرجاع 6.
321
00:15:40,210 --> 00:15:41,200
حسنا ماذا نفعل الان؟
322
00:15:41,200 --> 00:15:44,090
>> حسنًا ، نعمل الآن مع القوائم المرتبطة ، نحن لا نعمل مع المصفوفات.
323
00:15:44,090 --> 00:15:45,881
وعندما نعمل مع القوائم المرتبطة نحن
324
00:15:45,881 --> 00:15:49,790
نعلم أننا بحاجة إلى البدء ديناميكيًا في تخصيص المساحة وبناء السلاسل.
325
00:15:49,790 --> 00:15:54,020
هذا نوع من الكيفية - هذه هي العناصر الأساسية لبناء قائمة مرتبطة.
326
00:15:54,020 --> 00:15:57,670
لذلك دعونا نخصص مساحة ديناميكيًا لـ Joey ،
327
00:15:57,670 --> 00:16:00,390
ثم نضيفه إلى السلسلة.
328
00:16:00,390 --> 00:16:03,170
>> لذا انظر الآن إلى ما فعلناه.
329
00:16:03,170 --> 00:16:06,440
عندما قمنا بتجزئة جوي ، حصلنا على رمز التجزئة 6.
330
00:16:06,440 --> 00:16:11,790
الآن يشير المؤشر في موقع الصفيف 6 إلى رأس قائمة مرتبطة ،
331
00:16:11,790 --> 00:16:14,900
وهو الآن العنصر الوحيد في القائمة المرتبطة.
332
00:16:14,900 --> 00:16:18,350
والعقدة في تلك القائمة المرتبطة هي Joey.
333
00:16:18,350 --> 00:16:22,300
>> لذا إذا احتجنا إلى البحث عن Joey لاحقًا ، فسنقوم بتجزئة Joey مرة أخرى ،
334
00:16:22,300 --> 00:16:26,300
نحصل على 6 مرة أخرى لأن دالة التجزئة لدينا حتمية.
335
00:16:26,300 --> 00:16:30,400
وبعد ذلك نبدأ على رأس القائمة المرتبطة المشار إليها
336
00:16:30,400 --> 00:16:33,360
إلى عن طريق موقع المصفوفة 6 ، ويمكننا التكرار
337
00:16:33,360 --> 00:16:35,650
عبر محاولة العثور على جوي.
338
00:16:35,650 --> 00:16:37,780
وإذا قمنا ببناء جدول التجزئة الخاص بنا بشكل فعال ،
339
00:16:37,780 --> 00:16:41,790
ووظيفة التجزئة لدينا بشكل فعال لتوزيع البيانات بشكل جيد ،
340
00:16:41,790 --> 00:16:45,770
في المتوسط ، كل من تلك القوائم المرتبطة في كل موقع مصفوفة
341
00:16:45,770 --> 00:16:50,110
سيكون حجمه 1/10 إذا كان لدينا واحد ضخم
342
00:16:50,110 --> 00:16:51,650
قائمة مرتبطة بكل شيء بداخلها.
343
00:16:51,650 --> 00:16:55,670
>> إذا وزعنا تلك القائمة المرتبطة الضخمة عبر 10 قوائم مرتبطة
344
00:16:55,670 --> 00:16:57,760
ستكون كل قائمة بحجم 1/10.
345
00:16:57,760 --> 00:17:01,432
وبالتالي أسرع 10 مرات في البحث.
346
00:17:01,432 --> 00:17:02,390
لذلك دعونا نفعل هذا مرة أخرى.
347
00:17:02,390 --> 00:17:04,290
دعونا الآن تجزئة روس.
348
00:17:04,290 --> 00:17:07,540
>> ولنفترض أن روس ، عندما نفعل ذلك كود التجزئة الذي نحصل عليه هو 2.
349
00:17:07,540 --> 00:17:10,630
حسنًا ، نخصص عقدة جديدة ديناميكيًا ، ونضع روس في تلك العقدة ،
350
00:17:10,630 --> 00:17:14,900
ونقول الآن موقع المصفوفة 2 ، بدلاً من الإشارة إلى الصفر ،
351
00:17:14,900 --> 00:17:18,579
يشير إلى رأس قائمة مرتبطة العقدة الوحيدة هي روس.
352
00:17:18,579 --> 00:17:22,660
ويمكننا القيام بذلك مرة أخرى ، يمكننا تجزئة راشيل والحصول على رمز التجزئة 4.
353
00:17:22,660 --> 00:17:25,490
malloc عقدة جديدة ، ضع راشيل في العقدة ، وقل موقع مصفوفة
354
00:17:25,490 --> 00:17:27,839
4 يشير الآن إلى رأس القائمة المرتبطة التي
355
00:17:27,839 --> 00:17:31,420
العنصر الوحيد هو راشيل.
356
00:17:31,420 --> 00:17:33,470
>> حسنًا ولكن ماذا يحدث إذا حدث تصادم؟
357
00:17:33,470 --> 00:17:38,560
دعونا نرى كيف نتعامل مع الاصطدامات باستخدام طريقة التسلسل المنفصلة.
358
00:17:38,560 --> 00:17:39,800
دعونا نقسم فيبي.
359
00:17:39,800 --> 00:17:41,094
نحصل على رمز التجزئة 6.
360
00:17:41,094 --> 00:17:44,010
في مثالنا السابق كنا نقوم فقط بتخزين السلاسل في المصفوفة.
361
00:17:44,010 --> 00:17:45,980
كانت هذه مشكلة.
362
00:17:45,980 --> 00:17:48,444
>> لا نريد ضرب جوي ، وقد فعلنا ذلك بالفعل
363
00:17:48,444 --> 00:17:51,110
رأينا أنه يمكننا الحصول على بعض مشاكل التجميع إذا حاولنا خطوة
364
00:17:51,110 --> 00:17:52,202
من خلال والتحقيق.
365
00:17:52,202 --> 00:17:54,660
ولكن ماذا لو تعاملنا مع هذا النوع بنفس الطريقة ، أليس كذلك؟
366
00:17:54,660 --> 00:17:57,440
إنه يشبه تمامًا إضافة عنصر إلى رأس قائمة مرتبطة.
367
00:17:57,440 --> 00:18:00,220
دعونا فقط مساحة malloc لفيبي.
368
00:18:00,220 --> 00:18:04,764
>> سنقول أن مؤشر فيبي التالي يشير إلى الرأس القديم للقائمة المرتبطة ،
369
00:18:04,764 --> 00:18:07,180
ثم 6 يشير فقط إلى الرئيس الجديد للقائمة المرتبطة.
370
00:18:07,180 --> 00:18:10,150
والآن انظر ، لقد غيرنا فيبي في.
371
00:18:10,150 --> 00:18:14,210
يمكننا الآن تخزين عنصرين باستخدام رمز التجزئة 6 ،
372
00:18:14,210 --> 00:18:17,170
وليس لدينا أي مشاكل.
373
00:18:17,170 --> 00:18:20,147
>> هذا إلى حد كبير كل ما في السلاسل.
374
00:18:20,147 --> 00:18:21,980
And chaining is definitely the method that's
375
00:18:21,980 --> 00:18:27,390
going to be most effective for you if you are storing data in a hash table.
376
00:18:27,390 --> 00:18:30,890
But this combination of arrays and linked lists
377
00:18:30,890 --> 00:18:36,080
together to form a hash table really dramatically improves your ability
378
00:18:36,080 --> 00:18:40,550
to store large amounts of data, and very quickly and efficiently search
379
00:18:40,550 --> 00:18:41,630
through that data.
380
00:18:41,630 --> 00:18:44,150
>> There's still one more data structure out there
381
00:18:44,150 --> 00:18:48,700
that might even be a bit better in terms of guaranteeing
382
00:18:48,700 --> 00:18:51,920
that our insertion, deletion, and look up times are even faster.
383
00:18:51,920 --> 00:18:55,630
And we'll see that in a video on tries.
384
00:18:55,630 --> 00:18:58,930
I'm Doug Lloyd, this is CS50.
385
00:18:58,930 --> 00:19:00,214
undefined44719
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.
Afrikaans
Albanian
Amharic
Armenian
Azerbaijani
Basque
Belarusian
Bengali
Bosnian
Bulgarian
Catalan
Cebuano
Chichewa
Chinese (Simplified)
Chinese (Traditional)
Corsican
Croatian
Czech
Danish
Dutch
English
Esperanto
Estonian
Finnish
French
Frisian
Galician
Georgian
German
Greek
Gujarati
Haitian Creole
Hawaiian
Hungarian
Icelandic
Indonesian
Irish
Italian
Japanese
Kazakh
Khmer
Korean
Kurdish (Kurmanji)
Kyrgyz
Lao
Latvian
Lithuanian
Luxembourgish
Macedonian
Malagasy
Malay
Maltese
Maori
Mongolian
Myanmar (Burmese)
Nepali
Norwegian
Pashto
Polish
Portuguese
Romanian
Russian
Samoan
Serbian
Sesotho
Shona
Sinhala
Slovak
Slovenian
Somali
Spanish
Swahili
Swedish
Tajik
Thai
Turkish
Ukrainian
Urdu
Uzbek
Vietnamese
