1
00:00:06,979 --> 00:00:07,479
[רעש].

2
00:00:07,479 --> 00:00:09,367
לפני הצלילה לתוך שולחנות חשיש, בואו

3
00:00:09,367 --> 00:00:11,196
תסקור את היתרונות וחסרונות של חלק ראשון

4
00:00:11,196 --> 00:00:13,202
מבני נתונים פשוטים יותר, החל

5
00:00:13,202 --> 00:00:14,739
מערכים.

6
00:00:14,739 --> 00:00:16,869
נזכיר כי מערכים לאפשר לנו לאחסן

7
00:00:16,869 --> 00:00:18,644
אלמנטים מסוג נתונים אחד

8
00:00:18,644 --> 00:00:21,259
סמיכות בזיכרון.

9
00:00:21,259 --> 00:00:24,115
מכיוון שכל אלמנט קשור

10
00:00:24,115 --> 00:00:26,513
מדד, או מיקום,

11
00:00:26,513 --> 00:00:27,661
יש לנו גישה אקראית לכל

12
00:00:27,661 --> 00:00:28,860
אלמנטים במערך.

13
00:00:28,860 --> 00:00:31,308
במילים אחרות, אנו יכולים לגשת לכל אלמנט

14
00:00:31,308 --> 00:00:33,468
בשלב אחד על ידי יצירת אינדקס ל

15
00:00:33,468 --> 00:00:35,112
מערך.

16
00:00:35,112 --> 00:00:37,224
זה עניין גדול, כי אלגוריתמים

17
00:00:37,224 --> 00:00:39,204
כמו חיפוש בינארי תלוי באקראי

18
00:00:39,204 --> 00:00:40,570
גישה.

19
00:00:40,570 --> 00:00:43,130
חיסרון של מערכים הוא שהגודל שלהם

20
00:00:43,130 --> 00:00:44,380
הוא קבוע.

21
00:00:44,380 --> 00:00:46,630
מאחר שנתוני חנות מערכי contiguously ב

22
00:00:46,630 --> 00:00:49,490
זיכרון, עליך לציין גודל מערך

23
00:00:49,490 --> 00:00:50,600
כאשר אתה מצהיר מערך.

24
00:00:50,600 --> 00:00:53,510
אתה למעשה שואל את ההפעלה

25
00:00:53,510 --> 00:00:55,600
מערכת שומרת לעצמנו את הכמות המתאימה

26
00:00:55,600 --> 00:00:58,080
זיכרון לאלמנטים של המערך.

27
00:00:58,080 --> 00:01:00,240
אין שום ערובה לכך שיותר זיכרון,

28
00:01:00,240 --> 00:01:02,370
בסמוך למערך שלך, יהיה זמין

29
00:01:02,370 --> 00:01:03,480
לשימוש מאוחר יותר.

30
00:01:03,480 --> 00:01:05,550
אז מערכים לא יכולים לגדול בקלות.

31
00:01:05,550 --> 00:01:07,715
נזכיר כי גם אנחנו למדנו על מקושרים

32
00:01:07,715 --> 00:01:09,630
רשימות, אשר יכול לגדול בגללם

33
00:01:09,630 --> 00:01:12,430
אלמנטים אינם רציפים בזיכרון.

34
00:01:12,430 --> 00:01:14,680
כל צומת ברשימה מקושרת מכילה את

35
00:01:14,680 --> 00:01:16,620
אלמנט שאנחנו רוצים לאחסן, כמו גם

36
00:01:16,620 --> 00:01:18,976
מצביע לאלמנט הבא ב

37
00:01:18,976 --> 00:01:19,756
הרשימה.

38
00:01:19,756 --> 00:01:22,560
למרבה הצער, את המחיר ששלמנו בשבילו

39
00:01:22,560 --> 00:01:24,945
גודל דינמי הוא גישה אקראית ל

40
00:01:24,945 --> 00:01:26,460
אלמנטים.

41
00:01:26,460 --> 00:01:28,760
כדי לגשת לאלמנט מסוים,

42
00:01:28,760 --> 00:01:30,810
זה הכרחי כדי לעבור את כולו

43
00:01:30,810 --> 00:01:32,910
רשימה עד הרכיב הרצוי הוא

