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
Jaz sem Rob in hašiš dajmo
Ta rešitev ven.

4
00:00:16,210 --> 00:00:20,070
Torej, tukaj bomo izvajati
splošno hash tabelo.

5
00:00:20,070 --> 00:00:24,090
Vidimo, da struct node našega hash
miza bo izgledala takole.

6
00:00:24,090 --> 00:00:28,710
Tako se dogaja, da imajo char beseda
array dolžine velikosti plus 1.

7
00:00:28,710 --> 00:00:32,259
Ne pozabite na 1, saj je največja
beseda v slovarju, je 45.

8
00:00:32,259 --> 00:00:35,110
znakov, nato pa bomo
Potrebujemo en dodaten znak za

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

10
00:00:37,070 --> 00:00:40,870
>> In potem naša razpršena tabela v vsakem
bucket se dogaja, da shranite

11
00:00:40,870 --> 00:00:42,320
povezani seznam vozlišč.

12
00:00:42,320 --> 00:00:44,420
Ne počnemo ravno sondiranje tukaj.

13
00:00:44,420 --> 00:00:48,430
In tako, da se poveže na naslednji
element v vedro, moramo

14
00:00:48,430 --> 00:00:51,110
struct vozlišče * naslednji.

15
00:00:51,110 --> 00:00:53,090
Torej, to je tisto vozlišče izgleda.

16
00:00:53,090 --> 00:00:56,180
Zdaj, tukaj je deklaracija
naše razpršene tabele.

17
00:00:56,180 --> 00:01:01,910
To se dogaja, da imajo 16.384 vedra, vendar
to število ni važno.

18
00:01:01,910 --> 00:01:05,450
In končno, gremo, da imajo
Globalna spremenljivka hashtable_size, ki

19
00:01:05,450 --> 00:01:08,640
se dogaja, da začnete kot 0, in to je
dogaja, da bi spremljali, koliko besed

20
00:01:08,640 --> 00:01:10,080
so bile v našem slovarju.

21
00:01:10,080 --> 00:01:10,760
Vse je v redu.

22
00:01:10,760 --> 00:01:13,190
>> Tako da je lahko pogled na obremenitve.

23
00:01:13,190 --> 00:01:16,390
Tako opazili, da je obremenitev,
se vrne bool.

24
00:01:16,390 --> 00:01:20,530
Vam vrne true, če je bilo uspešno
naložen in false sicer.

25
00:01:20,530 --> 00:01:23,990
In to traja char * zvezdo
Slovar, ki je slovar

26
00:01:23,990 --> 00:01:25,280
da želimo odpreti.

27
00:01:25,280 --> 00:01:27,170
Tako da je prva stvar, ki
bomo storili.

28
00:01:27,170 --> 00:01:30,420
Bomo fopen slovar za
branje, in da bomo imeli

29
00:01:30,420 --> 00:01:34,700
se prepričajte, da je uspelo tako, če
se je vrnila NULL, potem nismo

30
00:01:34,700 --> 00:01:37,440
Uspešno odprite slovar
in moramo vrne false.

31
00:01:37,440 --> 00:01:41,580
>> Vendar ob predpostavki, da je to storila uspešno
open, nato pa smo želeli prebrati

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

33
00:01:42,400 --> 00:01:46,210
Tako da zanka, dokler ne bomo našli nekaj
Razlog za prekinitev iz tega

34
00:01:46,210 --> 00:01:47,570
zanke, ki bomo videli.

35
00:01:47,570 --> 00:01:51,780
Tako da zanka, in zdaj gremo
da malloc enotno vozlišče.

36
00:01:51,780 --> 00:01:56,800
In seveda, moramo k napakam pregled
spet tako da če mallocing ni uspelo

37
00:01:56,800 --> 00:02:00,660
in želimo, da se raztovarjanje kakršne koli vozlišče, ki smo
se je zgodilo z malloc prej, zaprite

38
00:02:00,660 --> 00:02:02,590
slovar in vrne false.

39
00:02:02,590 --> 00:02:07,440
>> Ampak ignoriranje, da ob predpostavki, da bomo
uspelo, nato pa smo želeli uporabiti fscanf

40
00:02:07,440 --> 00:02:12,400
se glasi eno samo besedo iz našega
slovar v naše vozlišče.

41
00:02:12,400 --> 00:02:17,310
Torej, ne pozabite, da vstop-> beseda je char
beseda buffer dolžine plus velikost

