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

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

3
00:00:13,050 --> 00:00:16,210
Som Rob, a poďme hash
Tento roztok sa.

4
00:00:16,210 --> 00:00:20,070
Takže tu budeme realizovať
Všeobecne hash tabuľky.

5
00:00:20,070 --> 00:00:24,090
Vidíme, že struct uzol našej hash
tabuľka bude vyzerať takto.

6
00:00:24,090 --> 00:00:28,710
Takže to bude mať char slovo
pole o dĺžke size plus 1.

7
00:00:28,710 --> 00:00:32,259
Nezabudnite 1 od maxima
slovo v slovníku je 45

8
00:00:32,259 --> 00:00:35,110
znaky, a potom budeme
Potrebujeme jeden ďalší znak pre

9
00:00:35,110 --> 00:00:37,070
spätné lomítko 0.

10
00:00:37,070 --> 00:00:40,870
>> A potom naše hash tabuľka v každom
vedro sa bude ukladať

11
00:00:40,870 --> 00:00:42,320
spájať zoznam uzlov.

12
00:00:42,320 --> 00:00:44,420
Nerobíme lineárne snímacie tu.

13
00:00:44,420 --> 00:00:48,430
A tak, aby odkazy na ďalšie
prvok v vedre, musíme

14
00:00:48,430 --> 00:00:51,110
struct uzol * ďalšie.

15
00:00:51,110 --> 00:00:53,090
Takže to je to, čo uzol vyzerá.

16
00:00:53,090 --> 00:00:56,180
Teraz je tu vyhlásenie
z našej tabuľky hash.

17
00:00:56,180 --> 00:01:01,910
Bude to mať 16.384 vedierka, ale
že počet nezáleží.

18
00:01:01,910 --> 00:01:05,450
A konečne budeme mať
globálna premenná hashtable_size, ktoré

19
00:01:05,450 --> 00:01:08,640
sa chystá odštartovať ako 0, a to
bude sledovať, koľko slov

20
00:01:08,640 --> 00:01:10,080
boli v našom slovníku.

21
00:01:10,080 --> 00:01:10,760
Dobrá.

22
00:01:10,760 --> 00:01:13,190
>> Takže poďme sa pozrieť na zaťaženie.

23
00:01:13,190 --> 00:01:16,390
Takže všimnúť, že zaťaženie,
vracia bool.

24
00:01:16,390 --> 00:01:20,530
Môžete sa vrátiť true, ak bolo úspešné
naložený a v opačnom prípade false.

25
00:01:20,530 --> 00:01:23,990
A to trvá const char * hviezdu
slovník, ktorý je slovník

26
00:01:23,990 --> 00:01:25,280
ktorý chceme otvoriť.

27
00:01:25,280 --> 00:01:27,170
Takže to je prvá vec,
budeme robiť.

28
00:01:27,170 --> 00:01:30,420
Chystáme sa fopen slovník
čítanie, a budeme mať

29
00:01:30,420 --> 00:01:34,700
aby sa ubezpečil, že sa podarilo, aby v prípade,
to sa vrátilo NULL, potom nie

30
00:01:34,700 --> 00:01:37,440
úspešne otvoriť slovník
a my sa musíme vrátiť false.

31
00:01:37,440 --> 00:01:41,580
>> Ale za predpokladu, že to úspešne urobil
otvorené, potom chceme prečítať

32
00:01:41,580 --> 00:01:42,400
slovník.

33
00:01:42,400 --> 00:01:46,210
Takže majte opakovanie, kým nenájdeme nejaký
dôvod, aby sa vymanili z tejto

34
00:01:46,210 --> 00:01:47,570
slučky, ktoré uvidíme.

35
00:01:47,570 --> 00:01:51,780
Takže majte opakovanie, a teraz ideme
malloc jeden uzol.

36
00:01:51,780 --> 00:01:56,800
A samozrejme, musíme k chybe kontroly
znovu, takže ak mallocing neuspel

37
00:01:56,800 --> 00:02:00,660
a chceme vyložiť ľubovoľný uzol, ktorý my
stalo malloc pred zavrite

38
00:02:00,660 --> 00:02:02,590
slovník a vráti false.

39
00:02:02,590 --> 00:02:07,440
>> Ale ignorovať, že za predpokladu, že sa
podarilo, potom chceme použiť fscanf

40
00:02:07,440 --> 00:02:12,400
prečítať jediné slovo z našej
slovník do nášho uzla.

