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
>> DOUG لويد: عليك الآن
أعرف الكثير عن المصفوفات،

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
That's-- ليس لدينا بيانات
هيكل بعد أن تستطيع أن تفعل ذلك،

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
الوقت يصبح أقرب إلى
ثيتا ن، ولقد الأساس

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
نحن عادة استدعاء hashcode، OK؟

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
وحتى تتم معالجة البيانات
ويبصق العدد، OK؟

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
>> ودعونا نقول اننا تشغيل جون
من خلال هذه الوظيفة تجزئة

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
نحن نريد ان نضع جون في موقع مجموعة
4، لأننا إذا تجزئة جون again--

91
00:04:22,050 --> 00:04:23,810
دعونا نقول أننا في وقت لاحق
تريد البحث ومعرفة

92
00:04:23,810 --> 00:04:26,960
إذا جون موجود في هذه البعثرة
table-- كل ما عليك القيام به

93
00:04:26,960 --> 00:04:30,310
يتم تشغيله من خلال نفس تجزئة
وظيفة، احصل على خروج عدد 4،

94
00:04:30,310 --> 00:04:33,929
وتكون قادرة على العثور جون
على الفور في بنية البيانات لدينا.

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
دعنا نقول أن هذا الوقت ونحن تشغيل
بول من خلال وظيفة التجزئة،

99
00:04:42,070 --> 00:04:44,600
وhashcode الذي تم إنشاؤه هو 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
ويدير كل ما عليك القيام به بول
من خلال وظيفة تجزئة مرة أخرى

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
لذلك نحن لا نريد أن استخدام anything--
نحن لا تتضمن أي شيء

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
في دالة البعثرة ونحن دائما
الحصول على نفس hashcode بها.

126
00:05:50,040 --> 00:05:52,870
إذا كنت تمر جون في
وظيفة تجزئة أخرج 4.

127
00:05:52,870 --> 00:05:56,110
وأود أن تكون قادرة على القيام بذلك 10000
مرة وأنا دائما الحصول على 4.

128
00:05:56,110 --> 00:06:00,810
لذلك لا أرقام عشوائية بشكل فعال
يمكن أن تشارك في تجزئة لدينا tables--

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
إذا كنت في كل مرة تشغيل البيانات من خلال
وظيفة تجزئة تحصل على hashcode 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
يبدو وكأننا إعلان متغير
دعا المبلغ ووضع ذلك يساوي 0.

144
00:06:44,420 --> 00:06:50,010
ومن ثم يبدو أنني أفعل شيئا
طالما strstr [ي] لا تساوي

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 [ي] وخلاصة القول، ثم في
نهاية اليوم سوف تعود مبلغ زارة الدفاع

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
إعادة بعض hashcode
كتكوت من قبل 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
لذا يجب دائما sure--
وليس فقط للتجزئة

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
>> OK لذلك دعونا إعادة النظر في هذا
جدول تجزئة لفترة ثانية.

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
>> ماذا لو تجزئة رينغو، وذلك
تبين أنه بعد تجهيز

192
00:09:06,770 --> 00:09:14,000
أن البيانات من خلال دالة البعثرة
وحققت رينغو وhashcode 6.

193
00:09:14,000 --> 00:09:16,810
لقد حصلت بالفعل على البيانات
hashcode-- موقع مجموعة 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
وظيفة تدر نفس hashcode.

198
00:09:29,200 --> 00:09:32,850
يفترض أننا لا تزال ترغب في الحصول على كل
قطعة من البيانات في جدول التجزئة،

199
00:09:32,850 --> 00:09:36,330
وإلا فإننا لن تكون قيد التشغيل رينغو
تعسفا من خلال وظيفة التجزئة.

200
00:09:36,330 --> 00:09:40,870
نريد من المفترض أن يحصل
رينغو إلى أن مجموعة.

201
00:09:40,870 --> 00:09:46,070
>> كيف لنا أن نفعل ذلك على الرغم من ذلك، إذا كان
وبول كل من العائد hashcode 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، أو أيا كان hashcode تم إنشاؤها،

208
00:10:08,580 --> 00:10:10,820
دعونا نضع له في hashcode زائد 1.