44
00:01:32,910 --> 00:01:33,950
הגיע.

45
00:01:33,950 --> 00:01:36,450
לכן, אם אני מחפש את המספר 9, הייתי

46
00:01:36,450 --> 00:01:39,340
בצע את המצביעים מצומת לצומת,

47
00:01:39,340 --> 00:01:41,350
בודק אם הערך של כל צומת

48
00:01:41,350 --> 00:01:42,584
שווה ל 9.

49
00:01:42,584 --> 00:01:46,303
ככזה, במקרה הגרוע ביותר, הוא להסתכל למעלה

50
00:01:46,303 --> 00:01:48,400
O (n), שהוא רחוק מלהיות יעיל.

51
00:01:49,690 --> 00:01:51,630
אנחנו יכולים לעשות טובים יותר מאשר O (n) ועדיין

52
00:01:51,630 --> 00:01:53,470
המאפשר למבנה הנתונים שלנו לצמוח מעל

53
00:01:53,470 --> 00:01:54,560
זמן?

54
00:01:54,560 --> 00:01:56,810
שולחנות חשיש להציע פתרון.

55
00:01:56,810 --> 00:01:58,730
שולחנות חשיש משמשים בעת מהירה

56
00:01:58,730 --> 00:02:00,820
הוספה, מחיקה, ובדיקה של

57
00:02:00,820 --> 00:02:01,910
אלמנטים הם בראש סדר עדיפויות.

58
00:02:01,910 --> 00:02:05,500
בתאוריה, הוספה, מחיקה, ובדיקה

59
00:02:05,500 --> 00:02:07,275
אפילו יכול להיות מושלם במתמיד

60
00:02:07,275 --> 00:02:08,890
זמן.

61
00:02:08,890 --> 00:02:11,120
אז, מה הוא שולחן חשיש בכל מקרה?

62
00:02:11,120 --> 00:02:13,170
שולחן חשיש הוא רק מערך שילוב

63
00:02:13,170 --> 00:02:14,940
עם פונקציה, שאנחנו קוראים לחשיש

64
00:02:14,940 --> 00:02:15,440
פונקציה.

65
00:02:16,440 --> 00:02:18,610
פונקציית hash לוקחת פיסת המידע

66
00:02:18,610 --> 00:02:20,778
כקלט, אנחנו קוראים לזה מפתח, ו

67
00:02:20,778 --> 00:02:23,700
פלטי מספר שלם, המכונות

68
00:02:23,700 --> 00:02:24,895
כערך Hash.

69
00:02:24,895 --> 00:02:28,810
ערך Hash מפות המפתח שלנו ל

70
00:02:28,810 --> 00:02:30,840
מדד מסוים בשולחן החשיש.

71
00:02:32,080 --> 00:02:34,330
אתה בהתחלה הייתי להשתמש בפונקצית החשיש

72
00:02:34,330 --> 00:02:36,410
לקבוע היכן בטבלת החשיש

73
00:02:36,410 --> 00:02:38,430
לאחסן מפתח נתון.

74
00:02:38,430 --> 00:02:41,030
מאוחר יותר, היית להשתמש באותה פונקצית החשיש

75
00:02:41,030 --> 00:02:42,950
כדי לקבוע היכן בטבלת החשיש

76
00:02:42,950 --> 00:02:45,010
לחפש את מפתח נתון.

77
00:02:45,010 --> 00:02:47,190
מסיבה זו, זה חיוני כי חשיש

78
00:02:47,190 --> 00:02:49,840
פונקציה מתנהגת באופן עקבי ותפוקות

79
00:02:49,840 --> 00:02:53,130
את אותו ערך Hash עבור מפתחות זהים.

80
00:02:53,130 --> 00:02:54,970
דע כי שולחנות חשיש יכולים לשמש כדי

81
00:02:54,970 --> 00:02:56,310
לאחסן נתונים מכל הסוגים.

82
00:02:56,310 --> 00:02:58,330
אבל כדי לפשט את הדברים, אנחנו מתמקדים

83
00:02:58,330 --> 00:02:59,830
מחרוזות לעת עתה.

84
00:02:59,830 --> 00:03:01,630
הנה פונקצית חשיש פשוט עבור מחרוזות.

