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

2
00:00:11,856 --> 00:00:13,050
>> ROB Bowden: Hi.

3
00:00:13,050 --> 00:00:16,210
Tôi Rob, và chúng ta hãy băm
giải pháp này ra.

4
00:00:16,210 --> 00:00:20,070
Vì vậy, ở đây chúng ta sẽ thực hiện
một bảng băm chung.

5
00:00:20,070 --> 00:00:24,090
Chúng ta thấy rằng các nút cấu trúc của băm của chúng tôi
bảng sẽ trông như thế này.

6
00:00:24,090 --> 00:00:28,710
Vì vậy, nó sẽ có một từ char
mảng chiều dài cộng với kích thước 1.

7
00:00:28,710 --> 00:00:32,259
Đừng quên 1 kể từ khi tối đa
từ trong từ điển là 45

8
00:00:32,259 --> 00:00:35,110
ký tự, và sau đó chúng ta sẽ
cần một nhân vật phụ cho

9
00:00:35,110 --> 00:00:37,070
dấu gạch chéo ngược 0.

10
00:00:37,070 --> 00:00:40,870
>> Và sau đó bảng băm của chúng tôi trong mỗi
xô là sẽ lưu một

11
00:00:40,870 --> 00:00:42,320
danh sách liên kết của các nút.

12
00:00:42,320 --> 00:00:44,420
Chúng tôi không làm tuyến tính thăm dò ở đây.

13
00:00:44,420 --> 00:00:48,430
Và như vậy để liên kết đến tiếp theo
yếu tố trong xô, chúng ta cần một

14
00:00:48,430 --> 00:00:51,110
struct node * next.

15
00:00:51,110 --> 00:00:53,090
Vì vậy, đó là những gì một nút như thế nào.

16
00:00:53,090 --> 00:00:56,180
Bây giờ, đây là khai báo
của bảng băm của chúng tôi.

17
00:00:56,180 --> 00:01:01,910
Nó sẽ có 16.384 thùng, nhưng
con số đó không quan trọng.

18
00:01:01,910 --> 00:01:05,450
Và cuối cùng, chúng ta sẽ có
hashtable_size biến toàn cầu,

19
00:01:05,450 --> 00:01:08,640
sẽ bắt đầu là 0, và nó
sẽ theo dõi có bao nhiêu từ

20
00:01:08,640 --> 00:01:10,080
là trong từ điển của chúng tôi.

21
00:01:10,080 --> 00:01:10,760
Được rồi.

22
00:01:10,760 --> 00:01:13,190
>> Vì vậy, chúng ta hãy nhìn vào tải.

23
00:01:13,190 --> 00:01:16,390
Vì vậy, nhận thấy rằng tải,
nó trả về một bool.

24
00:01:16,390 --> 00:01:20,530
Bạn trở về đúng nếu nó là thành công
nạp và sai khác.

25
00:01:20,530 --> 00:01:23,990
Và phải mất một char * const sao
từ điển, mà là từ điển

26
00:01:23,990 --> 00:01:25,280
mà chúng tôi muốn mở.

27
00:01:25,280 --> 00:01:27,170
Vì vậy, đó là điều đầu tiên
chúng ta sẽ làm.

28
00:01:27,170 --> 00:01:30,420
Chúng ta sẽ fopen từ điển cho
đọc, và chúng ta sẽ có

29
00:01:30,420 --> 00:01:34,700
để đảm bảo rằng nó đã thành công vì vậy nếu
nó trở về NULL, sau đó chúng tôi đã không

30
00:01:34,700 --> 00:01:37,440
mở thành công điển
và chúng ta cần phải trả về false.

31
00:01:37,440 --> 00:01:41,580
>> Nhưng giả định rằng nó đã thành công
mở, sau đó chúng tôi muốn đọc

32
00:01:41,580 --> 00:01:42,400
từ điển.

33
00:01:42,400 --> 00:01:46,210
Vì vậy, giữ vòng lặp cho đến khi chúng tôi tìm thấy một số
lý do để thoát ra khỏi này

34
00:01:46,210 --> 00:01:47,570
vòng lặp mà chúng ta sẽ thấy.

