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
Jsem Rob, a pojďme hash
Tento roztok se.

4
00:00:16,210 --> 00:00:20,070
Takže tady budeme realizovat
Obecně hash tabulky.

5
00:00:20,070 --> 00:00:24,090
Vidíme, že struct uzel naší hash
tabulka bude vypadat takto.

6
00:00:24,090 --> 00:00:28,710
Takže to bude mít char slovo
pole o délce size plus 1.

7
00:00:28,710 --> 00:00:32,259
Nezapomeňte 1 od maxima
slovo ve slovníku je 45

8
00:00:32,259 --> 00:00:35,110
znaky, a pak budeme
Potřebujeme jeden další znak pro

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

10
00:00:37,070 --> 00:00:40,870
>> A pak naše hash tabulka v každém
kbelík se bude ukládat

11
00:00:40,870 --> 00:00:42,320
spojový seznam uzlů.

12
00:00:42,320 --> 00:00:44,420
Neděláme lineární snímací zde.

13
00:00:44,420 --> 00:00:48,430
A tak, aby odkazy na další
prvek v kbelíku, musíme

14
00:00:48,430 --> 00:00:51,110
struct uzel * další.

15
00:00:51,110 --> 00:00:53,090
Takže to je to, co uzel vypadá.

16
00:00:53,090 --> 00:00:56,180
Nyní je zde prohlášení
z naší tabulky hash.

17
00:00:56,180 --> 00:01:01,910
Bude to mít 16.384 kbelíky, ale
že počet nezáleží.

18
00:01:01,910 --> 00:01:05,450
A konečně budeme mít
globální proměnná hashtable_size, které

19
00:01:05,450 --> 00:01:08,640
se chystá odstartovat jako 0, a to
bude sledovat, kolik slov

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

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

22
00:01:10,760 --> 00:01:13,190
>> Takže pojďme se podívat na zatížení.

23
00:01:13,190 --> 00:01:16,390
Takže všimnout, že zatížení,
vrací bool.

24
00:01:16,390 --> 00:01:20,530
Můžete se vrátit true, pokud bylo úspěšné
naložený a v opačném případě false.

25
00:01:20,530 --> 00:01:23,990
A to trvá const char * hvězdu
slovník, který je slovník

26
00:01:23,990 --> 00:01:25,280
který chceme otevřít.

27
00:01:25,280 --> 00:01:27,170
Takže to je první věc,
budeme dělat.

28
00:01:27,170 --> 00:01:30,420
Chystáme se fopen slovník pro
čtení, a budeme mít

29
00:01:30,420 --> 00:01:34,700
aby se ujistil, že se podařilo, aby v případě,
to se vrátilo NULL, pak ne

30
00:01:34,700 --> 00:01:37,440
úspěšně otevřít slovník
a my se musíme vrátit false.

31
00:01:37,440 --> 00:01:41,580
>> Ale za předpokladu, že to úspěšně udělal
otevřené, pak chceme přečíst

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

33
00:01:42,400 --> 00:01:46,210
Takže mějte opakování, dokud nenajdeme nějaký
důvod, aby se vymanily z této

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

35
00:01:47,570 --> 00:01:51,780
Takže mějte opakování, a teď jdeme
malloc jeden uzel.

36
00:01:51,780 --> 00:01:56,800
A samozřejmě, musíme k chybě kontroly
znovu, takže pokud mallocing neuspěl

37
00:01:56,800 --> 00:02:00,660
a chceme vyložit libovolný uzel, který my
stalo malloc před zavřete

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

39
00:02:02,590 --> 00:02:07,440
>> Ale ignorovat, že za předpokladu, že se
podařilo, pak chceme použít fscanf

40
00:02:07,440 --> 00:02:12,400
přečíst jediné slovo z naší
slovník do našeho uzlu.

41
00:02:12,400 --> 00:02:17,310
Takže pamatujte, že vstupní-> slovo je char
Slovo vyrovnávací délky plus velikosti

42
00:02:17,310 --> 00:02:20,300
jedno, že budeme
uložit slovo dovnitř