41
00:02:12,400 --> 00:02:17,310
Takže pamätajte, že vstupné-> slovo je char
Slovo vyrovnávacej dĺžky plus veľkosti

42
00:02:17,310 --> 00:02:20,300
jedno, že budeme
uložiť slovo dovnútra

43
00:02:20,300 --> 00:02:25,280
Takže fscanf sa chystá na návrat 1 tak dlho,
ako to bolo možné úspešne čítať

44
00:02:25,280 --> 00:02:26,750
slovo zo súboru.

45
00:02:26,750 --> 00:02:31,030
>> Pokiaľ to buď chyba sa stane, alebo sa dostaneme
koniec súboru, nebude

46
00:02:31,030 --> 00:02:34,950
vráti 1 v tom prípade, ak to nie je
vráti 1, sme sa konečne chystá zlomiť

47
00:02:34,950 --> 00:02:37,280
z tohto cyklu while.

48
00:02:37,280 --> 00:02:42,770
Takže vidíme, že raz sa nám podarilo mať
čítať slovo do

49
00:02:42,770 --> 00:02:48,270
entry-> slovo, potom ideme do hash
že slovo pomocou nášho hash funkcie.

50
00:02:48,270 --> 00:02:49,580
Poďme sa pozrieť na
funkcia hash.

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

52
00:02:52,430 --> 00:02:55,610
>> Takže nemáte naozaj potrebujete
to pochopiť.

53
00:02:55,610 --> 00:02:59,460
A vlastne, proste vytiahol to
hash funkcie z internetu.

54
00:02:59,460 --> 00:03:04,010
Jediná vec, ktorú je potrebné si uvedomiť, je
že to trvá const char * slovo,

55
00:03:04,010 --> 00:03:08,960
tak to trvá reťazec ako vstup a
vrátením unsigned int ako výstup.

56
00:03:08,960 --> 00:03:12,360
Tak to je všetko, funkcia hash je, je to
berie na vstupe, to vám dáva

57
00:03:12,360 --> 00:03:14,490
index do tabuľky hash.

58
00:03:14,490 --> 00:03:18,530
Všimnite si, že sme modding by NUM_BUCKETS
takže vrátená hodnota hash

59
00:03:18,530 --> 00:03:21,730
v skutočnosti je index do tabuľky hash
a nie je index za

60
00:03:21,730 --> 00:03:24,320
medze poľa.

61
00:03:24,320 --> 00:03:27,855
>> Takže za predpokladu, že ich haš funkcie, ideme
hash slovo, ktoré čítame

62
00:03:27,855 --> 00:03:31,700
zo slovníka, a potom ideme
na použitie, ktorý má vložiť

63
00:03:31,700 --> 00:03:33,750
vstup do hash tabuľky.

64
00:03:33,750 --> 00:03:38,830
Teraz, Hashtable hash je aktuálne
spájať zoznam v tabuľke hash, a

65
00:03:38,830 --> 00:03:41,410
je veľmi pravdepodobné, že je len NULL.

66
00:03:41,410 --> 00:03:45,640
Chceme vložiť náš vstup na
začiatku tohto spojovaceho zoznamu, a tak

67
00:03:45,640 --> 00:03:48,910
budeme mať našu aktuálnu položku
poukazujú na to, čo hash tabuľky v súčasnej dobe

68
00:03:48,910 --> 00:03:54,030
body, a potom budeme ukladať
v hash tabuľke na hash

69
00:03:54,030 --> 00:03:55,350
aktuálny záznam.

70
00:03:55,350 --> 00:03:59,320
>> Takže tieto dva riadky úspešne vložiť
Vstup na začiatku

71
00:03:59,320 --> 00:04:02,270
spájať zoznam v tomto indexe
v tabuľke hash.

72
00:04:02,270 --> 00:04:04,900
Akonáhle sme hotoví s tým, vieme,
že sme našli ďalšie slovo

73
00:04:04,900 --> 00:04:07,800
slovník a opäť zvyšovať.

74
00:04:07,800 --> 00:04:13,960
Tak sme to robiť, kým fscanf
konečne vráti niečo non 1 na

75
00:04:13,960 --> 00:04:18,560
ktorom mieste si uvedomiť, že musíme
vstup zadarmo, takže tu sme malloced

76
00:04:18,560 --> 00:04:21,329
vstup a snažili sme sa, aby si niečo prečítať
zo slovníka.

77
00:04:21,329 --> 00:04:24,110
A my sme nemali úspešne čítať
niečo zo slovníka, v ktorom

