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
>> דאג LLOYD: עד עכשיו אתה
יודע הרבה על מערכים,

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
הזמן הופך להיות קרוב יותר ל
תטא של 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
אנחנו בדרך כלל קוראים hashcode, בסדר?

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
>> ונניח שאנחנו רצים ג'ון
באמצעות פונקצית חשיש זה

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
ובכן פונקצית חשיש טובה צריכה
להשתמש רק בנתונים שhashed,

117
00:05:27,280 --> 00:05:29,420
ואת כל הנתונים שhashed.

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
אני צריך להיות מסוגל לעשות את זה 10,000
פעמים ואני תמיד מקבלים 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
ואז אני הולך לשמור
iterating דרך מחרוזת ש,

153
00:07:09,560 --> 00:07:15,310
הוספת strstr [י] לסיכום, ולאחר מכן ב
סופו של היום הולך לחזור 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
חוזר כמה hashcode
modded ידי 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
אבל כאשר אתה בעצם הולך
להתחיל hashing נתונים ואחסונו

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
>> אישור אז בואו לבקר זה
שולחן חשיש לשנייה.

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
אולי אנחנו לא צריכים לחפש
כל אלמנטי 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
ואנחנו רצים בארט בחשיש
פונקציה, אנחנו מקבלים 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
לקראת תטא של n.

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
אנחנו יודעים שמערך רק יכול
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 של n,

293
00:14:15,610 --> 00:14:19,590
עכשיו יש לנו 10 רשימות מקושרות,
או 1,000 רשימות מקושרות,

294
00:14:19,590 --> 00:14:24,120
עכשיו זה O של n מתחלק ב -10,
או O של n מחולק ב1,000.

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 פעמים מהר יותר,
או 1,000 פעמים מהר יותר,

300
00:14:36,610 --> 00:14:41,570
כי אנחנו מפיצים אחד ארוך
שרשרת על פני 1,000 רשתות קטנות יותר.

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
>> אשר הוא בממוצע ל
להיות 1,000 פעמים קצרות יותר.

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 המצביעים null.

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, במקום להצביע על null,

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