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

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

3
00:00:13,050 --> 00:00:16,210
Aš Robas, ir tegul maišos
šis sprendimas iš.

4
00:00:16,210 --> 00:00:20,070
Taigi čia mes ketiname įgyvendinti
Apskritai maišos lentelė.

5
00:00:20,070 --> 00:00:24,090
Mes matome, kad struct mazgas mūsų maišos
lentelė atrodys tai.

6
00:00:24,090 --> 00:00:28,710
Taigi jis ketina turėti char žodį
masyvo dydis ilgis plius 1.

7
00:00:28,710 --> 00:00:32,259
Nepamirškite 1 nuo didžiausios
žodis žodyne yra 45

8
00:00:32,259 --> 00:00:35,110
simbolių, tada mes ketiname
reikia vieną papildomą požymį

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

10
00:00:37,070 --> 00:00:40,870
>> Ir tada mūsų maišos lentelė kiekvienoje
kibiras ketina saugoti

11
00:00:40,870 --> 00:00:42,320
susijęs sąrašas mazgų.

12
00:00:42,320 --> 00:00:44,420
Mes nedarome linijinė zondavimo čia.

13
00:00:44,420 --> 00:00:48,430
Ir todėl, kad rodo į kitą
elementas kibirą, mes turime

14
00:00:48,430 --> 00:00:51,110
struct mazgas * šalia.

15
00:00:51,110 --> 00:00:53,090
Štai ką mazgas atrodo.

16
00:00:53,090 --> 00:00:56,180
Dabar čia yra deklaracija
mūsų maišos lentelėje.

17
00:00:56,180 --> 00:01:01,910
Ji ketina turėti 16.384 kibirus, bet
šis skaičius tikrai ne klausimas.

18
00:01:01,910 --> 00:01:05,450
Ir pagaliau, mes ketiname turėti
pasaulinį kintamąjį hashtable_size, kuris

19
00:01:05,450 --> 00:01:08,640
ketina pradėti ne kaip 0, ir tai
ketina sekti kiek žodžių

20
00:01:08,640 --> 00:01:10,080
buvo mūsų žodyną.

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

22
00:01:10,760 --> 00:01:13,190
>> Taigi galime pažvelgti apkrovos išvaizdą.

23
00:01:13,190 --> 00:01:16,390
Taigi pastebėti, kad apkrovos,
jis grįžta bool.

24
00:01:16,390 --> 00:01:20,530
Jūs grąžina true, jei ji buvo sėkmingai
pakrauta ir false kitaip.

25
00:01:20,530 --> 00:01:23,990
Ir tai trunka const char * žvaigždę
žodyną, kuris yra žodynas

26
00:01:23,990 --> 00:01:25,280
kad mes norime atidaryti.

27
00:01:25,280 --> 00:01:27,170
Štai pirmas dalykas,
mes ketiname daryti.

28
00:01:27,170 --> 00:01:30,420
Mes ketiname fopen į žodyną
skaityti, o mes ketiname turėti

29
00:01:30,420 --> 00:01:34,700
įsitikinkite, kad ji pavyko todėl, jei
jis grįžo NULL, tada mes ne

30
00:01:34,700 --> 00:01:37,440
sėkmingai atidaryti žodyną
ir mes turime grįžti klaidinga.

31
00:01:37,440 --> 00:01:41,580
>> Tačiau darant prielaidą, kad jis sėkmingai padarė
atidaryti, tada mes norime skaityti

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

33
00:01:42,400 --> 00:01:46,210
Taigi neišmeskite apsisukimo kol mes radote
priežastis išeiti iš šio

34
00:01:46,210 --> 00:01:47,570
kilpa, kuri matysime.

35
00:01:47,570 --> 00:01:51,780
Taigi neišmeskite kilpų, ir dabar mes ketiname
į malloc vieną mazgą.

36
00:01:51,780 --> 00:01:56,800
Ir, žinoma, mes turime patikrinti klaidų
vėl todėl, jei mallocing nepavyko

37
00:01:56,800 --> 00:02:00,660
ir mes norime iškrauti bet kokį mazgą, kad mes
atsitiko malloc prieš, uždarykite

38
00:02:00,660 --> 00:02:02,590
žodynas ir return false.

39
00:02:02,590 --> 00:02:07,440
>> Tačiau ignoruojant, kad, darant prielaidą, mes
pavyko, tada mes norite naudoti fscanf

40
00:02:07,440 --> 00:02:12,400
skaityti vieną žodį iš mūsų
žodyną į mūsų mazgas.

41
00:02:12,400 --> 00:02:17,310
Taigi prisiminti, kad pradinio> žodis yra char
Žodis buferio dydis ilgis plius

