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
Unë jam Rob, dhe të hash le të
kjo zgjidhje jashtë.

4
00:00:16,210 --> 00:00:20,070
Pra, këtu ne jemi duke shkuar për të zbatuar
një tabelë të përgjithshme hash.

5
00:00:20,070 --> 00:00:24,090
Ne e shohim se nyja struct të hash tonë
tabela do të duket si ky.

6
00:00:24,090 --> 00:00:28,710
Pra, kjo do të ketë një fjalë char
sërë gjatesi madhësisë plus 1.

7
00:00:28,710 --> 00:00:32,259
Mos harroni që nga 1 në maksimum
fjalë në fjalor është 45

8
00:00:32,259 --> 00:00:35,110
karaktere, dhe pastaj ne do të
nevojë për një karakter shtesë për

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

10
00:00:37,070 --> 00:00:40,870
>> Dhe pastaj tabelën tonë hash në secilin
kovë është duke shkuar për të ruajtur një

11
00:00:40,870 --> 00:00:42,320
listë e lidhur e nyjeve.

12
00:00:42,320 --> 00:00:44,420
Ne nuk jemi duke bërë lineare probing këtu.

13
00:00:44,420 --> 00:00:48,430
Dhe kështu që në mënyrë për të lidhur për të ardhshëm
element në kovë, ne kemi nevojë për një

14
00:00:48,430 --> 00:00:51,110
nyje struct * ardhshme.

15
00:00:51,110 --> 00:00:53,090
Pra, kjo është ajo që një nyje duket si.

16
00:00:53,090 --> 00:00:56,180
Tani, këtu është deklarata
i tryezën tonë hash.

17
00:00:56,180 --> 00:01:01,910
Ajo do të ketë 16.384 kova, por
se numri nuk ka rëndësi.

18
00:01:01,910 --> 00:01:05,450
Dhe në fund, ne do të kemi
hashtable_size globale ndryshueshme, e cila

19
00:01:05,450 --> 00:01:08,640
do të nisem si 0, dhe kjo është
do të mbajnë gjurmët e sa shumë fjalë

20
00:01:08,640 --> 00:01:10,080
ishin në fjalorin tonë.

21
00:01:10,080 --> 00:01:10,760
Dakord.

22
00:01:10,760 --> 00:01:13,190
>> Pra, le të marrin një vështrim në ngarkesë.

23
00:01:13,190 --> 00:01:16,390
Pra të vini re se ngarkesës,
ajo kthen një bool.

24
00:01:16,390 --> 00:01:20,530
Ju kthim i vërtetë në qoftë se ajo ishte sukses
ngarkuar dhe false ndryshe.

25
00:01:20,530 --> 00:01:23,990
Dhe ajo merr një const char * ylli
fjalor, i cili është dictionary

26
00:01:23,990 --> 00:01:25,280
që ne duam të hapur.

27
00:01:25,280 --> 00:01:27,170
Pra, kjo është gjëja e parë
ne jemi duke shkuar për të bërë.

28
00:01:27,170 --> 00:01:30,420
Ne jemi duke shkuar për fopen fjalorin për
lexim, dhe ne do të kemi

29
00:01:30,420 --> 00:01:34,700
për të siguruar që ajo arriti kështu që nëse
ajo u kthye NULL, atëherë ne nuk e bëri

30
00:01:34,700 --> 00:01:37,440
me sukses të hapur fjalorin
dhe ne duhet të kthimit të rreme.

31
00:01:37,440 --> 00:01:41,580
>> Por, duke supozuar se ajo e bëri me sukses
hapur, atëherë ne duam të lexuar

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

33
00:01:42,400 --> 00:01:46,210
Pra, të mbajtur looping deri sa të gjejmë disa
arsye për të thyer nga kjo

34
00:01:46,210 --> 00:01:47,570
lak të cilat ne do të shohim.

