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
Ako Rob, at hash let ni
solusyon na ito out.

4
00:00:16,210 --> 00:00:20,070
Kaya dito kami ay pagpunta sa ipatupad
isang pangkalahatang hash table.

5
00:00:20,070 --> 00:00:24,090
Nakita namin na ang struct node ng aming hash
talahanayan ay pagpunta sa ganito ang hitsura.

6
00:00:24,090 --> 00:00:28,710
Kaya ito ay pagpunta sa magkaroon ng isang pansamantalang trabaho salita
array ng haba laki ng plus 1.

7
00:00:28,710 --> 00:00:32,259
Huwag kalimutan ang 1 dahil ang maximum
salita sa diksyunaryo ay 45

8
00:00:32,259 --> 00:00:35,110
mga character, at pagkatapos kami ay pagpunta sa
kailangan isa dagdag ng character para sa mga

9
00:00:35,110 --> 00:00:37,070
backslash 0.

10
00:00:37,070 --> 00:00:40,870
>> At pagkatapos ay aming hash talahanayan sa bawat
bucket ay pagpunta sa mag-imbak ng

11
00:00:40,870 --> 00:00:42,320
naka-link na listahan ng mga node.

12
00:00:42,320 --> 00:00:44,420
Hindi namin ginagawa linear probing dito.

13
00:00:44,420 --> 00:00:48,430
At kaya upang mai-link sa susunod
sangkap sa mga bucket, kailangan namin ng isang

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

15
00:00:51,110 --> 00:00:53,090
Kaya na kung ano ang hitsura ng isang node tulad.

16
00:00:53,090 --> 00:00:56,180
Ngayon, dito ay ang deklarasyon
ng aming hash table.

17
00:00:56,180 --> 00:01:01,910
Ito ay pagpunta sa may 16,384 mga bucket, ngunit
numerong iyon ay hindi talagang mahalaga.

18
00:01:01,910 --> 00:01:05,450
At sa wakas, kami ay pagpunta sa may
global variable hashtable_size, na

19
00:01:05,450 --> 00:01:08,640
Pupunta upang simulan off bilang 0, at ito ay
pagpunta sa masubaybayan kung gaano karaming mga salita

20
00:01:08,640 --> 00:01:10,080
ay nasa aming diksyunaryo.

21
00:01:10,080 --> 00:01:10,760
Ayos lang.

22
00:01:10,760 --> 00:01:13,190
>> Kaya ipaalam sa tumagal ng isang pagtingin sa pag-load.

23
00:01:13,190 --> 00:01:16,390
Kaya mapapansin na ang pag-load,
Ibinabalik nito ang isang bool.

24
00:01:16,390 --> 00:01:20,530
Ikaw nagbabalik ng tunay na kung matagumpay na ito ay
na-load at hindi totoo kung hindi man.

25
00:01:20,530 --> 00:01:23,990
At ito ay tumatagal ng isang const pansamantalang trabaho * star
diksyonaryo, kung saan ay ang diksyunaryo

26
00:01:23,990 --> 00:01:25,280
na nais naming buksan.

27
00:01:25,280 --> 00:01:27,170
Kaya iyon ang unang bagay
kami ay pagpunta sa gawin.

28
00:01:27,170 --> 00:01:30,420
Kami ay pagpunta sa fopen sa diksyunaryo para sa
pagbabasa, at kami ay pagpunta sa may

29
00:01:30,420 --> 00:01:34,700
upang matiyak na ito Nagtagumpay kaya kung
ibinalik na ito null, pagkatapos kami ay hindi

30
00:01:34,700 --> 00:01:37,440
Matagumpay na buksan ang diksyunaryo
at kailangan namin upang bumalik hindi totoo.

31
00:01:37,440 --> 00:01:41,580
>> Ngunit sa pag-aakala na matagumpay na ginawa ito
bukas, pagkatapos ay nais naming basahin ang

32
00:01:41,580 --> 00:01:42,400
diksiyunaryo.

33
00:01:42,400 --> 00:01:46,210
Kaya panatilihin looping hanggang sa mahanap namin ang ilang
dahilan upang masira out ng ito