42
00:02:17,310 --> 00:02:20,300
vienas, kad mes ketiname
laikyti žodį in

43
00:02:20,300 --> 00:02:25,280
Taigi fscanf ketina grįžti 1 tol, kol
kaip ji galėjo sėkmingai skaityti

44
00:02:25,280 --> 00:02:26,750
Žodis iš failo.

45
00:02:26,750 --> 00:02:31,030
>> Jei kuri nors klaida įvyksta, ar mes pasiekiame
failo pabaiga, jis nebus

46
00:02:31,030 --> 00:02:34,950
grįžti 1 tokiu atveju, jei jis nėra
grįžti 1, mes pagaliau suluš

47
00:02:34,950 --> 00:02:37,280
iš šio while cikle.

48
00:02:37,280 --> 00:02:42,770
Taigi matome, kad kai mes sėkmingai
skaityti žodis į

49
00:02:42,770 --> 00:02:48,270
pradinio> žodis, tada mes ketiname maišos
kad žodis naudojant mūsų maišos funkciją.

50
00:02:48,270 --> 00:02:49,580
Paimkime pažvelgti
maišos funkcija.

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

52
00:02:52,430 --> 00:02:55,610
>> Taigi jums nereikia tikrai reikia
tai suprasti.

53
00:02:55,610 --> 00:02:59,460
Ir iš tiesų, mes tiesiog iškedentas tai
maišos funkciją iš interneto.

54
00:02:59,460 --> 00:03:04,010
Vienintelis dalykas, kurį reikia pripažinti,
kad tai mano const char * žodį

55
00:03:04,010 --> 00:03:08,960
todėl imsis eilutę kaip įvesties ir
grąžinant unsigned int kaip produkcija.

56
00:03:08,960 --> 00:03:12,360
Taigi, kad viskas maišos funkcija, tai
trunka įvesties, ji suteikia jums

57
00:03:12,360 --> 00:03:14,490
rodyklė į maišos lentelėje.

58
00:03:14,490 --> 00:03:18,530
Atkreipkite dėmesį, kad mes modding pagal NUM_BUCKETS
taip maišos vertė sugrįžo

59
00:03:18,530 --> 00:03:21,730
iš tikrųjų yra į hash lentelę, indeksas
ir neindeksuoja už

60
00:03:21,730 --> 00:03:24,320
Ribas masyvo.

61
00:03:24,320 --> 00:03:27,855
>> Taigi, turint omenyje, kad maišos funkcija, mes ketiname
maišos žodį, kad mes skaityti

62
00:03:27,855 --> 00:03:31,700
iš žodyno ir tada mes ketiname
naudoti, kad yra įterpti

63
00:03:31,700 --> 00:03:33,750
įsigaliojimas maišos lentelėje.

64
00:03:33,750 --> 00:03:38,830
Dabar Hashtable maišos yra dabartinė
susijęs sąrašas maišos lentelės ir

65
00:03:38,830 --> 00:03:41,410
tai labai gali būti, kad yra tik NULL.

66
00:03:41,410 --> 00:03:45,640
Mes norime įterpti mūsų bendrovėms patekti į rinką
pradžioje šio susijęs sąrašo, ir taip

67
00:03:45,640 --> 00:03:48,910
mes ketiname turėti savo esamą įrašą
atkreipia dėmesį į tai, kas maišos lentelė šiuo metu

68
00:03:48,910 --> 00:03:54,030
punktų ir tada mes ketiname saugoti
maišos lentelės prie maišos

69
00:03:54,030 --> 00:03:55,350
dabartinis įrašas.

70
00:03:55,350 --> 00:03:59,320
>> Taigi šios dvi linijos sėkmingai įterpti
prie pradžios įrašas

71
00:03:59,320 --> 00:04:02,270
susijęs sąrašas tuo indeksą
maišos lentelėje.

72
00:04:02,270 --> 00:04:04,900
Kai baigsime su tuo, mes žinome,
kad mes rasti kitą žodį

73
00:04:04,900 --> 00:04:07,800
žodynas ir mes prieaugio dar kartą.

74
00:04:07,800 --> 00:04:13,960
Taigi, mes nuolat tai daryti, kad iki fscanf
pagaliau grįžta kažką ne 1 metu

75
00:04:13,960 --> 00:04:18,560
kuris taškas prisiminti, kad turime
įėjimas nemokamas, todėl čia mes malloced

76
00:04:18,560 --> 00:04:21,329
įrašas ir bandėme skaityti kažką
iš žodyno.

77
00:04:21,329 --> 00:04:24,110
Ir mes ne sėkmingai skaityti
kažkas iš žodyno, kuriame

