1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> ROB אודן: היי.

3
00:00:13,050 --> 00:00:16,210
אני רוב, והחשיש הבה
פתרון את זה.

4
00:00:16,210 --> 00:00:20,070
אז הנה אנחנו הולכים ליישם
שולחן חשיש כללי.

5
00:00:20,070 --> 00:00:24,090
אנו רואים כי צומת struct של החשיש
השולחן הולך להיראות כך.

6
00:00:24,090 --> 00:00:28,710
אז זה הולך להיות מילת char
מערך של אורך בתוספת גודל 1.

7
00:00:28,710 --> 00:00:32,259
אל תשכח 1 מאז מרבי
מילה במילון היא 45

8
00:00:32,259 --> 00:00:35,110
תווים, ולאחר מכן אנחנו הולכים
צריך אופי אחד נוסף עבור

9
00:00:35,110 --> 00:00:37,070
קו נטוי הפוך 0.

10
00:00:37,070 --> 00:00:40,870
>> ולאחר מכן שולחן החשיש שלנו בכל אחד
דלי הולך לאחסון

11
00:00:40,870 --> 00:00:42,320
רשימה מקושרת של צמתים.

12
00:00:42,320 --> 00:00:44,420
אנחנו לא עושים ליניארי חיטוט כאן.

13
00:00:44,420 --> 00:00:48,430
וזאת על מנת לקשר למשנהו
אלמנט בדלי, שאנחנו צריכים

14
00:00:48,430 --> 00:00:51,110
צומת struct * הבא.

15
00:00:51,110 --> 00:00:53,090
אז זה מה שצומת נראית.

16
00:00:53,090 --> 00:00:56,180
עכשיו, הנה היא ההצהרה
משולחן החשיש שלנו.

17
00:00:56,180 --> 00:01:01,910
זה הולך לי 16,384 דליים, אבל
מספר זה לא ממש משנה.

18
00:01:01,910 --> 00:01:05,450
ולבסוף, אנחנו הולכים יש לי
hashtable_size משתנה הגלובלי, אשר

19
00:01:05,450 --> 00:01:08,640
הוא הולך להתחיל כמו 0, וזה
הולך לעקוב אחר כמה מילות

20
00:01:08,640 --> 00:01:10,080
היו במילון שלנו.

21
00:01:10,080 --> 00:01:10,760
בסדר.

22
00:01:10,760 --> 00:01:13,190
>> אז בואו נסתכל על עומס.

23
00:01:13,190 --> 00:01:16,390
אז שם לב שעומס,
היא מחזירה bool.

24
00:01:16,390 --> 00:01:20,530
אתה חוזר נכון אם זה היה בהצלחה
טעון ושקר אחר.

25
00:01:20,530 --> 00:01:23,990
וזה לוקח * כוכב char const
מילון, שהוא המילון

26
00:01:23,990 --> 00:01:25,280
כי אנחנו רוצים לפתוח.

27
00:01:25,280 --> 00:01:27,170
אז זה הדבר הראשון
אנחנו הולכים לעשות.

28
00:01:27,170 --> 00:01:30,420
אנחנו הולכים fopen המילון
קריאה, ואנחנו הולכים לי

29
00:01:30,420 --> 00:01:34,700
כדי לוודא שזה הצליח כל כך אם
זה חזר NULL, אז אנחנו לא

30
00:01:34,700 --> 00:01:37,440
בהצלחה לפתוח את המילון
ואנחנו צריכים לחזור שווא.

31
00:01:37,440 --> 00:01:41,580
>> אבל בהנחה שזה עשה בהצלחה
פתוח, אז אנחנו רוצים לקרוא

32
00:01:41,580 --> 00:01:42,400
במילון.

33
00:01:42,400 --> 00:01:46,210
אז לשמור על הלולאה עד שנמצא כמה
סיבה לפרוץ את זה

34
00:01:46,210 --> 00:01:47,570
לולאה שבו אנו נראה.

35
00:01:47,570 --> 00:01:51,780
אז לשמור על לולאות, ועכשיו אנחנו הולכים
לmalloc צומת אחת.