35
00:01:47,570 --> 00:01:51,780
Vì vậy, giữ vòng lặp, và bây giờ chúng ta sẽ
để malloc một nút duy nhất.

36
00:01:51,780 --> 00:01:56,800
Và tất nhiên, chúng ta cần phải kiểm tra lỗi
một lần nữa vì vậy nếu mallocing đã không thành công

37
00:01:56,800 --> 00:02:00,660
và chúng tôi muốn dỡ bỏ bất kỳ nút mà chúng ta
đã xảy ra với malloc trước, đóng cửa

38
00:02:00,660 --> 00:02:02,590
từ điển và trả về false.

39
00:02:02,590 --> 00:02:07,440
>> Nhưng bỏ qua mà, giả sử chúng ta
đã thành công, sau đó chúng tôi muốn sử dụng fscanf

40
00:02:07,440 --> 00:02:12,400
để đọc một từ duy nhất từ ​​chúng tôi
từ điển vào nút của chúng tôi.

41
00:02:12,400 --> 00:02:17,310
Vì vậy, hãy nhớ rằng từ nhập cảnh> là char
đệm từ có độ dài cộng với kích thước

42
00:02:17,310 --> 00:02:20,300
mà chúng ta đang đi
lưu trữ từ nhập

43
00:02:20,300 --> 00:02:25,280
Vì vậy, fscanf sẽ trả lại 1 miễn
vì nó đã có thể đọc thành công

44
00:02:25,280 --> 00:02:26,750
từ từ tập tin.

45
00:02:26,750 --> 00:02:31,030
>> Nếu một trong hai lỗi xảy ra hoặc chúng tôi đạt được
cuối của tập tin, nó sẽ không

46
00:02:31,030 --> 00:02:34,950
trả lại 1 trong trường hợp này nếu nó không
trở về 1, chúng tôi cuối cùng sẽ phá vỡ

47
00:02:34,950 --> 00:02:37,280
ra khỏi vòng lặp trong khi điều này.

48
00:02:37,280 --> 00:02:42,770
Vì vậy, chúng ta thấy rằng một khi chúng ta đã thành công
đọc một từ vào

49
00:02:42,770 --> 00:02:48,270
entry-> từ, sau đó chúng ta sẽ băm
từ đó sử dụng hàm băm của chúng tôi.

50
00:02:48,270 --> 00:02:49,580
Chúng ta hãy nhìn vào
hàm băm.

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

52
00:02:52,430 --> 00:02:55,610
>> Vì vậy, bạn không thực sự cần
để hiểu được điều này.

53
00:02:55,610 --> 00:02:59,460
Và trên thực tế, chúng ta chỉ cần kéo này
băm chức năng từ internet.

54
00:02:59,460 --> 00:03:04,010
Điều duy nhất bạn cần phải nhận ra là
rằng điều này có một const char * từ,

55
00:03:04,010 --> 00:03:08,960
do đó, nó tham gia một chuỗi như là đầu vào và
trả lại một int unsigned như đầu ra.

56
00:03:08,960 --> 00:03:12,360
Vì vậy, đó là tất cả một hàm băm được, là nó
mất trong một đầu vào, nó sẽ cho bạn một

57
00:03:12,360 --> 00:03:14,490
chỉ số vào bảng băm.

58
00:03:14,490 --> 00:03:18,530
Chú ý rằng bạn chỉnh sửa bởi NUM_BUCKETS
vì vậy giá trị băm trở lại

59
00:03:18,530 --> 00:03:21,730
thực sự là một chỉ số vào bảng băm
và không chỉ vượt ra ngoài

60
00:03:21,730 --> 00:03:24,320
giới hạn của mảng.

61
00:03:24,320 --> 00:03:27,855
>> Vì vậy, cho rằng hàm băm, chúng ta sẽ
để băm từ mà chúng ta đọc

62
00:03:27,855 --> 00:03:31,700
từ điển và sau đó chúng ta sẽ
sử dụng có để chèn

63
00:03:31,700 --> 00:03:33,750
nhập cảnh vào bảng băm.

64
00:03:33,750 --> 00:03:38,830
Bây giờ, băm Hashtable là hiện tại
danh sách liên kết trong bảng băm, và