85
00:03:03,570 --> 00:03:05,590
פונקציית hash זה מחשב חשיש

86
00:03:05,590 --> 00:03:07,410
פונקציה המבוססת על האות הראשונה של

87
00:03:07,410 --> 00:03:07,910
מפתח.

88
00:03:09,090 --> 00:03:11,300
"אפל" מתחיל באות "A", כך שזה

89
00:03:11,300 --> 00:03:13,200
ממופה למדד 0 בטבלת הגיבוב.

90
00:03:14,270 --> 00:03:17,402
בדומה לכך, "בננה" ממופית למדד 1,

91
00:03:17,402 --> 00:03:19,829
או "חתול" ממופה לאינדקס 2.

92
00:03:21,750 --> 00:03:23,790
אם חבר שואל אם המילה "כלב" היא ב

93
00:03:23,790 --> 00:03:26,150
השולחן, אנחנו קלט "כלב" לחשיש

94
00:03:26,150 --> 00:03:28,390
פונקציה, אשר יהיה פלט ערך Hash

95
00:03:28,390 --> 00:03:29,790
של 3.

96
00:03:29,790 --> 00:03:33,150
מאז "כלב" אינו מאוחסן במדד 3, אנחנו

97
00:03:33,150 --> 00:03:35,330
ניתן לומר בביטחון ש" כלב "הוא לא

98
00:03:35,330 --> 00:03:36,340
בטבלה,

99
00:03:36,340 --> 00:03:38,260
למרות שאנחנו בדקנו אחד בלבד

100
00:03:38,260 --> 00:03:40,120
חשיש מדדי 26 של הטבלה.

101
00:03:42,170 --> 00:03:44,280
הגיע זמן לזרוק את מפתח ברגים לדברים.

102
00:03:44,280 --> 00:03:46,130
מה אם אנחנו רוצים לאחסן את "נמלה" ל

103
00:03:46,130 --> 00:03:47,820
שולחן גם כן?

104
00:03:47,820 --> 00:03:51,730
"נמלה" hashes למדד 0, בדיוק כמו "תפוחים" לא.

105
00:03:51,730 --> 00:03:53,890
זוהי דוגמא של התנגשות,

106
00:03:53,890 --> 00:03:56,419
תוצאה של שני מפתחות וליבון לאותו

107
00:03:56,419 --> 00:03:57,080
אינדקס.

108
00:03:58,140 --> 00:04:00,040
גם אם שולחן החשיש שלך הוא גדול יותר מאשר

109
00:04:00,040 --> 00:04:01,980
הנתונים שלך להגדיר, ושבחרת טוב

110
00:04:01,980 --> 00:04:03,060
חשיש פונקציה,

111
00:04:03,060 --> 00:04:04,560
אתה עדיין צריך תכנית להתמודדות עם

112
00:04:04,560 --> 00:04:06,420
התנגשויות, אם וכאשר הם מתעוררים.

113
00:04:07,440 --> 00:04:09,810
בואו לדבר על היתרונות וחסרונות של שני

114
00:04:09,810 --> 00:04:12,360
שיטות נפוצות לפתרון התנגשויות:

115
00:04:12,360 --> 00:04:15,230
ליניארי חיטוט ושרשור נפרד.

116
00:04:15,230 --> 00:04:17,430
עם יניארי חיטוט, אם hashes מפתח

117
00:04:17,430 --> 00:04:19,340
אותו המדד כפי שאוחסן בעבר

118
00:04:19,340 --> 00:04:21,840
מפתח, זה מוקצה זמין הבא

119
00:04:21,840 --> 00:04:22,862
חריץ בטבלה.

120
00:04:22,862 --> 00:04:27,353
אז, "נמלה" מאוחסנת כעת במדד 3, שכן

121
00:04:27,353 --> 00:04:30,850
מדדים 0, 1, ו -2 כבר היו בשימוש.

122
00:04:32,780 --> 00:04:34,610
ואם ננסה לאחסן מילה שלישית ש

123
00:04:34,610 --> 00:04:36,410
מתחיל עם האות "א", זה שהוקצה

124
00:04:36,410 --> 00:04:41,263
למדד 4, שכן מדדים 0, 1, 2, ו -3

125
00:04:41,263 --> 00:04:42,530
הם מלאים.