35
00:01:47,570 --> 00:01:51,780
Pra mbani looping, dhe tani ne jemi duke shkuar
për malloc një nyje të vetme.

36
00:01:51,780 --> 00:01:56,800
Dhe sigurisht, ne kemi nevojë për të gabuar kontroll
përsëri kështu që nëse mallocing nuk pati sukses

37
00:01:56,800 --> 00:02:00,660
dhe ne duam që të shkarkoj ndonjë nyje që ne
ndodhur me malloc para, të mbyllur

38
00:02:00,660 --> 00:02:02,590
fjalor dhe kthimit të rreme.

39
00:02:02,590 --> 00:02:07,440
>> Por duke injoruar se, duke supozuar ne
pati sukses, atëherë ne duam të përdorim fscanf

40
00:02:07,440 --> 00:02:12,400
për të lexuar një fjalë të vetme nga tonë
dictionary në nyje tonë.

41
00:02:12,400 --> 00:02:17,310
Pra, mos harroni se fjala e hyrjes-> është char
tampon fjalë e gjatësisë madhësisë plus

42
00:02:17,310 --> 00:02:20,300
një që ne do të
ruajtur fjalën in

43
00:02:20,300 --> 00:02:25,280
Pra fscanf do të kthehet 1 për aq kohë
si ajo ishte në gjendje për të lexuar me sukses një

44
00:02:25,280 --> 00:02:26,750
fjalë nga file.

45
00:02:26,750 --> 00:02:31,030
>> Nëse një nga një gabim ndodh apo të arrijmë
në fund të skedarit, ajo nuk do të

46
00:02:31,030 --> 00:02:34,950
kthehen 1 në të cilin rast në qoftë se ajo nuk ka
kthehen me 1, ne jemi më në fund do të thyer

47
00:02:34,950 --> 00:02:37,280
nga kjo loop ndërsa.

48
00:02:37,280 --> 00:02:42,770
Pra, ne shohim se një herë ne kemi sukses
lexoni një fjalë në

49
00:02:42,770 --> 00:02:48,270
hyrje-> fjalë, atëherë ne do të hash
se fjala përdorur funksionin tonë të hash.

50
00:02:48,270 --> 00:02:49,580
Le të bëjmë një vështrim në
funksion hash.

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

52
00:02:52,430 --> 00:02:55,610
>> Pra, ju nuk duhet të vërtetë
për të kuptuar këtë.

53
00:02:55,610 --> 00:02:59,460
Dhe në të vërtetë, ne vetëm u tërhoq këtë
hash funksion nga interneti.

54
00:02:59,460 --> 00:03:04,010
E vetmja gjë që ju duhet për të njohur është
se kjo merr një const char * fjalën,

55
00:03:04,010 --> 00:03:08,960
kështu që është duke marrë një varg si input dhe
kthyer një int unsigned si prodhim.

56
00:03:08,960 --> 00:03:12,360
Pra, kjo është e gjitha një funksion hash është, është ajo
merr në një input, kjo ju jep ekber

57
00:03:12,360 --> 00:03:14,490
Indeksi në tabelën hash.

58
00:03:14,490 --> 00:03:18,530
Vini re që ne jemi modding nga NUM_BUCKETS
kështu që vlera e hash kthyer

59
00:03:18,530 --> 00:03:21,730
në të vërtetë është një indeks në tabelë hash
dhe nuk indeksi përtej

60
00:03:21,730 --> 00:03:24,320
caqeve të array.

61
00:03:24,320 --> 00:03:27,855
>> Pra, duke pasur parasysh se funksion hash, ne jemi duke shkuar
te bej hash fjalën që ne të lexuar

62
00:03:27,855 --> 00:03:31,700
nga fjalori dhe pastaj ne do
për të përdorur që ka për të futur

63
00:03:31,700 --> 00:03:33,750
hyrja në tabelën hash.

64
00:03:33,750 --> 00:03:38,830
Tani, hash hashtable është aktual
lista e lidhur në tabelë hash, dhe