65
00:03:38,830 --> 00:03:41,410
nó rất có thể đó chỉ là NULL.

66
00:03:41,410 --> 00:03:45,640
Chúng tôi muốn chèn mục của chúng tôi tại
bắt đầu của danh sách liên kết này, và như vậy

67
00:03:45,640 --> 00:03:48,910
chúng ta sẽ có mục hiện tại của chúng tôi
trỏ đến những gì các bảng băm hiện

68
00:03:48,910 --> 00:03:54,030
điểm và sau đó chúng ta sẽ lưu trữ
trong bảng băm vào băm

69
00:03:54,030 --> 00:03:55,350
mục hiện hành.

70
00:03:55,350 --> 00:03:59,320
>> Vì vậy, hai dòng chèn thành công
nhập cảnh tại các đầu

71
00:03:59,320 --> 00:04:02,270
danh sách liên kết tại chỉ số đó
trong bảng băm.

72
00:04:02,270 --> 00:04:04,900
Một khi chúng ta đang thực hiện với đó, chúng tôi biết
mà chúng ta tìm thấy một từ khác trong

73
00:04:04,900 --> 00:04:07,800
Từ điển và chúng tôi tăng một lần nữa.

74
00:04:07,800 --> 00:04:13,960
Vì vậy, chúng tôi tiếp tục làm điều đó cho đến khi fscanf
cuối cùng trả về một cái gì đó không 1 tại

75
00:04:13,960 --> 00:04:18,560
thời điểm đó hãy nhớ rằng chúng ta cần phải
vào cửa miễn phí, vì vậy ở đây, chúng tôi malloced một

76
00:04:18,560 --> 00:04:21,329
nhập cảnh, chúng tôi cố gắng để đọc một cái gì đó
từ điển.

77
00:04:21,329 --> 00:04:24,110
Và chúng tôi đã không đọc thành công
một cái gì đó từ điển, trong đó

78
00:04:24,110 --> 00:04:27,440
trường hợp chúng ta cần phải giải phóng các mục mà chúng ta
không bao giờ thực sự đưa vào bảng băm

79
00:04:27,440 --> 00:04:29,110
và cuối cùng phá vỡ.

80
00:04:29,110 --> 00:04:32,750
>> Một khi chúng ta thoát ra khỏi, chúng ta cần phải nhìn thấy, tốt,
chúng tôi đã phá vỡ ra bởi vì có

81
00:04:32,750 --> 00:04:35,840
được một lỗi đọc từ tập tin, hoặc
chúng tôi đã phá vỡ ra bởi vì chúng tôi đến

82
00:04:35,840 --> 00:04:37,120
kết thúc của tập tin?

83
00:04:37,120 --> 00:04:40,150
Nếu có một lỗi, sau đó chúng tôi muốn
return false vì tải không

84
00:04:40,150 --> 00:04:43,260
thành công, và trong quá trình này, chúng tôi muốn
dỡ bỏ tất cả các từ mà chúng ta đọc

85
00:04:43,260 --> 00:04:45,670
trong và đóng tập tin từ điển.

86
00:04:45,670 --> 00:04:48,740
Giả sử chúng ta đã thành công, sau đó chúng tôi chỉ
vẫn cần phải đóng cửa từ điển

87
00:04:48,740 --> 00:04:51,970
tập tin, và cuối cùng trở về đúng kể từ khi
chúng tôi đã nạp thành công

88
00:04:51,970 --> 00:04:53,040
từ điển.

89
00:04:53,040 --> 00:04:54,420
Và đó là nó cho tải.

90
00:04:54,420 --> 00:04:59,020
>> Vì vậy, bây giờ kiểm tra, đưa ra một bảng băm tải,
sẽ trông như thế này.

91
00:04:59,020 --> 00:05:02,690
Vì vậy, kiểm tra, nó trả về một bool, mà
sẽ chỉ ra cho dù

92
00:05:02,690 --> 00:05:07,530
thông qua trong char * từ, cho dù
chuỗi thông qua-in trong từ điển của chúng tôi.

93
00:05:07,530 --> 00:05:10,530
Vì vậy, nếu nó có trong từ điển, nếu nó là
trong bảng băm của chúng tôi, chúng tôi sẽ trở lại