43
00:02:20,300 --> 00:02:25,280
Takže fscanf se chystá k návratu 1 tak dlouho,
jak to bylo možné úspěšně číst

44
00:02:25,280 --> 00:02:26,750
slovo ze souboru.

45
00:02:26,750 --> 00:02:31,030
>> Pokud to buď chyba se stane, nebo se dostaneme
konec souboru, nebude

46
00:02:31,030 --> 00:02:34,950
vrátí 1 v tom případě, pokud to není
vrátí 1, jsme se konečně chystá zlomit

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

48
00:02:37,280 --> 00:02:42,770
Takže vidíme, že jednou se nám podařilo mít
číst slovo do

49
00:02:42,770 --> 00:02:48,270
entry-> slovo, pak jedeme do hash
že slovo pomocí našeho hash funkce.

50
00:02:48,270 --> 00:02:49,580
Pojďme se podívat na
funkce hash.

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

52
00:02:52,430 --> 00:02:55,610
>> Takže nemáte opravdu potřebujete
to pochopit.

53
00:02:55,610 --> 00:02:59,460
A vlastně, prostě vytáhl to
hash funkce z internetu.

54
00:02:59,460 --> 00:03:04,010
Jediná věc, kterou je třeba si uvědomit, je
že to trvá const char * slovo,

55
00:03:04,010 --> 00:03:08,960
tak to trvá řetězec jako vstup a
vrácením unsigned int jako výstup.

56
00:03:08,960 --> 00:03:12,360
Tak to je vše, funkce hash je, je to
bere na vstupu, to vám dává

57
00:03:12,360 --> 00:03:14,490
index do tabulky hash.

58
00:03:14,490 --> 00:03:18,530
Všimněte si, že jsme modding by NUM_BUCKETS
takže vrácena hodnota hash

59
00:03:18,530 --> 00:03:21,730
ve skutečnosti je index do tabulky hash
a není index za

60
00:03:21,730 --> 00:03:24,320
meze pole.

61
00:03:24,320 --> 00:03:27,855
>> Takže za předpokladu, že hashovací funkce, jedeme
hash slovo, které čteme

62
00:03:27,855 --> 00:03:31,700
ze slovníku, a pak jdeme
k použití, který má vložit

63
00:03:31,700 --> 00:03:33,750
vstup do hash tabulky.

64
00:03:33,750 --> 00:03:38,830
Nyní, Hashtable hash je aktuální
spojový seznam v tabulce hash, a

65
00:03:38,830 --> 00:03:41,410
je velmi pravděpodobné, že je jen NULL.

66
00:03:41,410 --> 00:03:45,640
Chceme vložit náš vstup na
začátku tohoto spojového seznamu, a tak

67
00:03:45,640 --> 00:03:48,910
budeme mít naši aktuální položku
poukázat na to, co hash tabulky v současné době

68
00:03:48,910 --> 00:03:54,030
body, a pak budeme ukládat
v hash tabulce na hash

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

70
00:03:55,350 --> 00:03:59,320
>> Takže tyto dva řádky úspěšně vložit
Vstup na začátku

71
00:03:59,320 --> 00:04:02,270
spojový seznam v tomto indexu
v tabulce hash.

72
00:04:02,270 --> 00:04:04,900
Jakmile jsme hotovi s tím, víme,
že jsme našli další slovo

73
00:04:04,900 --> 00:04:07,800
slovník a opět zvyšovat.

74
00:04:07,800 --> 00:04:13,960
Tak jsme to dělat, dokud fscanf
konečně vrátí něco non 1 na

75
00:04:13,960 --> 00:04:18,560
kterém místě si uvědomit, že musíme
vstup zdarma, takže tady jsme malloced

76
00:04:18,560 --> 00:04:21,329
vstup a snažili jsme se, aby si něco přečíst
ze slovníku.

77
00:04:21,329 --> 00:04:24,110
A my jsme neměli úspěšně číst
něco ze slovníku, ve kterém

