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

2
00:00:11,856 --> 00:00:13,050
>> ROB BOWDEN：你好。

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
我們看到，我們的散列的結構節點
表是要這個樣子。

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
結構節點*未來。

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
所以請注意，負載，
它返回一個布爾值。

24
00:01:16,390 --> 00:01:20,530
您將返回true，如果它是成功的
加載，否則為false。

25
00:01:20,530 --> 00:01:23,990
它需要一個為const char *星級
字典，它是詞典

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
成功打開詞典
我們需要返回false。

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
字典和返回false。

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
因此請記住入門>字是字符
大小長度的字緩衝區加

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
出這個while循環的。

48
00:02:37,280 --> 00:02:42,770
所以我們看到，一旦我們成功
讀一個字到

49
00:02:42,770 --> 00:02:48,270
入門>字，那麼我們將散列
使用我們的哈希函數這個詞。

50
00:02:48,270 --> 00:02:49,580
讓我們來看看
散列函數。

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
你需要認識到的唯一一件事就是
這需要為const char *的話，

55
00:03:04,010 --> 00:03:08,960
所以它採取一個字符串作為輸入，並
返回一個unsigned 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
請注意，我們通過NUM_BUCKETS改裝
所以返回的哈希值

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
現在，哈希表散列是當前
鍊錶哈希表中，並

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
如果出現了錯誤，那麼我們要
返回false，因為負載沒有

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
因此，檢查時，它返回一個布爾值，它
將要指示是否

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
真的，如果不是的話，
我們將返回false。

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
如果我們看一看我們的哈希函數，
我們的哈希函數實際上

99
00:05:29,510 --> 00:05:32,700
是小寫的每個字符
的話。

100
00:05:32,700 --> 00:05:37,580
所以不管資本化
總之，我們的哈希函數是要

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
現在，這個for循環是怎麼回事
過度鍊錶

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
返回true。

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
如果我們分手會發生什麼
出這個for循環？

124
00:06:50,160 --> 00:06:55,110
這意味著我們沒有發現一個條目，
匹配這個詞，在這種情況下，

125
00:06:55,110 --> 00:07:00,220
我們返回false，表明我們的
哈希表中沒有包含這個詞。

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
所以這是不可能卸載到永遠
返回false，而當我們完成後，我們

152
00:08:24,050 --> 00:08:25,320
剛剛返回true。

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