94
00:05:10,530 --> 00:05:13,380
đúng, và nếu nó không phải,
chúng tôi sẽ trả về false.

95
00:05:13,380 --> 00:05:17,770
Cho từ thông qua trong này, chúng tôi
sẽ băm từ.

96
00:05:17,770 --> 00:05:22,020
>> Bây giờ, một điều quan trọng để nhận ra là
mà trong tải, chúng tôi biết rằng tất cả các

97
00:05:22,020 --> 00:05:25,820
các từ được sẽ thấp hơn trường hợp,
nhưng ở đây, chúng tôi không như vậy chắc chắn.

98
00:05:25,820 --> 00:05:29,510
Nếu chúng ta hãy nhìn vào hàm băm của chúng tôi,
hàm băm của chúng tôi thực sự

99
00:05:29,510 --> 00:05:32,700
được lowercasing mỗi nhân vật
của từ.

100
00:05:32,700 --> 00:05:37,580
Vì vậy, bất kể giá trị vốn hóa của
từ, hàm băm của chúng tôi sẽ

101
00:05:37,580 --> 00:05:42,270
trả lại chỉ số tương tự cho bất cứ điều gì
vốn là như nó sẽ có

102
00:05:42,270 --> 00:05:45,280
trả lại cho một hoàn toàn chữ thường
phiên bản của từ.

103
00:05:45,280 --> 00:05:45,950
Được rồi.

104
00:05:45,950 --> 00:05:47,410
>> Vì vậy, đó là chỉ số của chúng tôi.

105
00:05:47,410 --> 00:05:49,790
Đó là bảng băm cho từ này.

106
00:05:49,790 --> 00:05:52,940
Bây giờ, điều này cho vòng lặp sẽ
đến hơn danh sách liên kết

107
00:05:52,940 --> 00:05:55,000
đó là tại chỉ số đó.

108
00:05:55,000 --> 00:05:59,630
Vì vậy, nhận thấy chúng ta đang khởi nhập
để trỏ đến chỉ số.

109
00:05:59,630 --> 00:06:03,480
Chúng tôi sẽ tiếp tục trong khi nhập không
không NULL bằng nhau, và hãy nhớ rằng

110
00:06:03,480 --> 00:06:08,350
cập nhật con trỏ trong danh sách liên kết của chúng tôi
nhập bằng entry-> tiếp theo, vì vậy có

111
00:06:08,350 --> 00:06:13,840
điểm vào hiện tại của chúng tôi với
mục tiếp theo trong danh sách liên kết.

112
00:06:13,840 --> 00:06:14,400
Được rồi.

113
00:06:14,400 --> 00:06:19,150
>> Vì vậy, cho mỗi mục trong danh sách liên kết,
chúng ta sẽ sử dụng strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Nó không strcmp vì một lần nữa, chúng tôi
muốn làm những điều trường hợp insensitively.

115
00:06:23,780 --> 00:06:28,830
Vì vậy, chúng tôi sử dụng để so sánh strcasecmp từ
đã được thông qua chức năng này

116
00:06:28,830 --> 00:06:31,860
chống lại các từ đó
là trong mục này.

117
00:06:31,860 --> 00:06:35,570
Nếu nó trả về 0, có nghĩa là đã có
một trận đấu, trong trường hợp này chúng tôi muốn

118
00:06:35,570 --> 00:06:36,630
return true.

119
00:06:36,630 --> 00:06:39,590
Chúng tôi tìm thấy thành công
từ trong bảng băm của chúng tôi.

120
00:06:39,590 --> 00:06:43,040
>> Nếu không có một trận đấu, thì chúng ta
đi lặp lại và nhìn vào

121
00:06:43,040 --> 00:06:43,990
mục tiếp theo.

122
00:06:43,990 --> 00:06:47,640
Và chúng tôi sẽ tiếp tục vòng lặp trong khi có
là các mục trong danh sách liên kết này.

123
00:06:47,640 --> 00:06:50,160
Điều gì xảy ra nếu chúng ta phá vỡ
trong số này cho vòng lặp?

124
00:06:50,160 --> 00:06:55,110
Điều đó có nghĩa chúng tôi không tìm thấy một mục mà
kết hợp từ này, trong trường hợp