65
00:03:38,830 --> 00:03:41,410
kjo është shumë e mundur që është vetëm NULL.

66
00:03:41,410 --> 00:03:45,640
Ne duam të futur hyrjen tonë në
fillimi i këtij listën e lidhur, dhe kështu

67
00:03:45,640 --> 00:03:48,910
ne do të ketë hyrjen tonë të tanishëm
tregojnë për çfarë tryezë hash aktualisht

68
00:03:48,910 --> 00:03:54,030
pikë për të dhe pastaj ne jemi duke shkuar për të ruajtur
në tabelën hash hash në

69
00:03:54,030 --> 00:03:55,350
hyrja aktuale.

70
00:03:55,350 --> 00:03:59,320
>> Pra, këto dy linja sukses futur
hyrja në fillim të

71
00:03:59,320 --> 00:04:02,270
lista e lidhur në atë indeks
në tabelën hash.

72
00:04:02,270 --> 00:04:04,900
Pasi ne jemi duke bërë me këtë, ne e dimë
se kemi gjetur një tjetër fjalë në

73
00:04:04,900 --> 00:04:07,800
fjalor dhe ne rritje përsëri.

74
00:04:07,800 --> 00:04:13,960
Pra, ne vazhdojmë të bëjmë që deri fscanf
më në fund kthehet diçka jo 1 në

75
00:04:13,960 --> 00:04:18,560
cilën pikë mos harroni se ne kemi nevojë për të
hyrje të lirë, kështu që deri këtu, ne malloced një

76
00:04:18,560 --> 00:04:21,329
Hyrja dhe jemi munduar për të lexuar diçka
nga fjalori.

77
00:04:21,329 --> 00:04:24,110
Dhe ne nuk e ka lexuar me sukses
diçka nga fjalori në të cilën

78
00:04:24,110 --> 00:04:27,440
rast ne kemi nevojë për të liruar hyrjen që ne
kurrë nuk e vënë në të vërtetë në tabelën hash

79
00:04:27,440 --> 00:04:29,110
dhe më në fund pushim.

80
00:04:29,110 --> 00:04:32,750
>> Pasi ne shpërthen, ne duhet të shohim, mirë,
nuk e kemi shpërthen për shkak se ka

81
00:04:32,750 --> 00:04:35,840
u lexuar një gabim nga skedari, ose
nuk e kemi shpërthen, sepse kemi arritur

82
00:04:35,840 --> 00:04:37,120
fundi i dosjes?

83
00:04:37,120 --> 00:04:40,150
Nëse ka pasur një gabim, atëherë ne duam të
kthimit të rreme për shkak të ngarkesës nuk e bëri

84
00:04:40,150 --> 00:04:43,260
të ketë sukses, dhe në proces, ne duam të
shkarkoj të gjitha fjalët që kemi lexuar

85
00:04:43,260 --> 00:04:45,670
në dhe afër fjalor file.

86
00:04:45,670 --> 00:04:48,740
Duke supozuar që pati sukses, atëherë ne vetëm
ende nevojë për të mbyllur fjalorin

87
00:04:48,740 --> 00:04:51,970
paraqesë, dhe më në fund kthehet e vërtetë që nga
ne kemi ngarkuar me sukses

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

89
00:04:53,040 --> 00:04:54,420
Dhe kjo është ajo për të ngarkesës.

90
00:04:54,420 --> 00:04:59,020
>> Deri tani të kontrolluar, duke pasur parasysh një tavolinë ngarkuar hash,
do të duket si ky.

91
00:04:59,020 --> 00:05:02,690
Pra shikoni, ajo kthen një bool, e cila
do të tregojë nëse

92
00:05:02,690 --> 00:05:07,530
kaluar-në char * fjalë, nëse
kaluar-në string është në fjalorin tonë.

93
00:05:07,530 --> 00:05:10,530
Pra, në qoftë se ajo është në fjalor, nëse është
në tabelën hash tonë, ne do të kthehen

