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