126
00:04:42,530 --> 00:04:44,300
כפי שניתן לראות אפילו מזו פשוטה

127
00:04:44,300 --> 00:04:46,580
למשל, ברגע שמתרחשת התנגשות, אתה

128
00:04:46,580 --> 00:04:48,400
להגדיל את הסיכויים באופן משמעותי, כי

129
00:04:48,400 --> 00:04:50,370
התנגשות נוספת תתרחש באותו

130
00:04:50,370 --> 00:04:51,630
אזור.

131
00:04:51,630 --> 00:04:53,530
זה נקרא קיבוץ, וזה

132
00:04:53,530 --> 00:04:56,200
חסרון רציני ליניארי חיטוט.

133
00:04:56,200 --> 00:04:59,240
יתר על כן, במקרה הגרוע ביותר הכנסה, מחיקה,

134
00:04:59,240 --> 00:05:02,008
ובזמני בדיקה שהואצלו לO (n),

135
00:05:02,008 --> 00:05:04,200
כמו שיש לי החריץ הפנוי הבא יכול

136
00:05:04,200 --> 00:05:06,225
פוטנציאל היה החריץ האחרון בטבלה.

137
00:05:06,225 --> 00:05:09,210
אולי שרשור נפרד יציע יותר

138
00:05:09,210 --> 00:05:10,220
פתרון משכנע.

139
00:05:10,220 --> 00:05:13,060
במודל השרשור הנפרד, החשיש

140
00:05:13,060 --> 00:05:14,930
שולחן הוא למעשה מערך של מצביעים ל

141
00:05:14,930 --> 00:05:16,220
רשימות מקושרות.

142
00:05:16,220 --> 00:05:18,350
כאשר מתרחשת התנגשות, המפתח יכול להיות

143
00:05:18,350 --> 00:05:20,760
הוכנס בזמן קבוע בראש

144
00:05:20,760 --> 00:05:22,270
הרשימה המתאימה המקושרת.

145
00:05:23,420 --> 00:05:25,310
מה קורה עכשיו כאשר אנו לחפש את "תפוח"

146
00:05:25,310 --> 00:05:26,900
בשולחן החשיש?

147
00:05:26,900 --> 00:05:28,940
במקרה הגרוע ביותר, עלינו לעבור את

148
00:05:28,940 --> 00:05:32,530
כל רשימה מקושרת, החל משעת מדד 0.

149
00:05:32,530 --> 00:05:34,210
המקרה הגרוע ביותר זמן בדיקה לחשיש

150
00:05:34,210 --> 00:05:35,890
שולחן שמשתמש בשרשור נפרד הוא

151
00:05:35,890 --> 00:05:38,580
לכן O (n / k), כאשר k הוא

152
00:05:38,580 --> 00:05:39,687
גודלו של שולחן החשיש.

153
00:05:39,687 --> 00:05:42,940
חכה שני, k הוא קבוע.

154
00:05:42,940 --> 00:05:46,280
אז O (n / k) הוא באמת רק O (n),

155
00:05:46,280 --> 00:05:47,940
שהיה הגרוע ביותר בזמן בדיקה ל

156
00:05:47,940 --> 00:05:49,320
רשימה מקושרת.

157
00:05:49,320 --> 00:05:50,770
האם אנחנו באמת עברנו את כל

158
00:05:50,770 --> 00:05:52,370
צרות של למידה על שולחנות חשיש

159
00:05:52,370 --> 00:05:54,927
אך בסופו של דבר חזרה בה התחלנו?

160
00:05:54,927 --> 00:05:56,975
זה יכול להיות במקרה מתיאורטי

161
00:05:56,975 --> 00:05:59,087
נקודת מבט, אבל בעולם האמיתי,

162
00:05:59,087 --> 00:06:01,199
O (n / k) יכול להיות שיפור עצום על פני

163
00:06:01,199 --> 00:06:03,257
O (n).

164
00:06:03,257 --> 00:06:05,687
תחשוב על זה ככה: תניח k שהוא

165
00:06:05,687 --> 00:06:08,360
10 - היית מעדיף לחכות 100 שניות

166
00:06:08,360 --> 00:06:11,076
או 100 / k?

