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

2
00:00:11,856 --> 00:00:13,050
>> ROB BOWDEN: Hæ.

3
00:00:13,050 --> 00:00:16,210
Ég er Rob, og kjötkássa skulum
Þessi lausn út.

4
00:00:16,210 --> 00:00:20,070
Svo hér erum við að fara að innleiða
almennt kjötkássa borð.

5
00:00:20,070 --> 00:00:24,090
Við sjáum að strúktúr hnút hash okkar
Taflan er að fara að líta svona út.

6
00:00:24,090 --> 00:00:28,710
Svo það er að fara að hafa bleikju orð
Fylki af stærðinni lengd auk 1.

7
00:00:28,710 --> 00:00:32,259
Ekki gleyma 1 síðan hámarki
orð í orðabókinni er 45

8
00:00:32,259 --> 00:00:35,110
stafir, og þá erum við að fara að
þarf einn auka staf fyrir hið

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

10
00:00:37,070 --> 00:00:40,870
>> Og þá kjötkássa borð okkar í hvert
fötu er að fara að geyma

11
00:00:40,870 --> 00:00:42,320
tengda listanum hnúta.

12
00:00:42,320 --> 00:00:44,420
Við erum ekki að línuleg leit hér.

13
00:00:44,420 --> 00:00:48,430
Og svo í röð til að tengja við næsta
þáttur í fötu, þurfum við að

14
00:00:48,430 --> 00:00:51,110
struct node * næst.

15
00:00:51,110 --> 00:00:53,090
Svo er það sem hnúturinn lítur út.

16
00:00:53,090 --> 00:00:56,180
Nú, hér er yfirlýsing
af kjötkássa borð okkar.

17
00:00:56,180 --> 00:01:01,910
Það er að fara að hafa 16.384 fötunum, en
þessi tala skiptir ekki máli.

18
00:01:01,910 --> 00:01:05,450
Og að lokum, við erum að fara að hafa
Global breyta hashtable_size, sem

19
00:01:05,450 --> 00:01:08,640
er að fara að byrja á eins og 0, og það er
fara að halda utan um hversu mörg orð

20
00:01:08,640 --> 00:01:10,080
voru í orðabók okkar.

21
00:01:10,080 --> 00:01:10,760
Allt í lagi.

22
00:01:10,760 --> 00:01:13,190
>> Þannig að við skulum taka a líta á hleðslu.

23
00:01:13,190 --> 00:01:16,390
Svo taka eftir því að hlaða,
það skilar bool.

24
00:01:16,390 --> 00:01:20,530
Þú skilar true ef það var með góðum árangri
hlaðinn og ósönn annars.

25
00:01:20,530 --> 00:01:23,990
Og það tekur const char * stjörnu
orðabók, sem er orðabók

26
00:01:23,990 --> 00:01:25,280
að við viljum að opna.

27
00:01:25,280 --> 00:01:27,170
Svo er það fyrsta sem
við erum að fara að gera.

28
00:01:27,170 --> 00:01:30,420
Við erum að fara að fopen orðabók fyrir
lestur, og við erum að fara að hafa

29
00:01:30,420 --> 00:01:34,700
að ganga úr skugga um að það tókst þannig að ef
það skilaði NULL, þá erum við did ekki

30
00:01:34,700 --> 00:01:37,440
tókst að opna orðabókina
og við þurfum að skila falskur.

31
00:01:37,440 --> 00:01:41,580
>> En miðað við að það gerði með góðum árangri
opinn, þá viljum við að lesa

32
00:01:41,580 --> 00:01:42,400
orðabók.

33
00:01:42,400 --> 00:01:46,210
Svo halda lykkja þar til við að finna nokkrar
ástæða til að brjótast út úr þessu

34
00:01:46,210 --> 00:01:47,570
lykkja sem við munum sjá.

35
00:01:47,570 --> 00:01:51,780
Svo halda lykkja, og nú erum við að fara
að malloc einum hnút.

36
00:01:51,780 --> 00:01:56,800
Og auðvitað þurfum við að villutékk
aftur svo ef mallocing ekki tekist

37
00:01:56,800 --> 00:02:00,660
og við viljum að afferma allir hnút sem við
gerðist að malloc áður, loka

38
00:02:00,660 --> 00:02:02,590
orðabók og aftur ósatt.

39
00:02:02,590 --> 00:02:07,440
>> En hunsa það, miðað við
tekist, þá viljum við nota fscanf

40
00:02:07,440 --> 00:02:12,400
til að lesa eitt orð frá okkar
orðabók í hnút okkar.