36
00:01:51,780 --> 00:01:56,800
וכמובן, אנחנו צריכים שגיאת בדיקה
שוב כך שאם mallocing לא הצליח

37
00:01:56,800 --> 00:02:00,660
ואנחנו רוצים לפרוק את כל צומת שאנחנו
קרה לי malloc לפני, סגור את

38
00:02:00,660 --> 00:02:02,590
מילון ותמורת שווא.

39
00:02:02,590 --> 00:02:07,440
>> אבל התעלמות שאנחנו בהנחה,
הצלחנו, אז אנחנו רוצים להשתמש fscanf

40
00:02:07,440 --> 00:02:12,400
לקרוא לו מילה אחת משלנו
מילון לצומת שלנו.

41
00:02:12,400 --> 00:02:17,310
אז לזכור שמילה כניסה-> הוא char
מילת חיץ באורך בתוספת גודל

42
00:02:17,310 --> 00:02:20,300
אחד שאנחנו הולכים
לאחסן את המילה פנימה

43
00:02:20,300 --> 00:02:25,280
אז fscanf הולך לחזור 1 עוד
כפי שהוא היה מסוגל לקרוא בהצלחה

44
00:02:25,280 --> 00:02:26,750
מילה מהקובץ.

45
00:02:26,750 --> 00:02:31,030
>> אם אחד שגיאה קורה או שנגיע
סוף הקובץ, זה לא יהיה

46
00:02:31,030 --> 00:02:34,950
בתמורה 1 ובמקרה זה אם זה לא
בתמורה 1, אנחנו סוף סוף הולכים לשבור

47
00:02:34,950 --> 00:02:37,280
מתוך לולאה בזמן זה.

48
00:02:37,280 --> 00:02:42,770
כך אנו רואים כי ברגע שיש לנו בהצלחה
קראת את מילה לתוך

49
00:02:42,770 --> 00:02:48,270
כניסה-> מילה, ואז אנחנו הולכים לחשיש
מילה שמשתמשת בפונקצית hash שלנו.

50
00:02:48,270 --> 00:02:49,580
בואו נסתכל על
פונקציית hash.

51
00:02:49,580 --> 00:02:52,430

52
00:02:52,430 --> 00:02:55,610
>> אז אתה לא באמת צריך
כדי להבין את זה.

53
00:02:55,610 --> 00:02:59,460
ובעצם, אנחנו פשוט משכתי את זה
חשיש פונקציה מהאינטרנט.

54
00:02:59,460 --> 00:03:04,010
הדבר היחיד שאתה צריך להכיר הוא
כי זה לוקח מילת char * const,

55
00:03:04,010 --> 00:03:08,960
כך שזה לוקח מחרוזת כקלט ו
חוזר int חתום כפלט.

56
00:03:08,960 --> 00:03:12,360
אז זה כל פונקצית חשיש הוא, האם זה
לוקח בקלט, זה נותן לך

57
00:03:12,360 --> 00:03:14,490
מדד לשולחן החשיש.

58
00:03:14,490 --> 00:03:18,530
שים לב שאנחנו modding ידי NUM_BUCKETS
כך חזר את ערך Hash

59
00:03:18,530 --> 00:03:21,730
למעשה הוא מדד לשולחן החשיש
ולא מעבר למדד

60
00:03:21,730 --> 00:03:24,320
גבולות של המערך.

61
00:03:24,320 --> 00:03:27,855
>> אז בהתחשב בכך שפונקצית חשיש, אנחנו הולכים
חשיש המילה שאנו קוראים

62
00:03:27,855 --> 00:03:31,700
מהמילון ולאחר מכן אנחנו הולכים
לשימוש, כי יש להכניס את

63
00:03:31,700 --> 00:03:33,750
כניסה לשולחן החשיש.

64
00:03:33,750 --> 00:03:38,830
עכשיו, חשיש hashtable הוא הנוכחי
רשימה מקושרת בטבלת החשיש, ו