78
00:04:24,110 --> 00:04:27,440
případě musíme uvolnit záznam, který my
nikdy dát do hash tabulky

79
00:04:27,440 --> 00:04:29,110
a konečně zlomit.

80
00:04:29,110 --> 00:04:32,750
>> Poté, co jsme se vymanit, musíme vidět, dobře,
jsme se zlomit, protože tam

81
00:04:32,750 --> 00:04:35,840
byla chyba při čtení ze souboru, nebo
jsme se zlomit, protože jsme dosáhli

82
00:04:35,840 --> 00:04:37,120
konec souboru?

83
00:04:37,120 --> 00:04:40,150
Pokud došlo k chybě, pak chceme, aby
return false, protože zatížení ne

84
00:04:40,150 --> 00:04:43,260
uspět, a v tomto procesu, chceme
vyložit všechna slova, která čteme

85
00:04:43,260 --> 00:04:45,670
v a zavřete soubor slovníku.

86
00:04:45,670 --> 00:04:48,740
Za předpokladu, že jsme se to podaří, pak jsme jen
Stále je třeba zavřít slovník

87
00:04:48,740 --> 00:04:51,970
soubor, a nakonec se vrátíte pravda, protože
jsme úspěšně 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 pro zatížení.

90
00:04:54,420 --> 00:04:59,020
>> Takže teď zjistit, vzhledem k tomu naložené hash tabulky,
bude vypadat takto.

91
00:04:59,020 --> 00:05:02,690
Tak se podívejte, vrací bool, který
se chystá uvést, zda

92
00:05:02,690 --> 00:05:07,530
předaný v char * slovo, zda
uplynulo-in string je v našem slovníku.

93
00:05:07,530 --> 00:05:10,530
Takže, je-li ve slovníku, je-li
v naší hašovací tabulce, vrátíme se

94
00:05:10,530 --> 00:05:13,380
pravda, a pokud to není,
vrátíme false.

95
00:05:13,380 --> 00:05:17,770
Vzhledem k tomu, to prošel-in slovo, my jsme
bude hash slovo.

96
00:05:17,770 --> 00:05:22,020
>> Nyní důležité si uvědomit, je
že v zátěži, věděli jsme, že všechny

97
00:05:22,020 --> 00:05:25,820
slova se bude malá písmena,
ale tady, my nejsme tak jistí.

98
00:05:25,820 --> 00:05:29,510
Pokud se podíváme na náš hash funkce,
naše hash funkce vlastně

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

100
00:05:32,700 --> 00:05:37,580
Takže bez ohledu na kapitalizace
Slovo, náš hash funkce se chystá

101
00:05:37,580 --> 00:05:42,270
vrátit stejný index pro cokoliv
kapitalizace je, jak to bude mít

102
00:05:42,270 --> 00:05:45,280
se vrátil k úplně malá
verze slova.

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 tabulka pro toto slovo.

106
00:05:49,790 --> 00:05:52,940
Teď to pro smyčce se děje
na více než na spojový seznam

107
00:05:52,940 --> 00:05:55,000
která byla v daném indexu.

108
00:05:55,000 --> 00:05:59,630
Takže všimnete jsme inicializaci vstup
poukázat na daném indexu.

109
00:05:59,630 --> 00:06:03,480
Budeme se i nadále při vstupu dělá
není rovno NULL, a pamatujte, že

110
00:06:03,480 --> 00:06:08,350
aktualizovat ukazatel v našem propojeném seznamu
vstup se rovná entry-> další, takže mají

111
00:06:08,350 --> 00:06:13,840
náš současný vstupní bod do
Dalším bodem v propojeném seznamu.

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

113
00:06:14,400 --> 00:06:19,150
>> Takže pro každou položku v propojeném seznamu,
budeme používat strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Není to strcmp, protože jednou jsme
chtějí dělat věci případ necitlivě.

115
00:06:23,780 --> 00:06:28,830
Tak jsme se použít strcasecmp porovnat slovo
, který byl předán k této funkci