41
00:02:12,400 --> 00:02:17,310
Svo muna að innganga-> orð er bleikjan
orð biðminni stærð lengd auk

42
00:02:17,310 --> 00:02:20,300
sá sem við erum að fara að
geyma orð inn

43
00:02:20,300 --> 00:02:25,280
Svo fscanf er að fara að skila 1 svo lengi
eins og það var fær til giftusamlega lesa

44
00:02:25,280 --> 00:02:26,750
orð úr skrá.

45
00:02:26,750 --> 00:02:31,030
>> Ef annað hvort villa kemur eða við náum
í lok skrá, það vilja ekki

46
00:02:31,030 --> 00:02:34,950
skila 1 í þeim tilvikum ef það virkar ekki
skila 1, við erum loksins að fara að brjóta

47
00:02:34,950 --> 00:02:37,280
út úr þessu while lykkju.

48
00:02:37,280 --> 00:02:42,770
Svo við sjáum að þegar við höfum tekist
lesa orð í

49
00:02:42,770 --> 00:02:48,270
innganga-> orð, þá erum við að fara að kjötkássa
þessi orð með kjötkássa virka okkar.

50
00:02:48,270 --> 00:02:49,580
Láta 'taka a líta á
kjötkássa virka.

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

52
00:02:52,430 --> 00:02:55,610
>> Svo þú þarft ekki raunverulega þörf
að skilja þetta.

53
00:02:55,610 --> 00:02:59,460
Og í raun, dró við bara þetta
kjötkássa virka af internetinu.

54
00:02:59,460 --> 00:03:04,010
Það eina sem þú þarft að viðurkenna er
að þetta tekur const char * orð,

55
00:03:04,010 --> 00:03:08,960
svo það tekur streng sem inntak og
aftur óundirritaður INT sem framleiðsla.

56
00:03:08,960 --> 00:03:12,360
Svo er það allt a kjötkássa virka er, er það
tekur í inntak, gefur það þér

57
00:03:12,360 --> 00:03:14,490
Vísitala inn kjötkássa töflunni.

58
00:03:14,490 --> 00:03:18,530
Takið eftir að við erum modding við NUM_BUCKETS
svo kjötkássa gildi aftur

59
00:03:18,530 --> 00:03:21,730
reyndar er vísitölu í kjötkássa töflunni
og ekki vísitölu handan

60
00:03:21,730 --> 00:03:24,320
mörk í fylkinu.

61
00:03:24,320 --> 00:03:27,855
>> Svo í ljósi þess kjötkássa virka, við erum að fara
til kjötkássa orð sem við lesum

62
00:03:27,855 --> 00:03:31,700
úr orðabókinni og þá erum við að fara
að nota sem hefur að settu

63
00:03:31,700 --> 00:03:33,750
Gildistaka kjötkássa töflunni.

64
00:03:33,750 --> 00:03:38,830
Nú, Hashtable kjötkássa er núverandi
tengda listanum í kjötkássa töflunni, og

65
00:03:38,830 --> 00:03:41,410
það er mjög líklegt að er bara NÚLL.

66
00:03:41,410 --> 00:03:45,640
Við viljum setja færslu okkar á
upphafi þessa tengda listanum og svo

67
00:03:45,640 --> 00:03:48,910
við erum að fara að hafa núverandi færslu okkar
benda á það sem kjötkássa borð eins og er

68
00:03:48,910 --> 00:03:54,030
stig til og þá erum við að fara að geyma
í kjötkássa töflunni í hökkun

69
00:03:54,030 --> 00:03:55,350
núverandi færslu.

70
00:03:55,350 --> 00:03:59,320
>> Svo þessar tvær línur tókst setja
færslunnar í upphafi að

71
00:03:59,320 --> 00:04:02,270
tengda listanum á vísitölunni
í kjötkássa töflunni.

72
00:04:02,270 --> 00:04:04,900
Þegar við erum búin með það, við vitum
að við fundum annað orð í

73
00:04:04,900 --> 00:04:07,800
orðabók og við stighækkun aftur.

74
00:04:07,800 --> 00:04:13,960
Svo við höldum að gera það fyrr en fscanf
loksins skilar eitthvað sem ekki 1 á

75
00:04:13,960 --> 00:04:18,560
sem lið muna að við þurfum að
Aðgangur er ókeypis og svo upp hér, malloced við að

76
00:04:18,560 --> 00:04:21,329
færslu og við reyndum að lesa eitthvað
úr orðabókinni.

77
00:04:21,329 --> 00:04:24,110
Og við fengum ekki tekist að lesa
eitthvað úr orðabókinni sem