65
00:03:38,830 --> 00:03:41,410
זה אפשרי מאוד כי הוא פשוט NULL.

66
00:03:41,410 --> 00:03:45,640
אנחנו רוצים להכניס את הכניסה שלנו ב
התחלה של רשימה מקושרת זה, וכך

67
00:03:45,640 --> 00:03:48,910
אנחנו הולכים יש לי הכניסה הנוכחית שלנו
תצביע על מה ששולחן החשיש כיום

68
00:03:48,910 --> 00:03:54,030
נקודות ולאז אנחנו הולכים לחנות
בשולחן החשיש בחשיש

69
00:03:54,030 --> 00:03:55,350
הכניסה הנוכחית.

70
00:03:55,350 --> 00:03:59,320
>> אז שתי שורות אלה להכניס בהצלחה
הכניסה בתחילת

71
00:03:59,320 --> 00:04:02,270
רשימה מקושרת במדד
בטבלת הגיבוב.

72
00:04:02,270 --> 00:04:04,900
ברגע שנסיים עם זה, אנחנו יודעים
שמצאנו מילה אחרת ב

73
00:04:04,900 --> 00:04:07,800
מילון ולהגדיל שוב.

74
00:04:07,800 --> 00:04:13,960
אז אנחנו ממשיכים לעשות את זה עד fscanf
לבסוף חוזר משהו שאינו 1 ב

75
00:04:13,960 --> 00:04:18,560
שנקודה לזכור שאנחנו צריכים
כניסה חופשית, ולכן עד כאן, אנחנו malloced

76
00:04:18,560 --> 00:04:21,329
כניסה וניסינו לקרוא משהו
מהמילון.

77
00:04:21,329 --> 00:04:24,110
ואנחנו לא קראנו בהצלחה
משהו מהמילון שבי

78
00:04:24,110 --> 00:04:27,440
מקרה אנחנו צריכים לשחרר את הערך שאנו
אף פעם לא ממש לשים לשולחן החשיש

79
00:04:27,440 --> 00:04:29,110
ולבסוף לשבור.

80
00:04:29,110 --> 00:04:32,750
>> ברגע שאנו לפרוץ החוצה, אנחנו צריכים לראות, טובים,
היה לנו לפרוץ החוצה, כי יש

81
00:04:32,750 --> 00:04:35,840
הייתה שגיאה בקריאה מהקובץ, או
היה לנו לפרוץ החוצה בגלל שאנחנו הגענו

82
00:04:35,840 --> 00:04:37,120
סוף הקובץ?

83
00:04:37,120 --> 00:04:40,150
אם הייתה טעות, אז אנחנו רוצים
בתמורת שווא בגלל עומס לא

84
00:04:40,150 --> 00:04:43,260
להצליח, ותוך כדי התהליך, אנחנו רוצים
לפרוק את כל הדברים אשר אנו קוראים

85
00:04:43,260 --> 00:04:45,670
ובסגור את קובץ המילון.

86
00:04:45,670 --> 00:04:48,740
בהנחה שאנחנו לא מצליחים, אז אנחנו פשוט
עדיין צריכה לסגור את המילון

87
00:04:48,740 --> 00:04:51,970
להגיש, ולבסוף לחזור נכון מאז
אנחנו כבר נטענו בהצלחה

88
00:04:51,970 --> 00:04:53,040
מילון.

89
00:04:53,040 --> 00:04:54,420
וזהו זה לעומס.

90
00:04:54,420 --> 00:04:59,020
>> אז עכשיו לבדוק, בהתחשב שולחן חשיש טעון,
הוא הולך להיראות כך.

91
00:04:59,020 --> 00:05:02,690
אז לבדוק, היא מחזירה bool, אשר
הוא הולך לציין אם

92
00:05:02,690 --> 00:05:07,530
עבר ב- char מילה *, בין אם
מחרוזת חלף-בהיא במילון שלנו.

93
00:05:07,530 --> 00:05:10,530
אז אם זה במילון, אם הוא
בטבלת הגיבוב שלנו, נחזור