94
00:05:10,530 --> 00:05:13,380
e vërtetë, dhe nëse ajo nuk është,
ne do të kthimit të rreme.

95
00:05:13,380 --> 00:05:17,770
Duke pasur parasysh këtë fjalë kaloi-në, ne jemi
do të hash fjalën.

96
00:05:17,770 --> 00:05:22,020
>> Tani, një gjë e rëndësishme për të njohur është
se në ngarkesës, ne e dinim se të gjithë

97
00:05:22,020 --> 00:05:25,820
fjalët u do të jetë rasti më i ulët,
por këtu, ne nuk jemi aq të sigurt.

98
00:05:25,820 --> 00:05:29,510
Nëse do të bëjmë një vështrim në funksion tonë të hash,
funksion ynë hash në të vërtetë

99
00:05:29,510 --> 00:05:32,700
është lowercasing çdo karakter
të fjalës.

100
00:05:32,700 --> 00:05:37,580
Pra, pavarësisht nga kapitalizimin e
fjalë, funksioni ynë hash do të

101
00:05:37,580 --> 00:05:42,270
kthejë të njëjtën indeksin për çfarëdo
kapitalizimi është ashtu siç do të kishte

102
00:05:42,270 --> 00:05:45,280
kthyer për një krejtësisht të vogla
Versioni i fjalës.

103
00:05:45,280 --> 00:05:45,950
Dakord.

104
00:05:45,950 --> 00:05:47,410
>> Pra, kjo është indeksi tonë.

105
00:05:47,410 --> 00:05:49,790
Kjo është tabela hash për këtë fjalë.

106
00:05:49,790 --> 00:05:52,940
Tani, kjo për lak është duke shkuar
në mbi listën e lidhur

107
00:05:52,940 --> 00:05:55,000
që ishte në atë indeks.

108
00:05:55,000 --> 00:05:59,630
Pra, vini re, ne jemi të fillimit të hyrjes
për pikë në këtë indeks.

109
00:05:59,630 --> 00:06:03,480
Ne jemi do të vazhdojë, ndërsa hyrja e bën
nuk NULL të barabartë, dhe mos harroni se

110
00:06:03,480 --> 00:06:08,350
përditësimin treguesin në listën tonë lidhur
Hyrja është e barabartë me hyrje-> ardhshme, kështu që kanë

111
00:06:08,350 --> 00:06:13,840
pika jonë e tanishme e hyrjes në
Pika tjetër në listën e lidhur.

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

113
00:06:14,400 --> 00:06:19,150
>> Kështu që për çdo hyrje në listën e lidhur,
ne jemi duke shkuar për të përdorur strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Kjo nuk është strcmp sepse edhe një herë, ne
dua të bëj gjëra rast insensitively.

115
00:06:23,780 --> 00:06:28,830
Pra, ne i përdorim strcasecmp për të krahasuar fjalën
që u miratua në këtë funksion

116
00:06:28,830 --> 00:06:31,860
kundër fjalës që
është në këtë term.

117
00:06:31,860 --> 00:06:35,570
Nëse ai kthehet në 0, kjo do të thotë ka pasur
një ndeshje, në të cilin rast ne duam të

118
00:06:35,570 --> 00:06:36,630
kthim i vërtetë.

119
00:06:36,630 --> 00:06:39,590
Ne me sukses gjetur
Fjala në tryezën tonë hash.

120
00:06:39,590 --> 00:06:43,040
>> Nëse ka nuk ishte një ndeshje, atëherë ne jemi
do të lak përsëri dhe të kërkoni në

121
00:06:43,040 --> 00:06:43,990
hyrje tjetër.

122
00:06:43,990 --> 00:06:47,640
Dhe ne do të vazhdojmë looping ndërsa ka
janë të hyra në këtë listën e lidhur.

123
00:06:47,640 --> 00:06:50,160
Çfarë ndodh nëse ne pushim
nga kjo për lak?