34
00:01:46,210 --> 00:01:47,570
loop na kung saan ipapakita namin makita.

35
00:01:47,570 --> 00:01:51,780
Kaya panatilihin looping, at ngayon kami ay pagpunta
sa malloc isang solong node.

36
00:01:51,780 --> 00:01:56,800
At siyempre, kailangan naming i-check error
muli kaya kung mallocing hindi nagtagumpay

37
00:01:56,800 --> 00:02:00,660
at gusto naming mag-ibis anumang node na namin
nangyari bago sa malloc, isara ang

38
00:02:00,660 --> 00:02:02,590
diksyunaryo at bumalik hindi totoo.

39
00:02:02,590 --> 00:02:07,440
>> Ngunit hindi papansin ang na, sa pag-aakala namin
nagtagumpay, pagkatapos ay nais naming gamitin fscanf

40
00:02:07,440 --> 00:02:12,400
basahin ang isang solong salita mula sa aming
diksyunaryo sa aming mga node.

41
00:02:12,400 --> 00:02:17,310
Kaya tandaan na ang entry-> salita ay ang pansamantalang trabaho
salita buffer ng haba laki ng plus

42
00:02:17,310 --> 00:02:20,300
isa na kami ng pagpunta sa
mag-imbak ang salitang in

43
00:02:20,300 --> 00:02:25,280
Kaya fscanf ay pagpunta upang bumalik 1 hangga't
dahil ito ay matagumpay na mai-basahin ang isang

44
00:02:25,280 --> 00:02:26,750
salita mula sa file.

45
00:02:26,750 --> 00:02:31,030
>> Kung nangyari ang alinman sa isang error o maabot namin
sa dulo ng file, ito ay hindi

46
00:02:31,030 --> 00:02:34,950
bumalik 1 sa kasong ito kung hindi
bumalik 1, sa wakas kami ay pagpunta sa masira

47
00:02:34,950 --> 00:02:37,280
out ng ito habang loop.

48
00:02:37,280 --> 00:02:42,770
Kaya nakikita natin na sa sandaling matagumpay na mayroon kami
basahin ang isang salita sa

49
00:02:42,770 --> 00:02:48,270
entry-> salita, pagkatapos kami ay pagpunta sa hash
ang salitang iyon gamit ang aming hash.

50
00:02:48,270 --> 00:02:49,580
Hayaan ang kumuha ng isang pagtingin sa
ang hash.

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

52
00:02:52,430 --> 00:02:55,610
>> Kaya huwag talagang kailangan mo
upang maunawaan ito.

53
00:02:55,610 --> 00:02:59,460
At talagang, na nakuha namin ito lamang
hash mula sa internet.

54
00:02:59,460 --> 00:03:04,010
Ang tanging bagay na kailangan mo upang makilala ang
na ito ay tumatagal ng isang const pansamantalang trabaho * salita,

55
00:03:04,010 --> 00:03:08,960
kaya tumatagal string na ito bilang input at
bumabalik isang wala pang kontratang int bilang output.

56
00:03:08,960 --> 00:03:12,360
Kaya iyon ang lahat ng hash function na ay, ay ito
tumatagal sa isang input, nagbibigay ito sa iyo ng isang

57
00:03:12,360 --> 00:03:14,490
index sa hash table.

58
00:03:14,490 --> 00:03:18,530
Pansinin na aming Modding sa pamamagitan ng NUM_BUCKETS
kaya ibinalik ang halaga ng hash

59
00:03:18,530 --> 00:03:21,730
talaga ay isang index sa hash talahanayan
at hindi ini-index nang higit sa

60
00:03:21,730 --> 00:03:24,320
hanggahan ng array.

61
00:03:24,320 --> 00:03:27,855
>> Kaya ibinigay na hash, ipinapadala namin ng pagpunta
sa hash ang salita na aming basahin

62
00:03:27,855 --> 00:03:31,700
mula sa diksyunaryo at pagkatapos kami ay pagpunta
gamitin na may upang ipasok ang

63
00:03:31,700 --> 00:03:33,750
entry sa hash table.

