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
Olen Rob ja olgem hash
seda lahendust.

4
00:00:16,210 --> 00:00:20,070
Nii et siin me läheme rakendada
üldine hash tabel.

5
00:00:20,070 --> 00:00:24,090
Me näeme, et struct tipp meie hash
tabel läheb välja nägema selline.

6
00:00:24,090 --> 00:00:28,710
Nii et see saab olema char sõna
massiivi suurus pikkus pluss 1.

7
00:00:28,710 --> 00:00:32,259
Ärge unustage, 1 kuna maksimaalne
sõna sõnastikus on 45

8
00:00:32,259 --> 00:00:35,110
märki ja siis me läheme
pead ühe pildi hieroglüüf

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

10
00:00:37,070 --> 00:00:40,870
>> Ja siis meie hash tabelit iga
kopp läheb salvestada

11
00:00:40,870 --> 00:00:42,320
seotud nimekirja sõlmed.

12
00:00:42,320 --> 00:00:44,420
Me ei tee lineaarse katsetamine siin.

13
00:00:44,420 --> 00:00:48,430
Ja nii, et siduda järgmise
element ämbrisse, peame

14
00:00:48,430 --> 00:00:51,110
struct tipp * järgmine.

15
00:00:51,110 --> 00:00:53,090
Nii see on, mida sõlme välja näeb.

16
00:00:53,090 --> 00:00:56,180
Nüüd, siin on avaldus
meie hash tabel.

17
00:00:56,180 --> 00:01:01,910
See saab olema 16384 kopad, kuid
et number ei ole tegelikult küsimus.

18
00:01:01,910 --> 00:01:05,450
Ja lõpuks, me ei kavatse olla
globaalse muutuja hashtable_size, mis

19
00:01:05,450 --> 00:01:08,640
läheb alustad kui 0, ja see on
kavatse jälgida, kui palju sõnu

20
00:01:08,640 --> 00:01:10,080
olid meie sõnastik.

21
00:01:10,080 --> 00:01:10,760
Hea küll.

22
00:01:10,760 --> 00:01:13,190
>> Võtame pilk koormus.

23
00:01:13,190 --> 00:01:16,390
Nii teate, et koormus,
ta naaseb bool.

24
00:01:16,390 --> 00:01:20,530
Sa tagasi true, kui see oli edukalt
koormatud ja vale teisiti.

25
00:01:20,530 --> 00:01:23,990
Ja see võtab const char * tärniga
sõnastik, mis on sõnastik

26
00:01:23,990 --> 00:01:25,280
et tahame avada.

27
00:01:25,280 --> 00:01:27,170
Nii et esimene asi,
me teeme.

28
00:01:27,170 --> 00:01:30,420
Me läheme fopen sõnastik
lugemine, ja me ei kavatse olla

29
00:01:30,420 --> 00:01:34,700
veenduda, et see õnnestus, nii et kui
see tagastatakse NULL, siis me ei

30
00:01:34,700 --> 00:01:37,440
edukalt avada sõnastik
ja me peame tagasi false.

31
00:01:37,440 --> 00:01:41,580
>> Kuid kui eeldada, et ta seda tegi edukalt
avatud, siis tahame, et lugeda

32
00:01:41,580 --> 00:01:42,400
sõnastik.

33
00:01:42,400 --> 00:01:46,210
Nii et hoidke silmusega kuni leiame mõned
põhjus välja murda see

34
00:01:46,210 --> 00:01:47,570
loop, mida me näeme.

35
00:01:47,570 --> 00:01:51,780
Nii et hoidke silmusega ja nüüd me läheme
et malloc ühe sõlme.

36
00:01:51,780 --> 00:01:56,800
Ja loomulikult peame viga näha
jälle nii kui mallocing ei õnnestunud

37
00:01:56,800 --> 00:02:00,660
ja me tahame lossida ühtegi sõlme, et me
juhtus malloc enne, sulgege

38
00:02:00,660 --> 00:02:02,590
sõnastik ja tagastab false.

39
00:02:02,590 --> 00:02:07,440
>> Aga tähelepanuta asjaolu, eeldades, et me
õnnestunud, siis tahame kasutada fscanf

40
00:02:07,440 --> 00:02:12,400
loe sõnagi meie
sõnastik meie sõlme.

41
00:02:12,400 --> 00:02:17,310
Seega pidage meeles, et entry-> sõna on char
sõna puhverala suurus pikkus pluss