124
00:06:50,160 --> 00:06:55,110
Kjo do të thotë ne nuk kemi gjetur një hyrje që
përputhet këtë fjalë, në të cilin rast

125
00:06:55,110 --> 00:07:00,220
ne kthimit të rreme për të treguar se tonë
tabelë hash nuk e përmbajnë këtë fjalë.

126
00:07:00,220 --> 00:07:01,910
Dhe kjo është ajo për kontroll.

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

128
00:07:02,540 --> 00:07:04,790
>> Pra, le të marrin një vështrim në madhësi.

129
00:07:04,790 --> 00:07:09,280
Tani, madhësia do të jetë shumë e thjeshtë
që të mbani mend në ngarkesë, për çdo fjalë

130
00:07:09,280 --> 00:07:12,880
kemi gjetur ne incremented një globale
hashtable_size ndryshueshme.

131
00:07:12,880 --> 00:07:15,830
Pra, funksioni madhësia është vetëm
do të kthehen që globale

132
00:07:15,830 --> 00:07:18,150
variabël, dhe kjo është ajo.

133
00:07:18,150 --> 00:07:22,300
>> Tani së fundi, ne kemi nevojë për të shkarkoj
fjalor herë është bërë çdo gjë.

134
00:07:22,300 --> 00:07:25,340
Pra, si do të shkojmë për të bërë këtë?

135
00:07:25,340 --> 00:07:30,440
Këtu, ne jemi looping mbi të gjitha
kova e tryezën tonë hash.

136
00:07:30,440 --> 00:07:33,240
Pra, ka NUM_BUCKETS kova.

137
00:07:33,240 --> 00:07:37,490
Dhe për çdo listën e lidhur të hash tonë
tavolinë, ne do të lak mbi

138
00:07:37,490 --> 00:07:41,070
tërësia e listës lidhur
liruar çdo element.

139
00:07:41,070 --> 00:07:46,070
Tani, ne duhet të jemi të kujdesshëm, kështu që këtu ne
kanë një ndryshore të përkohshme që është

140
00:07:46,070 --> 00:07:49,740
ruajtjen kursorin për të ardhshëm
element në lista lidhur.

141
00:07:49,740 --> 00:07:52,140
Dhe atëherë ne jemi duke shkuar për të lirë
element tanishme.

142
00:07:52,140 --> 00:07:55,990
>> Ne duhet të jetë i sigurt që ne e bëjmë këtë që nga viti ne
nuk mund vetëm të lirë elementin e tanishëm të

143
00:07:55,990 --> 00:07:59,260
dhe pastaj të përpiqet për të hyrë në treguesin e ardhshme
që nga një herë ne liruar atë

144
00:07:59,260 --> 00:08:00,870
kujtesës bëhet e pavlefshme.

145
00:08:00,870 --> 00:08:04,990
Pra, ne kemi nevojë për të mbajtur rreth një tregues për
element tjetër, atëherë ne mund të lirë

146
00:08:04,990 --> 00:08:08,360
element aktuale, dhe pastaj ne mund të rinovuar
element tonë aktuale për pikë për të

147
00:08:08,360 --> 00:08:09,590
element tjetër.

148
00:08:09,590 --> 00:08:12,770
>> Ne do të loop ndërsa ka elemente
në këtë listë e lidhur.

149
00:08:12,770 --> 00:08:16,450
Ne do të bëjmë që për të gjitha listat e lidhura në
tabela hash, dhe një herë ne jemi duke bërë

150
00:08:16,450 --> 00:08:20,180
me se, ne kemi shkarkuar plotësisht
tabela hash, dhe ne jemi duke bërë.

151
00:08:20,180 --> 00:08:24,050
Kështu që është e pamundur për shkarkon të gjithnjë
kthimit të rreme, dhe kur ne jemi bërë, ne

152
00:08:24,050 --> 00:08:25,320
vetëm kthim i vërtetë.

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