42
00:02:17,310 --> 00:02:20,300
tisti, ki bomo
shranite besedo prijavite

43
00:02:20,300 --> 00:02:25,280
Torej fscanf se bo vrnil 1, dokler
kot je bilo uspešno prebrati

44
00:02:25,280 --> 00:02:26,750
Beseda iz spisa.

45
00:02:26,750 --> 00:02:31,030
>> Če katera napaka se zgodi, ali smo dosegli
Konec datoteke, da ne bo

46
00:02:31,030 --> 00:02:34,950
vrne 1 v tem primeru, če ne
vrne 1, smo na koncu bo prekinil

47
00:02:34,950 --> 00:02:37,280
od tega, medtem ko zanke.

48
00:02:37,280 --> 00:02:42,770
Tako vidimo, da ko bomo imeli uspešno
prebrati besedo v

49
00:02:42,770 --> 00:02:48,270
vstopno-> beseda, potem pa bomo hash
ta beseda uporabo našega hash funkcijo.

50
00:02:48,270 --> 00:02:49,580
Oglejmo si na
hash funkcijo.

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

52
00:02:52,430 --> 00:02:55,610
>> Tako da ne boste res potrebujejo
razumeti.

53
00:02:55,610 --> 00:02:59,460
In dejansko smo pravkar potegnil to
hash funkcijo iz interneta.

54
00:02:59,460 --> 00:03:04,010
Edina stvar, morate priznati, je
da to traja char * besedo,

55
00:03:04,010 --> 00:03:08,960
tako da je ob niz kot vložek in
vračanje nepodpisan int kot proizvodnja.

56
00:03:08,960 --> 00:03:12,360
Tako, da je vse hash funkcija je, ali je
traja v vhod, vam omogoča

57
00:03:12,360 --> 00:03:14,490
Indeks v hash tabelo.

58
00:03:14,490 --> 00:03:18,530
Opazimo, da smo modding z NUM_BUCKETS
tako vrnjena vrednost hash

59
00:03:18,530 --> 00:03:21,730
dejansko je indeks v hash tabelo
in ne indeks tistega

60
00:03:21,730 --> 00:03:24,320
mejá matrike.

61
00:03:24,320 --> 00:03:27,855
>> Torej, glede na to, hash funkcijo, gremo
za razpršitev besedo, ki beremo

62
00:03:27,855 --> 00:03:31,700
iz slovarja, nato pa se bomo
za uporabo, ki ima za vstavljanje

63
00:03:31,700 --> 00:03:33,750
Začetek razpršene tabele.

64
00:03:33,750 --> 00:03:38,830
Zdaj, Hashtable hash je trenutna
povezani seznam v razpršene tabele, ter

65
00:03:38,830 --> 00:03:41,410
to je zelo možno, da je le NULL.

66
00:03:41,410 --> 00:03:45,640
Želimo, da vstavite svoj vstop na
začetku tega povezani seznam, in tako

67
00:03:45,640 --> 00:03:48,910
bomo morali naše sedanje vnos
opozarjajo na kakšen razpršene tabele trenutno

68
00:03:48,910 --> 00:03:54,030
opozarja na in potem bomo za shranjevanje
V razpršene tabele na hašiš

69
00:03:54,030 --> 00:03:55,350
trenutni vpis.

70
00:03:55,350 --> 00:03:59,320
>> Torej ti dve vrstici uspešno vstavite
Vpis na začetku

71
00:03:59,320 --> 00:04:02,270
povezani seznam v tem indeksu
v razpršene tabele.

72
00:04:02,270 --> 00:04:04,900
Ko smo končali s tem, vemo,
da smo našli še eno besedo

73
00:04:04,900 --> 00:04:07,800
slovar in smo spet prirastek.

74
00:04:07,800 --> 00:04:13,960
Tako smo ostali storiti, dokler fscanf
končno vrne nekaj, non 1 na

75
00:04:13,960 --> 00:04:18,560
kateri točki se spomnite, da moramo
prost vstop, tako da tukaj smo malloced

76
00:04:18,560 --> 00:04:21,329
Vnos in smo poskušali prebrati nekaj
iz slovarja.

77
00:04:21,329 --> 00:04:24,110
In nismo uspešno prebrati
Nekaj ​​od slovarju v katerem

78
00:04:24,110 --> 00:04:27,440
primeru moramo osvoboditi vnos, ki smo
nikoli dejansko dana v razpršene tabele