125
00:06:55,110 --> 00:07:00,220
chúng tôi trả về false để chỉ ra rằng chúng tôi
bảng băm không có từ này.

126
00:07:00,220 --> 00:07:01,910
Và đó là nó để kiểm tra.

127
00:07:01,910 --> 00:07:02,540
Được rồi.

128
00:07:02,540 --> 00:07:04,790
>> Vì vậy, chúng ta hãy nhìn vào kích thước.

129
00:07:04,790 --> 00:07:09,280
Bây giờ, kích thước sẽ là khá đơn giản
kể từ khi nhớ trong tải, cho mỗi từ

130
00:07:09,280 --> 00:07:12,880
chúng tôi thấy chúng tôi tăng lên một toàn cầu
hashtable_size biến.

131
00:07:12,880 --> 00:07:15,830
Vì vậy, các chức năng kích thước chỉ là
sẽ trả lại rằng toàn cầu

132
00:07:15,830 --> 00:07:18,150
biến, và đó là nó.

133
00:07:18,150 --> 00:07:22,300
>> Bây giờ cuối cùng, chúng ta cần phải dỡ bỏ các
từ điển một lần tất cả mọi thứ được thực hiện.

134
00:07:22,300 --> 00:07:25,340
Vì vậy, làm thế nào chúng tôi sẽ làm điều đó?

135
00:07:25,340 --> 00:07:30,440
Ngay tại đây, chúng tôi đang Looping trên tất cả
xô bảng băm của chúng tôi.

136
00:07:30,440 --> 00:07:33,240
Vì vậy, có NUM_BUCKETS xô.

137
00:07:33,240 --> 00:07:37,490
Và cho mỗi danh sách liên kết trong băm của chúng tôi
bảng, chúng ta sẽ vòng qua

138
00:07:37,490 --> 00:07:41,070
toàn bộ danh sách liên kết
giải phóng mỗi yếu tố.

139
00:07:41,070 --> 00:07:46,070
Bây giờ, chúng ta cần phải cẩn thận, vì vậy ở đây chúng tôi
có một biến tạm thời đó là

140
00:07:46,070 --> 00:07:49,740
lưu trữ các con trỏ đến tiếp theo
phần tử trong danh sách liên kết.

141
00:07:49,740 --> 00:07:52,140
Và sau đó chúng tôi sẽ miễn phí
các yếu tố hiện tại.

142
00:07:52,140 --> 00:07:55,990
>> Chúng tôi cần phải chắc chắn chúng tôi làm điều này vì chúng ta
không thể chỉ giải phóng các yếu tố hiện tại

143
00:07:55,990 --> 00:07:59,260
và sau đó cố gắng truy cập vào các con trỏ tới
kể từ khi chúng tôi giải thoát nó

144
00:07:59,260 --> 00:08:00,870
bộ nhớ trở nên không hợp lệ.

145
00:08:00,870 --> 00:08:04,990
Vì vậy, chúng ta cần phải giữ cho xung quanh một con trỏ tới
các yếu tố tiếp theo, sau đó chúng tôi có thể giải phóng

146
00:08:04,990 --> 00:08:08,360
yếu tố hiện tại, và sau đó chúng tôi có thể cập nhật
phần tử hiện tại của chúng tôi để trỏ đến

147
00:08:08,360 --> 00:08:09,590
các yếu tố tiếp theo.

148
00:08:09,590 --> 00:08:12,770
>> Chúng tôi sẽ vòng lặp trong khi có những yếu tố
trong danh sách liên kết này.

149
00:08:12,770 --> 00:08:16,450
Chúng tôi sẽ làm điều đó cho tất cả các danh sách liên kết trong
bảng băm, và một khi chúng ta đang thực hiện

150
00:08:16,450 --> 00:08:20,180
với đó, chúng tôi đã hoàn toàn dỡ
bảng băm, và chúng tôi đang thực hiện.

151
00:08:20,180 --> 00:08:24,050
Vì vậy, nó không thể trút bao giờ
return false, và khi chúng tôi đang thực hiện, chúng tôi

152
00:08:24,050 --> 00:08:25,320
chỉ trả lại sự thật.

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