78
00:04:24,110 --> 00:04:27,440
ef við þurfum að losa færsluna sem við
aldrei raunverulega setja inn kjötkássa töflunni

79
00:04:27,440 --> 00:04:29,110
og að lokum brjóta.

80
00:04:29,110 --> 00:04:32,750
>> Þegar við brjótast út, þurfum við að sjá, vel,
höfum vér brjótast út vegna þess að það

81
00:04:32,750 --> 00:04:35,840
var að villa við lestur úr skránni, eða
höfum vér brjótast út vegna þess að við náð

82
00:04:35,840 --> 00:04:37,120
í lok skrárinnar?

83
00:04:37,120 --> 00:04:40,150
Ef það kom upp villa, þá viljum við
return false því hlaða gerði ekki

84
00:04:40,150 --> 00:04:43,260
ná árangri, og í því ferli, við viljum
afferma öll þau orð sem við lesum

85
00:04:43,260 --> 00:04:45,670
í og loka orðabók skrá.

86
00:04:45,670 --> 00:04:48,740
Miðað við hafi tekist, þá erum við bara
enn þurft að loka orðabók

87
00:04:48,740 --> 00:04:51,970
skrá, og að lokum aftur satt þar
við höfum tekist hlaðinn á

88
00:04:51,970 --> 00:04:53,040
orðabók.

89
00:04:53,040 --> 00:04:54,420
Og það er það að hlaða.

90
00:04:54,420 --> 00:04:59,020
>> Svo nú athugað, í ljósi hlaðinn kjötkássa borð,
er að fara að líta svona út.

91
00:04:59,020 --> 00:05:02,690
Svo stöðva það skilar bool, sem
er að fara að kynna hvort

92
00:05:02,690 --> 00:05:07,530
samþykkt í char * orði, hvort
framhjá-í band er í orðabók okkar.

93
00:05:07,530 --> 00:05:10,530
Þannig að ef það er í orðabókinni, ef það er
í kjötkássa töflunni okkar, munum við aftur

94
00:05:10,530 --> 00:05:13,380
satt, og ef það er ekki,
munum við aftur ósatt.

95
00:05:13,380 --> 00:05:17,770
Í ljósi þessa samþykkt í orð, við erum
fara að kjötkássa orðið.

96
00:05:17,770 --> 00:05:22,020
>> Nú, mikilvægur hlutur til að viðurkenna er
að í álagi, vissum við að allar

97
00:05:22,020 --> 00:05:25,820
orðin voru að fara að vera lágstöfum,
en hér erum við ekki svo viss.

98
00:05:25,820 --> 00:05:29,510
Ef við lítum á kjötkássa virka okkar,
kjötkássa virka okkar í raun

99
00:05:29,510 --> 00:05:32,700
er lowercasing hvern staf
orðsins.

100
00:05:32,700 --> 00:05:37,580
Svo óháð fjármögnun
orð, kjötkássa virka okkar er að fara að

101
00:05:37,580 --> 00:05:42,270
skila sömu vísitölu hvað sem
fjármögnun er eins og það myndi hafa

102
00:05:42,270 --> 00:05:45,280
aftur fyrir alveg lágstafir
útgáfa af orðinu.

103
00:05:45,280 --> 00:05:45,950
Allt í lagi.

104
00:05:45,950 --> 00:05:47,410
>> Svo er það vísitalan okkar.

105
00:05:47,410 --> 00:05:49,790
Það er kjötkássa borð fyrir þessu orði.

106
00:05:49,790 --> 00:05:52,940
Nú, þetta for lykkju er að fara
til yfir tengda listanum

107
00:05:52,940 --> 00:05:55,000
sem var á vísitölunni.

108
00:05:55,000 --> 00:05:59,630
Svo taka við erum Frumstilli færslu
til að benda á vísitölunni.

109
00:05:59,630 --> 00:06:03,480
Við ætlum að halda áfram á meðan innganga er
ekki jöfn NULL, og muna að

110
00:06:03,480 --> 00:06:08,350
uppfæra músina í tengda listanum okkar
færsla jafngildir innganga-> næsta, svo hafa

111
00:06:08,350 --> 00:06:13,840
núverandi innganga okkar benda til
næsta atriði í tengda listanum.

112
00:06:13,840 --> 00:06:14,400
Allt í lagi.

113
00:06:14,400 --> 00:06:19,150
>> Svo fyrir hverja færslu í tengda listanum,
við erum að fara að nota strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Það er ekki strcmp því aftur, við
vilja til að gera hlutina mál insensitively.