94
00:05:10,530 --> 00:05:13,380
נכון, ואם זה לא,
אנו בתמורת שווא.

95
00:05:13,380 --> 00:05:17,770
בהינתן מילה חלפה-בזה, אנחנו
הולך חשיש המילה.

96
00:05:17,770 --> 00:05:22,020
>> עכשיו, דבר חשוב להכיר הוא
כי בעומס, ידעו שכל

97
00:05:22,020 --> 00:05:25,820
המילים הולכות להיות באותיות קטנות,
אבל כאן, אנחנו לא כל כך בטוחים.

98
00:05:25,820 --> 00:05:29,510
אם נסתכל על פונקציית hash שלנו,
פונקציית hash שלנו בעצם

99
00:05:29,510 --> 00:05:32,700
הוא lowercasing כל תו
של המילה.

100
00:05:32,700 --> 00:05:37,580
אז ללא קשר לשווי של
מילה, פונקציית hash שלנו הולכת

101
00:05:37,580 --> 00:05:42,270
להחזיר את אותו מדד לכל
היוון הוא כפי שהוא היה צריך

102
00:05:42,270 --> 00:05:45,280
חזרתי לאותיות קטנות לחלוטין
גרסה של המילה.

103
00:05:45,280 --> 00:05:45,950
בסדר.

104
00:05:45,950 --> 00:05:47,410
>> אז זה המדד שלנו.

105
00:05:47,410 --> 00:05:49,790
זה שולחן החשיש למילה זו.

106
00:05:49,790 --> 00:05:52,940
עכשיו, זה ללולאה הולך
לכל רחבי הרשימה המקושרת

107
00:05:52,940 --> 00:05:55,000
שהיה במדד זה.

108
00:05:55,000 --> 00:05:59,630
אז שמתי לב שאנו מאתחלים כניסה
כדי להצביע על מדד זה.

109
00:05:59,630 --> 00:06:03,480
אנחנו הולכים להמשיך בזמן שהכניסה עושה
לא NULL שווה, ולזכור כי

110
00:06:03,480 --> 00:06:08,350
מעדכן את המצביע ברשימה המקושרת שלנו
כניסה שווה כניסה-> הבאה, ולכן יש לי

111
00:06:08,350 --> 00:06:13,840
נקודת הכניסה הנוכחית שלנו
הפריט הבא ברשימה מקושרת.

112
00:06:13,840 --> 00:06:14,400
בסדר.

113
00:06:14,400 --> 00:06:19,150
>> אז לכל ערך ברשימה המקושרת,
אנחנו הולכים להשתמש strcasecmp.

114
00:06:19,150 --> 00:06:23,780
זה לא strcmp כי שוב, אנחנו
רוצה לעשות דברים בחוסר רגיש מקרה.

115
00:06:23,780 --> 00:06:28,830
כך אנו משתמשים strcasecmp להשוות את המילה
שהועבר לפונקציה זו

116
00:06:28,830 --> 00:06:31,860
נגד המילה ש
ברשומה זו.

117
00:06:31,860 --> 00:06:35,570
אם היא מחזירה 0, זה אומר שלא היה
משחק, ובמקרה כזה אנחנו רוצים

118
00:06:35,570 --> 00:06:36,630
החזר אמיתי.

119
00:06:36,630 --> 00:06:39,590
מצאנו בהצלחה
מילה בטבלת הגיבוב שלנו.

120
00:06:39,590 --> 00:06:43,040
>> אם לא היה במשחק, אז אנחנו
הולך ללולאה שוב ומסתכלים על

121
00:06:43,040 --> 00:06:43,990
הכניסה הבאה.

122
00:06:43,990 --> 00:06:47,640
ואנחנו נמשיך לולאות בעוד יש
הם ערכים ברשימה מקושר זה.

123
00:06:47,640 --> 00:06:50,160
מה קורה אם אנחנו שוברים
מתוך זה ללולאה?

124
00:06:50,160 --> 00:06:55,110
זה אומר שאנחנו לא מצאנו שכניסה
תאם את המילה הזאת, ובמקרה זה