64
00:03:33,750 --> 00:03:38,830
Ngayon, hashtable hash ay ang kasalukuyang
naka-link na listahan sa hash talahanayan, at

65
00:03:38,830 --> 00:03:41,410
ito ay napaka posible na lamang null.

66
00:03:41,410 --> 00:03:45,640
Gusto naming upang ipasok ang aming entry sa
simula ng ito na naka-link listahan, at sa gayon

67
00:03:45,640 --> 00:03:48,910
kami ay pagpunta sa may aming kasalukuyang entry
tumuturo sa kung ano ang hash talahanayan sa kasalukuyan

68
00:03:48,910 --> 00:03:54,030
mga punto upang at pagkatapos kami ay pagpunta upang mag-imbak
sa hash talahanayan sa hash

69
00:03:54,030 --> 00:03:55,350
ang kasalukuyang entry.

70
00:03:55,350 --> 00:03:59,320
>> Kaya matagumpay na ipasok ang dalawang mga linya
ang entry sa simula ng

71
00:03:59,320 --> 00:04:02,270
naka-link na listahan sa index na
sa hash table.

72
00:04:02,270 --> 00:04:04,900
Sa sandaling tapos na kami doon, alam namin
nakakita kami ng isa pang salita sa

73
00:04:04,900 --> 00:04:07,800
diksyunaryo at kami dinagdagan muli.

74
00:04:07,800 --> 00:04:13,960
Kaya panatilihin namin ang paggawa na hanggang fscanf
sa wakas ay nagbabalik ng isang bagay na hindi pang 1 sa

75
00:04:13,960 --> 00:04:18,560
na kung saang tandaan na kailangan namin upang
libreng entry, kaya hanggang dito, malloced kami ng isang

76
00:04:18,560 --> 00:04:21,329
entry at sinubukan naming basahin ang isang bagay
mula sa diksyunaryo.

77
00:04:21,329 --> 00:04:24,110
At kami ay hindi matagumpay na basahin
isang bagay mula sa diksyunaryo kung saan

78
00:04:24,110 --> 00:04:27,440
sakaling kailangan namin upang palayain ang entry na kami
hindi kailanman talagang ilagay sa hash talahanayan

79
00:04:27,440 --> 00:04:29,110
at sa wakas ay masira.

80
00:04:29,110 --> 00:04:32,750
>> Sa sandaling magsimula namin, kailangan naming makita, mahusay,
ay masira kami out dahil mayroong

81
00:04:32,750 --> 00:04:35,840
ay isang error sa pagbabasa mula sa file, o
ay masira kami out dahil naabot namin

82
00:04:35,840 --> 00:04:37,120
sa dulo ng file?

83
00:04:37,120 --> 00:04:40,150
Kung nagkaroon ng error, pagkatapos ay nais naming
bumalik hindi totoo dahil ang hindi pagkarga

84
00:04:40,150 --> 00:04:43,260
magtagumpay, at sa proseso, nais naming
alisan ng bala lahat ng mga salita na aming basahin

85
00:04:43,260 --> 00:04:45,670
sa at isara ang file na diksiyunaryo.

86
00:04:45,670 --> 00:04:48,740
Sa pag-aakala namin ginawa magtagumpay, pagkatapos namin lamang
kailangan pa rin upang isara ang diksyunaryo

87
00:04:48,740 --> 00:04:51,970
maghain, at sa wakas ay nagbabalik ng tunay na mula noong
matagumpay naming na-load ang

88
00:04:51,970 --> 00:04:53,040
diksiyunaryo.

89
00:04:53,040 --> 00:04:54,420
At na ito para sa pag-load.

90
00:04:54,420 --> 00:04:59,020
>> Kaya ngayon suriin, bibigyan ng load hash talahanayan,
ay pagpunta sa ganito ang hitsura.

91
00:04:59,020 --> 00:05:02,690
Kaya tingnan, nagbabalik ito ng isang bool, na
Pupunta upang ipahiwatig kung ang

92
00:05:02,690 --> 00:05:07,530
pumasang-in pansamantalang trabaho * salita, kung ang
pumasang-in string ay nasa aming diksyunaryo.