79
00:04:27,440 --> 00:04:29,110
in končno prekinil.

80
00:04:29,110 --> 00:04:32,750
>> Ko smo izbruhnejo, moramo videti, dobro,
smo izbruhnejo, ker tam

81
00:04:32,750 --> 00:04:35,840
je bila napaka pri branju iz datoteke, ali
smo izbruhnila, ker smo dosegli

82
00:04:35,840 --> 00:04:37,120
Konec datoteke?

83
00:04:37,120 --> 00:04:40,150
Če je prišlo do napake, nato pa smo želeli
vrne false, ker obremenitev ni

84
00:04:40,150 --> 00:04:43,260
uspeti, in v procesu, želimo
razložiti vse besede, ki jih beremo

85
00:04:43,260 --> 00:04:45,670
v in zaprite datoteko slovarja.

86
00:04:45,670 --> 00:04:48,740
Ob predpostavki, da nam ni uspelo, nato pa smo pravkar
še vedno morali zapreti slovar

87
00:04:48,740 --> 00:04:51,970
datoteko, in na koncu vrne true, saj
smo uspešno naložen

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

89
00:04:53,040 --> 00:04:54,420
In to je to za tovor.

90
00:04:54,420 --> 00:04:59,020
>> Torej, zdaj preveriti, saj naložen razpršena tabela,
bo izgledala takole.

91
00:04:59,020 --> 00:05:02,690
Zato preverite, da vrne bool, ki
se dogaja, da navedejo, ali

92
00:05:02,690 --> 00:05:07,530
opravili-in Char * besedo, ali
opravili-in niz je v našem slovarju.

93
00:05:07,530 --> 00:05:10,530
Torej, če je v slovarju, če je
v naši razpršene tabele, se bomo vrnili

94
00:05:10,530 --> 00:05:13,380
res, in če ni,
se bomo vrnili napačen.

95
00:05:13,380 --> 00:05:17,770
Glede na to minilo-in beseda, smo
gre za razpršitev besedo.

96
00:05:17,770 --> 00:05:22,020
>> Zdaj, pomembna stvar je, da priznajo
da v obremenitvi, smo vedeli, da so vsi

97
00:05:22,020 --> 00:05:25,820
besede so bile bo malimi črkami,
ampak tukaj, nismo tako prepričani.

98
00:05:25,820 --> 00:05:29,510
Če pogledamo našo hash funkcijo,
naša hash funkcija dejansko

99
00:05:29,510 --> 00:05:32,700
je lowercasing vsak znak
besede.

100
00:05:32,700 --> 00:05:37,580
Torej, ne glede na kapitalizacijo
beseda, naš hash funkcija bo

101
00:05:37,580 --> 00:05:42,270
vrne isti indeks za karkoli
kapitalizacija je, kot bi morala

102
00:05:42,270 --> 00:05:45,280
vrnjeni v celoti male črke
različica besede.

103
00:05:45,280 --> 00:05:45,950
Vse je v redu.

104
00:05:45,950 --> 00:05:47,410
>> Tako, da je naš indeks.

105
00:05:47,410 --> 00:05:49,790
To je razpršena tabela za te besede.

106
00:05:49,790 --> 00:05:52,940
Zdaj, to zanko se dogaja
da preko povezani seznam

107
00:05:52,940 --> 00:05:55,000
, ki je bil v tistem indeksu.

108
00:05:55,000 --> 00:05:59,630
Torej opazili smo inicializacija vnos
poudariti, da tega indeksa.

109
00:05:59,630 --> 00:06:03,480
Bomo še naprej, medtem ko vnos ne
ni enaka NULL, in ne pozabite, da

110
00:06:03,480 --> 00:06:08,350
posodabljanje kazalec v našem povezanem seznamu
Vnos je enako vstopno-> naslednji, tako da imajo

111
00:06:08,350 --> 00:06:13,840
Naša trenutna vstopna točka za
Naslednji element v povezanem seznamu.

112
00:06:13,840 --> 00:06:14,400
Vse je v redu.

113
00:06:14,400 --> 00:06:19,150
>> Torej, za vsak vpis v povezanem seznamu
bomo uporabili strcasecmp.

114
00:06:19,150 --> 00:06:23,780
To ni strcmp, ker še enkrat, bomo
želeli narediti stvari primera insensitively.