115
00:06:23,780 --> 00:06:28,830
Svo við notum strcasecmp að bera orð
sem var samþykkt við aðgerðina

116
00:06:28,830 --> 00:06:31,860
gegn orði, sem
er í þessari færslu.

117
00:06:31,860 --> 00:06:35,570
Ef það skilar 0, sem þýðir að það var
leik, en í því tilviki sem við viljum

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

119
00:06:36,630 --> 00:06:39,590
Við fundum tókst að
orð í kjötkássa töflunni okkar.

120
00:06:39,590 --> 00:06:43,040
>> Ef það var ekki passa, þá erum við
fara að lykkja aftur og líta á

121
00:06:43,040 --> 00:06:43,990
Next Entry.

122
00:06:43,990 --> 00:06:47,640
Og við munum halda áfram að lykkja á meðan það
eru færslur í þessum tengda listanum.

123
00:06:47,640 --> 00:06:50,160
Hvað gerist ef við brjóta
út af þessu fyrir lykkju?

124
00:06:50,160 --> 00:06:55,110
Það þýðir að við vildum ekki fundið færslu sem
samþykkt þetta orð, en í því tilviki

125
00:06:55,110 --> 00:07:00,220
við aftur ósatt að benda að okkar
kjötkássa borð ekki innihalda þetta orð.

126
00:07:00,220 --> 00:07:01,910
Og það er það að athuga.

127
00:07:01,910 --> 00:07:02,540
Allt í lagi.

128
00:07:02,540 --> 00:07:04,790
>> Þannig að við skulum taka a líta á stærð.

129
00:07:04,790 --> 00:07:09,280
Nú, stærð er að fara að vera frekar einfalt
síðan man í álag, fyrir hvert orð

130
00:07:09,280 --> 00:07:12,880
við fundum að við hækkaða alþjóðlegt
breytilegum hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Svo er stærð virka bara
fara að skila að alþjóðlegum

132
00:07:15,830 --> 00:07:18,150
breytu, og það er það.

133
00:07:18,150 --> 00:07:22,300
>> Nú loksins, þurfum við að afferma
orðabók þegar allt er gert.

134
00:07:22,300 --> 00:07:25,340
Svo hvernig eigum við að fara að gera það?

135
00:07:25,340 --> 00:07:30,440
Hérna erum við lykkja yfir alla
fötunum kjötkássa borð okkar.

136
00:07:30,440 --> 00:07:33,240
Þannig að það eru NUM_BUCKETS fötunum.

137
00:07:33,240 --> 00:07:37,490
Og fyrir hvert tengda listanum í hash okkar
borð, við erum að fara að lykkja yfir á

138
00:07:37,490 --> 00:07:41,070
heild á tengda listanum
frjáls hvert frumefni.

139
00:07:41,070 --> 00:07:46,070
Nú þurfum við að fara varlega, svo hér við
hafa tímabundna breytu sem er

140
00:07:46,070 --> 00:07:49,740
geyma músina til næsta
þáttur í tengda listanum.

141
00:07:49,740 --> 00:07:52,140
Og þá erum við að fara að losa
núverandi þáttur.

142
00:07:52,140 --> 00:07:55,990
>> Við þurfum að vera viss um að við gerum þetta því vér
getur ekki bara losa Opin ELEMENT

143
00:07:55,990 --> 00:07:59,260
og reyna svo að sjá næsta músina
síðan þegar við leysti það á

144
00:07:59,260 --> 00:08:00,870
minni verður öryrki.

145
00:08:00,870 --> 00:08:04,990
Þannig að við þurfum að halda í kring bendi á
næsta þátt, þá getum við frjálsari

146
00:08:04,990 --> 00:08:08,360
núverandi þáttur, og þá getum við uppfært
Núverandi þáttur okkar til að benda á

147
00:08:08,360 --> 00:08:09,590
næsta þátt.

148
00:08:09,590 --> 00:08:12,770
>> Við munum lykkja en það eru þættir
í þessu tengda listanum.

149
00:08:12,770 --> 00:08:16,450
Við munum gera það fyrir alla tengda listum í
kjötkássa borð, og þegar við erum búin

150
00:08:16,450 --> 00:08:20,180
við það, höfum við alveg skipað
kjötkássa borð, og við erum búin.

151
00:08:20,180 --> 00:08:24,050
Svo það er ómögulegt fyrir yfirgefur við alltaf
return false, og þegar við erum búin, við

152
00:08:24,050 --> 00:08:25,320
bara aftur satt.

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