93
00:05:07,530 --> 00:05:10,530
Kaya kung ito ay nasa sa diksyunaryo, kung ito ay
sa aming hash talahanayan, magkakaroon kami bumalik

94
00:05:10,530 --> 00:05:13,380
totoo, at kung hindi,
ay namin bumalik false.

95
00:05:13,380 --> 00:05:17,770
Given na ito ang pumasa sa-sa salita, kami ay
pagpunta sa hash ang salita.

96
00:05:17,770 --> 00:05:22,020
>> Ngayon, ang isang mahalagang bagay upang makilala ang
na sa pag-load, alam namin na ang lahat ng

97
00:05:22,020 --> 00:05:25,820
ang mga salita ay pagpunta sa maging mas mababa kaso,
ngunit dito, hindi kami kaya sigurado.

98
00:05:25,820 --> 00:05:29,510
Kung tumagal kami ng isang tumingin sa aming hash,
ang aming hash talaga

99
00:05:29,510 --> 00:05:32,700
ay lowercasing bawat karakter
ng salita.

100
00:05:32,700 --> 00:05:37,580
Kaya anuman ang capitalization ng
salita, ang aming hash ay pagpunta sa

101
00:05:37,580 --> 00:05:42,270
ibalik ang parehong index para sa anumang mga
capitalization ay gaya ng ang mga ito ay may

102
00:05:42,270 --> 00:05:45,280
ibinalik para sa isang ganap na lowercase
bersyon ng salita.

103
00:05:45,280 --> 00:05:45,950
Ayos lang.

104
00:05:45,950 --> 00:05:47,410
>> Kaya iyon ang aming index.

105
00:05:47,410 --> 00:05:49,790
Ito ay ang talahanayan ng hash para sa salitang ito.

106
00:05:49,790 --> 00:05:52,940
Ngayon, ito para sa loop ay pagpunta
sa ibabaw ng naka-link na listahan

107
00:05:52,940 --> 00:05:55,000
na noon ay sa index iyon.

108
00:05:55,000 --> 00:05:59,630
Kaya't mapapansin ay Sinisimulan namin entry
upang tumuro sa index iyon.

109
00:05:59,630 --> 00:06:03,480
Kami ay pagpunta upang magpatuloy habang entry gumagana
hindi katumbas null, at tandaan na

110
00:06:03,480 --> 00:06:08,350
ina-update ang pointer sa aming listahan na naka-link
entry ay katumbas ng entry-> susunod, kaya may

111
00:06:08,350 --> 00:06:13,840
aming kasalukuyang entry point sa
susunod na item sa naka-link na listahan.

112
00:06:13,840 --> 00:06:14,400
Ayos lang.

113
00:06:14,400 --> 00:06:19,150
>> Kaya para sa bawat entry sa naka-link na listahan,
kami ay pagpunta sa gamitin strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Hindi ito strcmp dahil sa sandaling muli, namin
gusto gawin kaso bagay insensitively.

115
00:06:23,780 --> 00:06:28,830
Kaya ginagamit namin strcasecmp upang ihambing ang salitang
na pumasa sa mga ito sa function na

116
00:06:28,830 --> 00:06:31,860
laban sa mga salita na
ay nasa ang entry na ito.

117
00:06:31,860 --> 00:06:35,570
Kung nagbabalik ito 0, ibig sabihin nagkaroon
isang tugma, kung saan nais naming

118
00:06:35,570 --> 00:06:36,630
nagbabalik ng tunay.

119
00:06:36,630 --> 00:06:39,590
Kami matagumpay nahanap ang
salita sa aming hash table.

120
00:06:39,590 --> 00:06:43,040
>> Kung nagkaroon hindi isang tugma, pagkatapos kami ay
pagpunta sa loop muli at tumingin sa

121
00:06:43,040 --> 00:06:43,990
susunod na entry.

122
00:06:43,990 --> 00:06:47,640
At patuloy kaming looping habang doon
mga entry sa naka-link na ito listahan.