42
00:02:17,310 --> 00:02:20,300
üks, et me läheme
hoidke sõna sisse

43
00:02:20,300 --> 00:02:25,280
Nii fscanf läheb tagasi 1 niikaua
kui see oli võimalik edukalt lugeda

44
00:02:25,280 --> 00:02:26,750
sõna failist.

45
00:02:26,750 --> 00:02:31,030
>> Kui üks viga juhtub või jõuame
Faili lõpus, siis ei

46
00:02:31,030 --> 00:02:34,950
tagastab 1, kus juhul, kui see ei ole
tagasi 1, lõpuks ometi oleme murda

47
00:02:34,950 --> 00:02:37,280
sellest samas silmus.

48
00:02:37,280 --> 00:02:42,770
Nii me näeme, et kui meil on edukalt
loe sõna võtta

49
00:02:42,770 --> 00:02:48,270
entry-> sõna, siis me läheme hash
et sõna meie hash funktsiooni.

50
00:02:48,270 --> 00:02:49,580
Võtame pilk
hash funktsiooni.

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

52
00:02:52,430 --> 00:02:55,610
>> Nii et sa tõesti ei pea
sellest aru saama.

53
00:02:55,610 --> 00:02:59,460
Ja tegelikult, me lihtsalt tõmmatakse see
räsifunktsiooni internetist.

54
00:02:59,460 --> 00:03:04,010
Ainuke asi, sa pead tunnistama, on
et see võtab const char * sõna,

55
00:03:04,010 --> 00:03:08,960
nii see võtab stringi sisendiks ja
tagastamise allkirjastamata int toodanguna.

56
00:03:08,960 --> 00:03:12,360
Nii et kõik on hash funktsiooni, on see
võtab sisend, see annab sulle

57
00:03:12,360 --> 00:03:14,490
indeks hash tabel.

58
00:03:14,490 --> 00:03:18,530
Pange tähele, et me oleme modding poolt NUM_BUCKETS
nii räsi tagasi

59
00:03:18,530 --> 00:03:21,730
tegelikult on indeks hash tabel
ja ei indeks üle

60
00:03:21,730 --> 00:03:24,320
piire massiiv.

61
00:03:24,320 --> 00:03:27,855
>> Seega, arvestades, et hash funktsiooni, me
hash sõna, et me lugeda

62
00:03:27,855 --> 00:03:31,700
sõnaraamatust ja siis me läheme
kasutada, mis on sisestada

63
00:03:31,700 --> 00:03:33,750
sisenemise hash tabel.

64
00:03:33,750 --> 00:03:38,830
Nüüd Hashtable hash on praegune
seotud nimekirja hash tabelit ja

65
00:03:38,830 --> 00:03:41,410
On väga võimalik, et on lihtsalt NULL.

66
00:03:41,410 --> 00:03:45,640
Me tahame, et lisada oma sisenemise
alguses see seotud nimekirja, ja nii

67
00:03:45,640 --> 00:03:48,910
me lähed on meie praegune kanne
juhtida sellele, mida hash tabel praegu

68
00:03:48,910 --> 00:03:54,030
võrra ja siis me lähme salvestada
räsi tabeli hash

69
00:03:54,030 --> 00:03:55,350
Praegune kirje.

70
00:03:55,350 --> 00:03:59,320
>> Nii et need kaks rida edukalt sisestada
kande alguses

71
00:03:59,320 --> 00:04:02,270
seotud nimekirja sel indeks
aastal hash tabel.

72
00:04:02,270 --> 00:04:04,900
Kui me teinud, et me teame
et me leidsime teise sõna

73
00:04:04,900 --> 00:04:07,800
sõnastik ja me juurdekasvu uuesti.

74
00:04:07,800 --> 00:04:13,960
Nii me edasi teha kuni fscanf
lõpuks tagasi midagi mitte 1 juures

75
00:04:13,960 --> 00:04:18,560
mis punkt meeles pidada, et me peame
sissepääs tasuta, nii et siin on meil malloced

76
00:04:18,560 --> 00:04:21,329
sisenemise ja üritasime midagi lugeda
sõnaraamatust.

77
00:04:21,329 --> 00:04:24,110
Ja me ei ole suutnud lugeda
midagi sõnaraamatust, kus

78
00:04:24,110 --> 00:04:27,440
juhul me peame vabastama kanne, et me
tegelikult kunagi pannakse hash tabel