116
00:06:28,830 --> 00:06:31,860
proti slovu, které
je v této položce.

117
00:06:31,860 --> 00:06:35,570
Pokud se vrátí 0, to znamená, že tam byl
Zápas, ve kterém případě chceme, aby

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

119
00:06:36,630 --> 00:06:39,590
Úspěšně jsme našli
Slovo v našem tabulky hash.

120
00:06:39,590 --> 00:06:43,040
>> V případě, že nebyl zápas, pak jsme
jít na smyčku znovu a podívat se na

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

122
00:06:43,990 --> 00:06:47,640
A budeme pokračovat smyčkování zatímco
jsou položky v této aplikaci v seznamu.

123
00:06:47,640 --> 00:06:50,160
Co se stane, když se rozejdeme
z toho pro smyčce?

124
00:06:50,160 --> 00:06:55,110
To znamená, že jsme neměli najít položku, která
uzavřeno toto slovo, v tom případě

125
00:06:55,110 --> 00:07:00,220
vrátíme false což znamená, že naše
hash tabulka neobsahuje toto slovo.

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

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

128
00:07:02,540 --> 00:07:04,790
>> Takže pojďme se podívat na velikosti.

129
00:07:04,790 --> 00:07:09,280
Nyní, velikost bude velmi jednoduchá
od nezapomeňte v zátěži, pro každé slovo

130
00:07:09,280 --> 00:07:12,880
zjistili jsme, zvýší globální
variabilní hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Takže funkce velikost je jen
bude vracet, že globální

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

133
00:07:18,150 --> 00:07:22,300
>> Nyní konečně, musíme uvolnit
slovník jednou všechno hotovo.

134
00:07:22,300 --> 00:07:25,340
Tak jak budeme dělat, že?

135
00:07:25,340 --> 00:07:30,440
Právě tady, my smyčky přes všechny
kbelíky naší hašovací tabulky.

136
00:07:30,440 --> 00:07:33,240
Takže tam jsou NUM_BUCKETS kbelíky.

137
00:07:33,240 --> 00:07:37,490
A pro každou aplikaci v seznamu v naší hash
stůl, jedeme do smyčky přes

138
00:07:37,490 --> 00:07:41,070
celistvost propojeného seznamu
uvolní každý prvek.

139
00:07:41,070 --> 00:07:46,070
Nyní musíme být opatrní, tak jsme tady
mají dočasnou proměnnou, které je

140
00:07:46,070 --> 00:07:49,740
uložení ukazatele na další
prvek v propojeném seznamu.

141
00:07:49,740 --> 00:07:52,140
A pak budeme zdarma
aktuální prvek.

142
00:07:52,140 --> 00:07:55,990
>> Musíme si být jisti, že jsme to udělat, protože my
nemůže jen tak uvolnit aktuálního prvku

143
00:07:55,990 --> 00:07:59,260
a pak zkuste přejděte na další ukazatele
protože jakmile ji osvobodil

144
00:07:59,260 --> 00:08:00,870
paměť se stává neplatným.

145
00:08:00,870 --> 00:08:04,990
Takže musíme držet kolem ukazatel na
Další prvek, pak se můžeme osvobodit

146
00:08:04,990 --> 00:08:08,360
aktuální prvek, a pak se můžeme aktualizovat
Naše aktuální prvek poukázat na

147
00:08:08,360 --> 00:08:09,590
další prvek.

148
00:08:09,590 --> 00:08:12,770
>> Budeme smyčky, zatímco tam jsou prvky,
v tomto propojeném seznamu.

149
00:08:12,770 --> 00:08:16,450
Uděláme to pro všechny propojené seznamy v
hash tabulka, a jakmile budeme hotovi

150
00:08:16,450 --> 00:08:20,180
s tím, že jsme zcela vyloženo
hash tabulka, a jsme hotovi.

151
00:08:20,180 --> 00:08:24,050
Takže je to nemožné, uvolní se někdy
return false, a když jsme hotovi, můžeme

152
00:08:24,050 --> 00:08:25,320
jen vrátit true.

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