125
00:06:55,110 --> 00:07:00,220
אנחנו חוזרים שווא כדי לציין ש
שולחן חשיש לא הכיל את המילה הזאת.

126
00:07:00,220 --> 00:07:01,910
וזה אותו לבדיקה.

127
00:07:01,910 --> 00:07:02,540
בסדר.

128
00:07:02,540 --> 00:07:04,790
>> אז בואו נסתכל על גודל.

129
00:07:04,790 --> 00:07:09,280
עכשיו, גודל הולך להיות די פשוט
מאז לזכור בעומס, לכל מילה

130
00:07:09,280 --> 00:07:12,880
גילינו שאנחנו מוגדלים גלובליים
hashtable_size משתנה.

131
00:07:12,880 --> 00:07:15,830
אז פונקצית הגודל היא רק
הולך לחזור כי גלובלי

132
00:07:15,830 --> 00:07:18,150
משתנה, וזהו זה.

133
00:07:18,150 --> 00:07:22,300
>> עכשיו סוף סוף, אנחנו צריכים לפרוק את
מילון פעם אחת את כל מה שעשה.

134
00:07:22,300 --> 00:07:25,340
אז איך אנחנו הולכים לעשות את זה?

135
00:07:25,340 --> 00:07:30,440
ממש כאן, אנחנו לולאה על כל
דליים של טבלת הגיבוב שלנו.

136
00:07:30,440 --> 00:07:33,240
אז יש דליי NUM_BUCKETS.

137
00:07:33,240 --> 00:07:37,490
ועבור כל רשימה מקושרת בהחשיש
שולחן, אנחנו הולכים ללולאה מעל

138
00:07:37,490 --> 00:07:41,070
שלמות של הרשימה המקושרת
לשחרר את כל רכיב.

139
00:07:41,070 --> 00:07:46,070
עכשיו, אנחנו צריכים להיות זהירים, אז הנה לנו
יש לי משתנה זמני זה

140
00:07:46,070 --> 00:07:49,740
אחסון המצביע למשנהו
אלמנט ברשימה המקושרת.

141
00:07:49,740 --> 00:07:52,140
ואז אנחנו הולכים לחופשיים
האלמנט הנוכחי.

142
00:07:52,140 --> 00:07:55,990
>> אנחנו צריכים להיות בטוחים שאנחנו עושים את זה מאז ש
לא יכול פשוט לשחרר את האלמנט הנוכחי

143
00:07:55,990 --> 00:07:59,260
ולאחר מכן נסה לגשת למצביע הבא
מאז רגע ששחררנו אותו

144
00:07:59,260 --> 00:08:00,870
זיכרון הופך להיות לא חוקי.

145
00:08:00,870 --> 00:08:04,990
אז אנחנו צריכים לשמור על סביב מצביע
האלמנט הבא, אז אנחנו יכולים לשחרר את

146
00:08:04,990 --> 00:08:08,360
אלמנט הנוכחי, ולאחר מכן אנו יכולים לעדכן
האלמנט הנוכחי שלנו כדי להצביע על

147
00:08:08,360 --> 00:08:09,590
האלמנט הבא.

148
00:08:09,590 --> 00:08:12,770
>> אנחנו לולאה בזמן שיש אלמנטים
ברשימה מקושרת זה.

149
00:08:12,770 --> 00:08:16,450
אנחנו נעשה את זה בשביל כל הרשימות המקושרות ב
שולחן החשיש, וברגע שנסיים

150
00:08:16,450 --> 00:08:20,180
עם זה, אנחנו כבר נפרקו לחלוטין
שולחן החשיש, ואנחנו נעשו.

151
00:08:20,180 --> 00:08:24,050
כך שזה בלתי אפשרי עבור לפרוק אי פעם
בתמורת שווא, וכשנסיים, אנחנו

152
00:08:24,050 --> 00:08:25,320
רק החזר אמיתי.

153
00:08:25,320 --> 00:08:27,563