167
00:06:11,076 --> 00:06:13,252
10 שניות מ-Microsoft Word כדי לסיים

168
00:06:13,252 --> 00:06:15,608
בדיקת איות המסמך שלך.

169
00:06:15,608 --> 00:06:17,368
כפי שראית, פתרון התנגשויות

170
00:06:17,368 --> 00:06:19,018
כרוך בסוג של חיפוש ליניארי אחד או

171
00:06:19,018 --> 00:06:20,558
אחר, אשר מאט את הדברים

172
00:06:20,558 --> 00:06:23,280
במידה ניכרת.

173
00:06:23,280 --> 00:06:25,470
לכן, אתה רוצה לבחור חשיש

174
00:06:25,470 --> 00:06:27,470
פונקציה שמקטינה את הסיכוי של

175
00:06:27,470 --> 00:06:29,170
התנגשויות מתרחשות במקום הראשון.

176
00:06:30,540 --> 00:06:32,120
הנה כמה מאפיינים של חשיש טוב

177
00:06:32,120 --> 00:06:33,400
פונקציות שכדאי לזכור.

178
00:06:34,610 --> 00:06:36,590
פונקציית hash טובה צריכה לעשות שימוש

179
00:06:36,590 --> 00:06:38,830
כל המידע הנמסר על ידי מפתח נתון

180
00:06:38,830 --> 00:06:40,890
על מנת למקסם את מספר

181
00:06:40,890 --> 00:06:42,960
ערכי Hash אפשריים.

182
00:06:42,960 --> 00:06:45,540
לדוגמא, "חתול" אם היו לנו שתי מחרוזות

183
00:06:45,540 --> 00:06:47,980
ו" זחל ", שהיינו רוצה שהם חשיש

184
00:06:47,980 --> 00:06:50,190
למקומות שונים על השולחן.

185
00:06:50,190 --> 00:06:52,410
אם פונקצית חשיש לקחה בחשבון רק

186
00:06:52,410 --> 00:06:54,860
הראשון אחד, שתיים, או אפילו שלוש אותיות

187
00:06:54,860 --> 00:06:57,290
של המחרוזות, התנגשות תתרחש,

188
00:06:57,290 --> 00:06:58,970
מאז שני המילים מתחילות באותה

189
00:06:58,970 --> 00:06:59,560
שלוש אותיות.

190
00:07:01,110 --> 00:07:03,100
ערכי Hash צריכים להתפשט באופן שווה

191
00:07:03,100 --> 00:07:04,790
מעבר לשולחן החשיש.

192
00:07:04,790 --> 00:07:06,300
זה יקטין את אורך מקושר

193
00:07:06,300 --> 00:07:08,050
רשימות צריכה התנגשויות יתרחשו.

194
00:07:09,390 --> 00:07:11,490
זה גם סימן טוב, אם ערך Hash שלך

195
00:07:11,490 --> 00:07:13,600
היא מסוגלת לייצר שונה מאוד

196
00:07:13,600 --> 00:07:15,660
חשיש ערכים למפתחות דומים,

197
00:07:15,660 --> 00:07:17,250
מה שהופך את ההתנגשויות הרבה פחות סביר.

198
00:07:18,420 --> 00:07:21,110
המטרה שלנו היא כניסה מהירה, מחיקה,

199
00:07:21,110 --> 00:07:22,100
ובדיקה.

200
00:07:22,100 --> 00:07:24,060
פונקציית hash ממלאת תפקיד מכריע ב

201
00:07:24,060 --> 00:07:25,520
כל אחד מתהליכים אלה ויהיו

202
00:07:25,520 --> 00:07:26,735
נקרא לעתים קרובות מאוד.

203
00:07:26,735 --> 00:07:29,620
לכן, ודא שהוא מעסיק רק מאוד

204
00:07:29,620 --> 00:07:32,160
פעולות פשוטות, מהירות כדי למזער את הטווח

205
00:07:32,160 --> 00:07:33,360
זמן.

206
00:07:33,360 --> 00:07:34,560
אני מקווה שאתה נהנה זה קצר

207
00:07:34,560 --> 00:07:36,540
מבוא לחשיש שולחנות.

208
00:07:36,540 --> 00:07:41,189
שמי הוא לורן, וזה CS50.