78
00:04:24,110 --> 00:04:27,440
atveju turime išlaisvinti įrašą, kad mes
niekada iš tikrųjų įdėti į maišos lentelė

79
00:04:27,440 --> 00:04:29,110
ir galiausiai lūžta.

80
00:04:29,110 --> 00:04:32,750
>> Kai mes išeiti, mes turime pamatyti, gerai,
Ar mes išeiti, nes

81
00:04:32,750 --> 00:04:35,840
buvo klaida skaitant iš failo, arba
Ar mes išeiti, nes mes pasiekėme

82
00:04:35,840 --> 00:04:37,120
failo pabaiga?

83
00:04:37,120 --> 00:04:40,150
Jei ten buvo klaida, tada mes norime
return false, nes krovinys nebuvo

84
00:04:40,150 --> 00:04:43,260
sėkmės, ir į šį procesą, norime
iškrauti visus žodžius, kad mes skaityti

85
00:04:43,260 --> 00:04:45,670
ir uždaryti žodyno failą.

86
00:04:45,670 --> 00:04:48,740
Darant prielaidą, kad mes iš tikrųjų pavyko, tada mes tiesiog
vis dar reikia uždaryti žodyną

87
00:04:48,740 --> 00:04:51,970
failą, ir galiausiai grąžina true, nes
mes sėkmingai įkeltas

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

89
00:04:53,040 --> 00:04:54,420
Štai ir viskas kroviniu.

90
00:04:54,420 --> 00:04:59,020
>> Taigi, dabar patikrinti, nes pakrautas maišos lentelė,
ketina atrodyti taip.

91
00:04:59,020 --> 00:05:02,690
Taigi patikrinti, jis grįžta bool, kuris
ketina nurodyti, ar

92
00:05:02,690 --> 00:05:07,530
praėjo laikas char * žodžiu, ar
praėjo laikas eilutė yra mūsų žodyną.

93
00:05:07,530 --> 00:05:10,530
Taigi, jei tai yra žodyne, jei ji yra
mūsų maišos lentelės, grįšime

94
00:05:10,530 --> 00:05:13,380
tiesa, ir jei taip nėra,
grįšime klaidinga.

95
00:05:13,380 --> 00:05:17,770
Atsižvelgiant į tai praėjo laikas žodis, mes
ketina koduoti žodį.

96
00:05:17,770 --> 00:05:22,020
>> Dabar svarbiausias dalykas pripažinti,
kad apkrovos, mes žinojome, kad visi

97
00:05:22,020 --> 00:05:25,820
žodžiai buvo bus mažosios raidės,
bet čia mes ne tokie tikri.

98
00:05:25,820 --> 00:05:29,510
Jei mes atsižvelgti į mūsų maišos funkcija atrodo,
mūsų maišos funkcija faktiškai

99
00:05:29,510 --> 00:05:32,700
yra lowercasing kiekvieną simbolį
žodžio.

100
00:05:32,700 --> 00:05:37,580
Taigi, nepriklausomai nuo kapitalizacijos
žodis, mūsų maišos funkcija ketina

101
00:05:37,580 --> 00:05:42,270
grįžti tą patį indeksą kokia
kapitalizacija yra taip, kaip turėtų

102
00:05:42,270 --> 00:05:45,280
grąžinama visiškai mažosiomis raidėmis
portalo žodį.

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

104
00:05:45,950 --> 00:05:47,410
>> Štai mūsų indeksas.

105
00:05:47,410 --> 00:05:49,790
Tai maišos lentelė šiuo žodžiu.

106
00:05:49,790 --> 00:05:52,940
Dabar, tai for ciklas vyksta
iki daugiau kaip susietą sąrašą

107
00:05:52,940 --> 00:05:55,000
kad buvo tuo indeksu.

108
00:05:55,000 --> 00:05:59,630
Taigi pastebėsite mes Inicijuojama įrašą
atkreipti dėmesį į šio indekso.

109
00:05:59,630 --> 00:06:03,480
Mes ketiname tęsti, o įrašo nėra
nėra lygus NULL, ir prisiminti, kad

110
00:06:03,480 --> 00:06:08,350
atnaujinti žymiklį mūsų susietą sąrašą
įrašas Lygu įrašas-> kitas, todėl turi

111
00:06:08,350 --> 00:06:13,840
dabartinis mūsų įvažiavimo į
Kitas darbotvarkės punktas yra susijęs sąrašą.

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

113
00:06:14,400 --> 00:06:19,150
>> Taigi kiekvieno susieto sąrašo įrašą,
mes ketiname naudoti strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Tai ne strcmp nes vėlgi, mes
noriu daryti tai, ko bylą insensitively.