78
00:04:24,110 --> 00:04:27,440
prípade musíme uvoľniť záznam, ktorý my
nikdy dať do hash tabuľky

79
00:04:27,440 --> 00:04:29,110
a konečne zlomiť.

80
00:04:29,110 --> 00:04:32,750
>> Potom, čo sme sa vymaniť, musíme vidieť, dobre,
sme sa zlomiť, pretože tam

81
00:04:32,750 --> 00:04:35,840
bola chyba pri čítaní zo súboru, alebo
sme sa zlomiť, pretože sme dosiahli

82
00:04:35,840 --> 00:04:37,120
koniec súboru?

83
00:04:37,120 --> 00:04:40,150
Ak došlo k chybe, potom chceme, aby
return false, pretože zaťaženie nie

84
00:04:40,150 --> 00:04:43,260
uspieť, a v tomto procese, chceme
vyložiť všetky slová, ktoré čítame

85
00:04:43,260 --> 00:04:45,670
v a zatvorte súbor slovníka.

86
00:04:45,670 --> 00:04:48,740
Za predpokladu, že sme sa to podarí, potom sme len
Stále je potrebné zavrieť slovník

87
00:04:48,740 --> 00:04:51,970
súbor, a nakoniec sa vrátite pravda, pretože
sme úspešne vložený

88
00:04:51,970 --> 00:04:53,040
slovník.

89
00:04:53,040 --> 00:04:54,420
A to je pre zaťaženie.

90
00:04:54,420 --> 00:04:59,020
>> Takže teraz zistiť, vzhľadom k tomu naložené hash tabuľky,
bude vyzerať takto.

91
00:04:59,020 --> 00:05:02,690
Tak sa pozrite, vracia bool, ktorý
sa chystá uviesť, či

92
00:05:02,690 --> 00:05:07,530
odovzdaný v char * slovo, či
uplynulo-in string je v našom slovníku.

93
00:05:07,530 --> 00:05:10,530
Takže, ak je v slovníku, je-li
v našej hašovacej tabuľke, vrátime sa

94
00:05:10,530 --> 00:05:13,380
pravda, a ak to nie je,
vrátime false.

95
00:05:13,380 --> 00:05:17,770
Vzhľadom k tomu, to prešiel-in slovo, my sme
bude hash slovo.

96
00:05:17,770 --> 00:05:22,020
>> Teraz dôležité si uvedomiť, je
že v záťaži, vedeli sme, že všetky

97
00:05:22,020 --> 00:05:25,820
slová sa bude malé písmená,
ale tu, my nie sme tak istí.

98
00:05:25,820 --> 00:05:29,510
Ak sa pozrieme na náš hash funkcie,
naše hash funkcia vlastne

99
00:05:29,510 --> 00:05:32,700
je lowercasing každý znak
slová.

100
00:05:32,700 --> 00:05:37,580
Takže bez ohľadu na kapitalizácie
Slovo, náš hash funkcie sa chystá

101
00:05:37,580 --> 00:05:42,270
vrátiť rovnaký index pre čokoľvek
kapitalizácie je, ako to bude mať

102
00:05:42,270 --> 00:05:45,280
sa vrátil k úplne malá
verzie slová.

103
00:05:45,280 --> 00:05:45,950
Dobrá.

104
00:05:45,950 --> 00:05:47,410
>> Tak to je náš index.

105
00:05:47,410 --> 00:05:49,790
Je to hash tabuľka pre toto slovo.

106
00:05:49,790 --> 00:05:52,940
Teraz to pre slučke sa deje
na viac než na komunikačné zoznam

107
00:05:52,940 --> 00:05:55,000
ktorá bola v danom indexe.

108
00:05:55,000 --> 00:05:59,630
Takže všimnete sme inicializácii vstup
poukázať na danom indexe.

109
00:05:59,630 --> 00:06:03,480
Budeme sa aj naďalej pri vstupe robí
nie je rovné NULL, a pamätajte, že

110
00:06:03,480 --> 00:06:08,350
aktualizovať ukazovateľ v našom prepojenom zoznamu
vstup sa rovná entry-> ďalšie, takže majú

111
00:06:08,350 --> 00:06:13,840
náš súčasný vstupný bod do
Ďalším bodom v prepojenom zozname.

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

113
00:06:14,400 --> 00:06:19,150
>> Takže pre každú položku v prepojenom zoznamu,
budeme používať strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Nie je to strcmp, pretože raz sme
chcú robiť veci prípad necitlivo.

115
00:06:23,780 --> 00:06:28,830
Tak sme sa použiť strcasecmp porovnať slovo
, Ktorý bol odovzdaný k tejto funkcii