79
00:04:27,440 --> 00:04:29,110
ja lõpuks murda.

80
00:04:29,110 --> 00:04:32,750
>> Kui me välja murda, peame vaatama, noh,
me välja murda, sest seal

81
00:04:32,750 --> 00:04:35,840
oli viga lugemisel failist, või
me välja murda, sest me jõudsime

82
00:04:35,840 --> 00:04:37,120
Faili lõpus?

83
00:04:37,120 --> 00:04:40,150
Kui seal oli viga, siis me tahame
tagasi false sest koormus ei

84
00:04:40,150 --> 00:04:43,260
õnnestub, ja selles protsessis me tahame
lossimiseks kõik sõnad, et me loeme

85
00:04:43,260 --> 00:04:45,670
ja sulgege sõnastik faili.

86
00:04:45,670 --> 00:04:48,740
Eeldades, et me ei õnnestu, siis me lihtsalt
ikka on vaja sulgeda sõnastik

87
00:04:48,740 --> 00:04:51,970
fail ning lõpuks tagasi true alates
oleme edukalt laaditud

88
00:04:51,970 --> 00:04:53,040
sõnastik.

89
00:04:53,040 --> 00:04:54,420
Ja see on see koormus.

90
00:04:54,420 --> 00:04:59,020
>> Nüüd vaadake, arvestades koormatud hash tabel,
läheb välja nägema selline.

91
00:04:59,020 --> 00:05:02,690
Nii et vaadata, tagastatakse tõeväärtus, mis
läheb, et näidata, kas

92
00:05:02,690 --> 00:05:07,530
edasi-in char * sõna, kas
edasi-in string on meie sõnastik.

93
00:05:07,530 --> 00:05:10,530
Nii et kui see on sõnastikus olemas, kui see on
meie hash tabel, me tagasi

94
00:05:10,530 --> 00:05:13,380
tõsi, ja kui see ei ole,
me tagasi vale.

95
00:05:13,380 --> 00:05:17,770
Arvestades seda edasi-sõnaga, me oleme
läheb räsi sõna.

96
00:05:17,770 --> 00:05:22,020
>> Nüüd tähtsam tunnustada on
et koormus, me teadsime, et kõik

97
00:05:22,020 --> 00:05:25,820
sõnad, saab olema väiketähti
kuid siin me ei ole nii kindel.

98
00:05:25,820 --> 00:05:29,510
Kui me võtame pilk meie räsifunktsiooni,
meie räsifunktsiooni tegelikult

99
00:05:29,510 --> 00:05:32,700
on lowercasing iga märk
sõna.

100
00:05:32,700 --> 00:05:37,580
Seega sõltumata kapitaliseerimine
Ühesõnaga, meie räsifunktsiooni läheb

101
00:05:37,580 --> 00:05:42,270
tagasi sama indeksit mingil
kapitalisatsioon on see oleks

102
00:05:42,270 --> 00:05:45,280
tagastatud täielikult väiketähti
versioon sõna.

103
00:05:45,280 --> 00:05:45,950
Hea küll.

104
00:05:45,950 --> 00:05:47,410
>> Nii et meie kataloogi.

105
00:05:47,410 --> 00:05:49,790
See on hash tabel selle sõna.

106
00:05:49,790 --> 00:05:52,940
Nüüd on see loop läheb
et üle seotud nimekirja

107
00:05:52,940 --> 00:05:55,000
mis oli sel indeks.

108
00:05:55,000 --> 00:05:59,630
Nii märkate oleme algväärtustamisel kanne
osutada, et indeks.

109
00:05:59,630 --> 00:06:03,480
Me jätkata samas kirje ei
ei võrdu NULL, ja pidage meeles, et

110
00:06:03,480 --> 00:06:08,350
ajakohastamine pointer meie seotud nimekirja
kanne võrdub entry-> kõrval, nii on

111
00:06:08,350 --> 00:06:13,840
meie praegune lähtepunkt
Järgmine punkt on seotud nimekirja.

112
00:06:13,840 --> 00:06:14,400
Hea küll.

113
00:06:14,400 --> 00:06:19,150
>> Nii iga kande seotud nimekirja,
Me ei kavatse kasutada strcasecmp.

114
00:06:19,150 --> 00:06:23,780
See ei strcmp sest taas oleme
tahan teha asju, juhul hoolimatult.