115
00:06:23,780 --> 00:06:28,830
Tako smo uporabili strcasecmp primerjati besedo
, ki je bil sprejet na tej funkciji

116
00:06:28,830 --> 00:06:31,860
ob besedi, ki
je v tej točki.

117
00:06:31,860 --> 00:06:35,570
Če se vrne 0, kar pomeni, da ni bilo
ujemanje, v tem primeru želimo

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

119
00:06:36,630 --> 00:06:39,590
Uspešno smo ugotovili
beseda v našem razpršene tabele.

120
00:06:39,590 --> 00:06:43,040
>> Če ne bi bilo tekmo, nato pa smo
spet bo zanke in pogled na

121
00:06:43,040 --> 00:06:43,990
next entry.

122
00:06:43,990 --> 00:06:47,640
In bomo še naprej loopinga medtem ko
so navedbe v tej povezanem seznamu.

123
00:06:47,640 --> 00:06:50,160
Kaj se zgodi, če razbijemo
v to zanko?

124
00:06:50,160 --> 00:06:55,110
To pomeni, da nismo našli vnos, ki
ujema to besedo, v tem primeru

125
00:06:55,110 --> 00:07:00,220
vrnemo false, ki označuje, da je naš
razpršene tabele ne vsebujejo to besedo.

126
00:07:00,220 --> 00:07:01,910
In da je za pregled.

127
00:07:01,910 --> 00:07:02,540
Vse je v redu.

128
00:07:02,540 --> 00:07:04,790
>> Tako da je lahko pogled na velikost.

129
00:07:04,790 --> 00:07:09,280
Zdaj, velikost se bo zelo preprosta
od zapomni pri obremenitvi, za vsako besedo

130
00:07:09,280 --> 00:07:12,880
smo ugotovili, smo se poveča globalno
spremenljivka hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Torej funkcija znaša le
vrača, da svetovna

132
00:07:15,830 --> 00:07:18,150
spremenljivka, in to je to.

133
00:07:18,150 --> 00:07:22,300
>> Zdaj končno moramo raztovoriti
slovar, ko je vse končano.

134
00:07:22,300 --> 00:07:25,340
Torej, kako bomo to storili?

135
00:07:25,340 --> 00:07:30,440
Tukaj sem, da smo zanka nad vsem
vedra naše razpršene tabele.

136
00:07:30,440 --> 00:07:33,240
Torej obstajajo NUM_BUCKETS vedra.

137
00:07:33,240 --> 00:07:37,490
In za vsakega povezanega seznama v naši hash
miza, bomo zanko

138
00:07:37,490 --> 00:07:41,070
celota povezanega seznama
sprostitev vsak element.

139
00:07:41,070 --> 00:07:46,070
Zdaj pa moramo biti previdni, tako da tukaj smo
imajo začasno spremenljivko, ki je

140
00:07:46,070 --> 00:07:49,740
shranjevanje kazalec na naslednji
element v povezanem seznamu.

141
00:07:49,740 --> 00:07:52,140
In potem bomo brezplačno
trenutni element.

142
00:07:52,140 --> 00:07:55,990
>> Moramo biti prepričani, da bomo to naredili, ker smo
Ne moreš sprostiti trenutni element

143
00:07:55,990 --> 00:07:59,260
in nato poskusite za dostop do naslednjega kazalec
saj ko bomo osvobodili

144
00:07:59,260 --> 00:08:00,870
spomin postane neveljaven.

145
00:08:00,870 --> 00:08:04,990
Zato moramo ohraniti okoli kazalec
Naslednji element, potem bomo lahko osvobodi

146
00:08:04,990 --> 00:08:08,360
Sedanji element, in potem bomo lahko posodobite
Naš trenutni element, da kaže na

147
00:08:08,360 --> 00:08:09,590
Naslednji element.

148
00:08:09,590 --> 00:08:12,770
>> Bomo zanko, medtem ko obstajajo elementi
V tem povezani seznam.

149
00:08:12,770 --> 00:08:16,450
To bomo storili za vse povezane sezname
razpršene tabele, in ko sva končala

150
00:08:16,450 --> 00:08:20,180
S tem smo v celoti raztovoriti
hash tabelo, in sva končala.

151
00:08:20,180 --> 00:08:24,050
Zato je nemogoče, da bi kdaj raztovarja
vrne false, in ko bomo končali, smo

152
00:08:24,050 --> 00:08:25,320
pravkar vrnil res.

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