116
00:06:28,830 --> 00:06:31,860
proti slovu, ktoré
je v tejto položke.

117
00:06:31,860 --> 00:06:35,570
Ak sa vráti 0, to znamená, že tam bol
Zápas, v ktorom prípade chceme, aby

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

119
00:06:36,630 --> 00:06:39,590
Úspešne sme našli
Slovo v našom tabuľky hash.

120
00:06:39,590 --> 00:06:43,040
>> V prípade, že nebol zápas, potom sme
ísť na slučku znova a pozrieť sa na

121
00:06:43,040 --> 00:06:43,990
ďalší záznam.

122
00:06:43,990 --> 00:06:47,640
A budeme pokračovať smyčkování zatiaľ čo
sú položky v tejto aplikácii v zozname.

123
00:06:47,640 --> 00:06:50,160
Čo sa stane, keď sa rozídeme
z toho pre sláčiky?

124
00:06:50,160 --> 00:06:55,110
To znamená, že sme nemali nájsť položku, ktorá
uzavreté toto slovo, v tom prípade

125
00:06:55,110 --> 00:07:00,220
vrátime false čo znamená, že naše
hash tabuľka neobsahuje toto slovo.

126
00:07:00,220 --> 00:07:01,910
A to je pre kontrolu.

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

128
00:07:02,540 --> 00:07:04,790
>> Takže poďme sa pozrieť na veľkosti.

129
00:07:04,790 --> 00:07:09,280
Teraz, veľkosť bude veľmi jednoduchá
od nezabudnite v záťaži, pre každé slovo

130
00:07:09,280 --> 00:07:12,880
zistili sme, zvýši globálne
variabilný hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Takže funkcia veľkosť je len
bude vracať, že globálna

132
00:07:15,830 --> 00:07:18,150
variabilný, a to je všetko.

133
00:07:18,150 --> 00:07:22,300
>> Teraz konečne, musíme uvoľniť
slovník raz všetko hotové.

134
00:07:22,300 --> 00:07:25,340
Tak ako budeme robiť, že?

135
00:07:25,340 --> 00:07:30,440
Práve tu, my slučky cez všetky
vedierka našej hašovacej tabuľky.

136
00:07:30,440 --> 00:07:33,240
Takže tam sú NUM_BUCKETS vedierka.

137
00:07:33,240 --> 00:07:37,490
A pre každú aplikáciu v zozname v našej hash
stôl, ideme do slučky cez

138
00:07:37,490 --> 00:07:41,070
celistvosť prepojeného zoznamu
uvoľní každý prvok.

139
00:07:41,070 --> 00:07:46,070
Teraz musíme byť opatrní, tak sme tu
majú dočasnú premennú, ktoré je

140
00:07:46,070 --> 00:07:49,740
uloženie ukazovatele na ďalšie
prvok v prepojenom zozname.

141
00:07:49,740 --> 00:07:52,140
A potom budeme zadarmo
aktuálny prvok.

142
00:07:52,140 --> 00:07:55,990
>> Musíme si byť istí, že sme to urobiť, pretože my
nemôže len tak uvoľniť aktuálneho prvku

143
00:07:55,990 --> 00:07:59,260
a potom skúste prejdite na ďalšie ukazovatele
pretože akonáhle ju oslobodil

144
00:07:59,260 --> 00:08:00,870
pamäť sa stáva neplatným.

145
00:08:00,870 --> 00:08:04,990
Takže musíme držať okolo ukazovateľ na
Ďalší prvok, potom sa môžeme oslobodiť

146
00:08:04,990 --> 00:08:08,360
aktuálny prvok, a potom sa môžeme aktualizovať
Naše aktuálne prvok poukázať na

147
00:08:08,360 --> 00:08:09,590
ďalší prvok.

148
00:08:09,590 --> 00:08:12,770
>> Budeme slučky, zatiaľ čo tam sú prvky,
v tomto prepojenom zozname.

149
00:08:12,770 --> 00:08:16,450
Urobíme to pre všetky prepojené zoznamy v
hash tabuľka, a akonáhle budeme hotoví

150
00:08:16,450 --> 00:08:20,180
s tým, že sme úplne vyložený
hash tabuľka, a sme hotoví.

151
00:08:20,180 --> 00:08:24,050
Takže je to nemožné, uvoľní sa niekedy
return false, a keď sme hotoví, môžeme

152
00:08:24,050 --> 00:08:25,320
len vrátiť true.

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