115
00:06:23,780 --> 00:06:28,830
Nii et me kasutame strcasecmp võrrelda sõna
mis võeti vastu, et see funktsioon

116
00:06:28,830 --> 00:06:31,860
vastu sõna, mis
on see kanne.

117
00:06:31,860 --> 00:06:35,570
Kui ta naaseb 0, mis tähendab, et seal oli
mängu, mille puhul me tahame

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

119
00:06:36,630 --> 00:06:39,590
Oleme edukalt leitud
sõna meie hash tabel.

120
00:06:39,590 --> 00:06:43,040
>> Kui ei sobi, siis me oleme
läheb loop uuesti ja vaadata

121
00:06:43,040 --> 00:06:43,990
järgmine kanne.

122
00:06:43,990 --> 00:06:47,640
Ja me jätkame silmukoiminen samas
on sissekanded Selle seotud nimekirja.

123
00:06:47,640 --> 00:06:50,160
Mis juhtub, kui me murda
sellest loop?

124
00:06:50,160 --> 00:06:55,110
See tähendab, et me ei leia kirje,
sobitada see sõna, mille puhul

125
00:06:55,110 --> 00:07:00,220
me tagasi false näitab, et meie
hash tabel ei sisalda seda sõna.

126
00:07:00,220 --> 00:07:01,910
Ja see on seda kontrollida.

127
00:07:01,910 --> 00:07:02,540
Hea küll.

128
00:07:02,540 --> 00:07:04,790
>> Võtame pilk suurus.

129
00:07:04,790 --> 00:07:09,280
Nüüd suurus saab olema üsna lihtne
sest mäletan koormus, iga sõna

130
00:07:09,280 --> 00:07:12,880
leidsime me suurendatakse globaalset
muutuja hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Nii suuruse funktsioon on lihtsalt
läheb tagasi, et globaalne

132
00:07:15,830 --> 00:07:18,150
muutuja, ja see on kõik.

133
00:07:18,150 --> 00:07:22,300
>> Nüüd lõpuks on meil vaja maha laadida
sõnastik Kui kõik on tehtud.

134
00:07:22,300 --> 00:07:25,340
Niisiis, kuidas me saame seda teha?

135
00:07:25,340 --> 00:07:30,440
Siinsamas, me silmusega üle kõik
ämbrid meie hash tabel.

136
00:07:30,440 --> 00:07:33,240
Seega on NUM_BUCKETS ämbrid.

137
00:07:33,240 --> 00:07:37,490
Ja iga seotud nimekirja meie hash
tabel, me silmus üle

138
00:07:37,490 --> 00:07:41,070
kogu seotud nimekirja
vabastades iga element.

139
00:07:41,070 --> 00:07:46,070
Nüüd me peame olema ettevaatlikud, et siin me
on ajutine muutuja, mis on

140
00:07:46,070 --> 00:07:49,740
hoidmiseks kursor järgmisele
element, mis on seotud nimekirja.

141
00:07:49,740 --> 00:07:52,140
Ja siis me tasuta
praegune element.

142
00:07:52,140 --> 00:07:55,990
>> Me peame olema kindlad, et me teeme seda, sest me
ei saa lihtsalt vaba praegune element

143
00:07:55,990 --> 00:07:59,260
ja seejärel üritada pääsu järgmise pointer
sest kui me vabastas ta

144
00:07:59,260 --> 00:08:00,870
mälu muutub kehtetuks.

145
00:08:00,870 --> 00:08:04,990
Seega on meil vaja, et hoida umbes viit
Järgmine element, siis saab tasuta

146
00:08:04,990 --> 00:08:08,360
praegune element, ja siis saame uuendada
meie praegune element osutada

147
00:08:08,360 --> 00:08:09,590
Järgmine element.

148
00:08:09,590 --> 00:08:12,770
>> Me loop kui ilmnevad asjaolud,
Selles seotud nimekirja.

149
00:08:12,770 --> 00:08:16,450
Me teeme, et kõik, mis on seotud loendite
hash tabelis ja kui me oleme valmis

150
00:08:16,450 --> 00:08:20,180
koos, et me oleme täielikult maha laadida
hash tabelit ja me oleme valmis.

151
00:08:20,180 --> 00:08:24,050
Nii et see on võimatu, et selle tühjendab kunagi
tagasi false, ja kui me teinud oleme

152
00:08:24,050 --> 00:08:25,320
lihtsalt tagasi tõsi.

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