123
00:06:47,640 --> 00:06:50,160
Ano ang mangyayari kung masira namin
out na ito para sa loop?

124
00:06:50,160 --> 00:06:55,110
Nangangahulugan iyon na hindi kami nakahanap ng isang entry na
tugmang salita na ito, kung saan

125
00:06:55,110 --> 00:07:00,220
bumalik kami huwad upang ipahiwatig na ang aming
hash talahanayan ay hindi naglalaman ng salitang ito.

126
00:07:00,220 --> 00:07:01,910
At na ito para sa check.

127
00:07:01,910 --> 00:07:02,540
Ayos lang.

128
00:07:02,540 --> 00:07:04,790
>> Kaya ipaalam sa tumagal ng isang pagtingin sa laki.

129
00:07:04,790 --> 00:07:09,280
Ngayon, laki ay magiging kaakit-akit na simple
dahil tandaan sa pag-load, para sa bawat salita

130
00:07:09,280 --> 00:07:12,880
nakita namin incremented kami ng isang global
variable hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Kaya ang function ng laki ay lamang
pagpunta sa bumalik na global

132
00:07:15,830 --> 00:07:18,150
variable, at iyon ito.

133
00:07:18,150 --> 00:07:22,300
>> Ngayon sa wakas, kailangan naming mag-ibis ang
diksyunaryo-sabay ang lahat ng bagay tapos na.

134
00:07:22,300 --> 00:07:25,340
Kaya paano kami makapupunta sa gawin iyon?

135
00:07:25,340 --> 00:07:30,440
Kanan dito, kami ay looping sa ibabaw ng lahat
mga bucket ng aming hash table.

136
00:07:30,440 --> 00:07:33,240
Kaya may mga NUM_BUCKETS bucket.

137
00:07:33,240 --> 00:07:37,490
At para sa bawat naka-link na listahan sa aming hash
talahanayan, kami ay pagpunta sa loop sa ibabaw ng

138
00:07:37,490 --> 00:07:41,070
kabuuan ng naka-link na listahan
pagbabakante bawat elemento.

139
00:07:41,070 --> 00:07:46,070
Ngayon, kailangan naming maging maingat, kaya dito kami
magkaroon ng isang pansamantalang variable na

140
00:07:46,070 --> 00:07:49,740
pag-iimbak ang pointer sa susunod
elemento sa naka-link na listahan.

141
00:07:49,740 --> 00:07:52,140
At pagkatapos ay kami ay pagpunta sa libreng
ang kasalukuyang elemento.

142
00:07:52,140 --> 00:07:55,990
>> Kailangan naming siguruhin ang ginagawa namin ito dahil kami
Hindi maaaring lamang palayain ang kasalukuyang elemento

143
00:07:55,990 --> 00:07:59,260
at pagkatapos ay subukang i-access ang susunod na pointer
dahil sa sandaling napalaya namin ito ng

144
00:07:59,260 --> 00:08:00,870
nagiging di-wastong memorya.

145
00:08:00,870 --> 00:08:04,990
Kaya kailangan namin upang panatilihin sa paligid ng isang pointer upang
sa susunod na elemento, pagkatapos ay maaari naming palayain ang

146
00:08:04,990 --> 00:08:08,360
kasalukuyang elemento, at pagkatapos ay maaari naming i-update
aming kasalukuyang elemento upang tumuro sa

147
00:08:08,360 --> 00:08:09,590
sa susunod na elemento.

148
00:08:09,590 --> 00:08:12,770
>> Kami na magugustuhan loop habang mayroong mga elemento
sa naka-link na listahan.

149
00:08:12,770 --> 00:08:16,450
Gagawin namin ang na para sa lahat ng naka-link na mga listahan sa
ang hash talahanayan, at sa sandaling tapos na kami

150
00:08:16,450 --> 00:08:20,180
may iyon, ganap namin deskargado na
ang hash talahanayan, at tapos na kami.

151
00:08:20,180 --> 00:08:24,050
Kaya imposibleng para sa unloads sa kailanman
bumalik false, at kapag tapos na kami, namin

152
00:08:24,050 --> 00:08:25,320
bumalik lang totoo.

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