115
00:06:23,780 --> 00:06:28,830
Taigi mes naudojame strcasecmp palyginti žodį
kad buvo perduota ši funkcija

116
00:06:28,830 --> 00:06:31,860
prieš žodį,
yra šio įrašo.

117
00:06:31,860 --> 00:06:35,570
Jei ji grąžina 0, tai reiškia, kad buvo
rungtynės, tokiu atveju mes norime

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

119
00:06:36,630 --> 00:06:39,590
Mes sėkmingai surado
žodis mūsų maišos lentelėje.

120
00:06:39,590 --> 00:06:43,040
>> Jei ten buvo ne rungtynės, tada mes
ketina kilpos ir vėl pažvelgti

121
00:06:43,040 --> 00:06:43,990
Kitas įrašas.

122
00:06:43,990 --> 00:06:47,640
Ir mes ir toliau Looping nors
yra Įrašų šiame susijęs sąrašą.

123
00:06:47,640 --> 00:06:50,160
Kas atsitiks, jei mes pertrauka
iš čia už linijos?

124
00:06:50,160 --> 00:06:55,110
Tai reiškia, kad mes ne rasti įrašą,
atitiko šį žodį, tokiu atveju

125
00:06:55,110 --> 00:07:00,220
mes return false nurodyti, kad mūsų
maišos lentelė nebuvo šį žodį.

126
00:07:00,220 --> 00:07:01,910
Štai ir viskas registruotis.

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

128
00:07:02,540 --> 00:07:04,790
>> Taigi galime pažvelgti dydžio išvaizdą.

129
00:07:04,790 --> 00:07:09,280
Dabar, dydis bus gana paprasta
nes prisiminti, apkrova, už kiekvieną žodį

130
00:07:09,280 --> 00:07:12,880
mes pastebėjome padidinamas pasaulio
kintamasis hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Taigi dydis funkcija yra tik
ketina grįžti, kad visuotinis

132
00:07:15,830 --> 00:07:18,150
kintamasis, ir viskas.

133
00:07:18,150 --> 00:07:22,300
>> Dabar pagaliau turime iškrauti
žodynas kartą viskas daroma.

134
00:07:22,300 --> 00:07:25,340
Taigi, kaip mes ketiname daryti?

135
00:07:25,340 --> 00:07:30,440
Štai čia mes apsisukimo per visus
kibirai mūsų maišos lentelėje.

136
00:07:30,440 --> 00:07:33,240
Taigi yra NUM_BUCKETS kibirai.

137
00:07:33,240 --> 00:07:37,490
Ir kiekvieną susietą sąrašą mūsų maišos
stalas, mes ketiname kilpa per

138
00:07:37,490 --> 00:07:41,070
visuma susietą sąrašą
išlaisvina kiekvieną elementą.

139
00:07:41,070 --> 00:07:46,070
Dabar, mes turime būti atsargūs, kad čia mes
turėti laikiną kintamąjį, kad yra

140
00:07:46,070 --> 00:07:49,740
saugoti žymiklį į kitą
elementas susijęs sąrašą.

141
00:07:49,740 --> 00:07:52,140
Ir tada mes ketiname nemokamai
dabartinis elementas.

142
00:07:52,140 --> 00:07:55,990
>> Mes turime būti tikri, kad mes darome tai, nes mes
gali ne tik atlaisvinti einamųjų elemento

143
00:07:55,990 --> 00:07:59,260
ir tada bandykite ir atidarykite kitą žymeklį
nes kai mes išlaisvino jį

144
00:07:59,260 --> 00:08:00,870
atmintis tampa negaliojančiu.

145
00:08:00,870 --> 00:08:04,990
Taigi, mes turime išlaikyti aplink rodyklę į
Kitas elementas, tada mes galime nemokamai

146
00:08:04,990 --> 00:08:08,360
dabartinis elementas, ir tada mes galime atnaujinti
mūsų dabartinis elementas rodo

147
00:08:08,360 --> 00:08:09,590
kitas elementas.

148
00:08:09,590 --> 00:08:12,770
>> Mes kilpa nors yra elementai
Šiame susijęs sąrašą.

149
00:08:12,770 --> 00:08:16,450
Mes padarysime, kad visais su sąrašais
maišos lentelė, ir kai baigsime

150
00:08:16,450 --> 00:08:20,180
su tuo, mes visiškai iškraunamas
maišos lentelė, ir baigsime.

151
00:08:20,180 --> 00:08:24,050
Todėl neįmanoma iškrauna kada
return false, o kai baigsime mes

152
00:08:24,050 --> 00:08:25,320
tiesiog grąžina true.

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