209
00:10:10,820 --> 00:10:13,670
وإذا كان هذا هو كامل دعونا
وضعت له في hashcode زائد 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
ربما لم يكن لدينا للبحث
جميع العناصر ن من جدول التجزئة.

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
بالقرب من ن، لذلك ربما هذا سوف يعمل.

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
ونحن تشغيل بارت من خلال تجزئة
وظيفة، وحصلنا على hashcode 6.

221
00:10:48,460 --> 00:10:52,100
ونحن نلقي نظرة، ونحن نرى 6 هو
فارغة، حتى نتمكن من وضع بارت هناك.

222
00:10:52,100 --> 00:10:55,410
>> ونحن الآن تجزئة ليزا والتي
كما يولد hashcode 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
وذلك دعونا نضع هوميروس في 8.

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
ونحن الآن تجزئة زبدة نباتية، و
مارج أيضا إرجاع 6.

241
00:11:32,000 --> 00:11:39,560
>> حسنا 6 كامل، 7 كامل، 8 كامل،
9، أشكر جميع حق الله، 9 فارغ.

242
00:11:39,560 --> 00:11:41,600
يمكن أن أضع زبدة نباتية في 9.

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
وبدءا من الحصول على بعض الشيء more--
بدأت تميل قليلا أكثر

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
وإذا حاولنا وإضافة 11TH أو 12TH،
ليس لدينا مكان لوضعها.

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
ونحن نعلم أن مجموعة يمكن فقط
hold-- كل عنصر من عناصر مجموعة

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 ن،

293
00:14:15,610 --> 00:14:19,590
لدينا الآن 10 القوائم المرتبطة،
أو 1000 القوائم المرتبطة،

294
00:14:19,590 --> 00:14:24,120
الآن حان O ن مقسوما على 10،
أو O ن مقسوما 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
كل واحدة من تلك المؤشرات 10 لاغيا.

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
سنقوم سيتم تشغيل سلسلة جوي من خلال
وظيفة تجزئة ونعود 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
هذا النوع من how-- تلك هي جوهر
عناصر بناء قائمة مرتبطة.

326
00:15:54,020 --> 00:15:57,670
لذلك دعونا حيوي
تخصيص مساحة لجوي،

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
عندما كنا تجزئة جوي حصلنا على hashcode 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
والعقدة في ذلك
قائمة مرتبطة هي جوي.

333
00:16:18,350 --> 00:16:22,300
>> حتى إذا كنا بحاجة للبحث عن جوي
في وقت لاحق، ونحن فقط تجزئة جوي مرة أخرى،

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
ويمكننا أن نفعل ذلك أكثر مرة واحدة، ونحن
يمكن تجزئة راشيل والحصول على hashcode 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
نحصل على hashcode 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
يمكننا الآن تخزين اثنين
العناصر مع hashcode 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
وتسلسل هو بالتأكيد
الأسلوب الذي هو

375
00:18:21,980 --> 00:18:27,390
سيكون الأكثر فعالية بالنسبة لك إذا
يتم تخزين البيانات في جدول تجزئة.

376
00:18:27,390 --> 00:18:30,890
ولكن هذا المزيج من
المصفوفات والقوائم المرتبطة

377
00:18:30,890 --> 00:18:36,080
معا لتشكيل جدول تجزئة حقا
يحسن بشكل كبير على قدرتك

378
00:18:36,080 --> 00:18:40,550
لتخزين كميات كبيرة من البيانات، و
بسرعة كبيرة وكفاءة البحث

379
00:18:40,550 --> 00:18:41,630
من خلال تلك البيانات.

380
00:18:41,630 --> 00:18:44,150
>> لا يزال هناك أكثر من
هيكل البيانات الى هناك

381
00:18:44,150 --> 00:18:48,700
قد يكون حتى قليلا
أفضل من حيث ضمان

382
00:18:48,700 --> 00:18:51,920
أن لدينا الإدراج أو الحذف، و
بحث عن الأوقات حتى أسرع.

383
00:18:51,920 --> 00:18:55,630
وسنرى ذلك في شريط فيديو على محاولات.

384
00:18:55,630 --> 00:18:58,930
أنا دوغ ويد، وهذا هو CS50.

385
00:18:58,930 --> 00:19:00,214