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

2
00:00:11,856 --> 00:00:13,050
>> ROB Bowden: Bok.

3
00:00:13,050 --> 00:00:16,210
Ja sam Rob, i neka je mljeveno meso
ovo rješenje se.

4
00:00:16,210 --> 00:00:20,070
Dakle, ovdje ćemo provesti
Općenito hash tablicu.

5
00:00:20,070 --> 00:00:24,090
Vidimo da struct node našeg mljeveno meso
Stol će izgledati ovako.

6
00:00:24,090 --> 00:00:28,710
Dakle, to će imati char riječ
Niz duljine veličine plus jedan.

7
00:00:28,710 --> 00:00:32,259
Nemojte zaboraviti jedan jer je najduže
Riječ u rječniku je 45

8
00:00:32,259 --> 00:00:35,110
likovi, a onda idemo u
treba mi jedan dodatni znak za

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

10
00:00:37,070 --> 00:00:40,870
>> I onda naš hash tablicu u svakoj
kanta će pohraniti

11
00:00:40,870 --> 00:00:42,320
povezani popis čvorova.

12
00:00:42,320 --> 00:00:44,420
Ne radimo linearnu sondiranja ovdje.

13
00:00:44,420 --> 00:00:48,430
I tako, kako bi se povezati na sljedećoj
element u kantu, trebamo

14
00:00:48,430 --> 00:00:51,110
struct node * next.

15
00:00:51,110 --> 00:00:53,090
Dakle, to je ono što čvor izgleda.

16
00:00:53,090 --> 00:00:56,180
Sada, ovdje je deklaracija
našeg hash tablicu.

17
00:00:56,180 --> 00:01:01,910
To će imati 16.384 kante, ali
taj broj zapravo ne smeta.

18
00:01:01,910 --> 00:01:05,450
I na kraju, da ćemo imati
Globalna varijabla hashtable_size, koji

19
00:01:05,450 --> 00:01:08,640
će krenuti kao 0, a to je
će pratiti koliko riječi

20
00:01:08,640 --> 00:01:10,080
bili su u našem rječniku.

21
00:01:10,080 --> 00:01:10,760
U redu.

22
00:01:10,760 --> 00:01:13,190
>> Tako ćemo pogledati na teret.

23
00:01:13,190 --> 00:01:16,390
Dakle, primijetite da je opterećenje,
to vraća bool.

24
00:01:16,390 --> 00:01:20,530
Vraćate li istina da je uspješno
učitan i lažno drugi način.

25
00:01:20,530 --> 00:01:23,990
I to traje const char * zvijezdu
rječnik, koji je rječnik

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

27
00:01:25,280 --> 00:01:27,170
Dakle, to je prva stvar
idemo raditi.

28
00:01:27,170 --> 00:01:30,420
Idemo u fopen rječnik za
čitanje, a mi ćemo imati

29
00:01:30,420 --> 00:01:34,700
kako bi bili sigurni da je to uspjelo pa ako
je vratio NULL, onda nismo

30
00:01:34,700 --> 00:01:37,440
Uspješno otvaranje rječnik
i moramo se vratiti false.

31
00:01:37,440 --> 00:01:41,580
>> No, uz pretpostavku da je uspješno učinio
otvoren, onda želimo čitati

32
00:01:41,580 --> 00:01:42,400
rječnik.

33
00:01:42,400 --> 00:01:46,210
Dakle, imajte petlje dok ne nađemo neki
Razlog da se probijemo iz toga

34
00:01:46,210 --> 00:01:47,570
Petlja koja ćemo vidjeti.

35
00:01:47,570 --> 00:01:51,780
Dakle, imajte petlje, a sada idemo
na malloc jedan čvor.

36
00:01:51,780 --> 00:01:56,800
I naravno, moramo pogrešaka ček
opet pa ako mallocing nisu uspjeli

37
00:01:56,800 --> 00:02:00,660
i želimo rasteretiti bilo čvor koji smo
dogodilo malloc prije, zatvorite

38
00:02:00,660 --> 00:02:02,590
rječnik i povratak false.

39
00:02:02,590 --> 00:02:07,440
>> No, ignoriranje da, pod pretpostavkom da
uspjeli, onda želimo koristiti fscanf

40
00:02:07,440 --> 00:02:12,400
čitati jednu riječ iz naše
Rječnik u našu čvora.

41
00:02:12,400 --> 00:02:17,310
Dakle, ne zaboravite da je ulazak-> riječ je char
Riječ tampon duljine veličine plus

42
00:02:17,310 --> 00:02:20,300
onaj koji ćemo
pohraniti riječ u.

43
00:02:20,300 --> 00:02:25,280
Dakle fscanf će vratiti 1 dokle
kao što je bio u mogućnosti uspješno pročitati

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

45
00:02:26,750 --> 00:02:31,030
>> Ako je bilo pogrešaka dogodi ili ne stignemo
kraj datoteke, to neće

46
00:02:31,030 --> 00:02:34,950
vratiti jedan u kojem slučaju, ako se to ne dogodi
povratak 1, napokon smo idemo razbiti

47
00:02:34,950 --> 00:02:37,280
iz ovog while petlje.

48
00:02:37,280 --> 00:02:42,770
Dakle, vidimo da je jednom uspješno smo
pročitati riječ u

49
00:02:42,770 --> 00:02:48,270
entry-> riječ, onda idemo u hash
da je riječ pomoću naše hash funkciju.

50
00:02:48,270 --> 00:02:49,580
Idemo pogledati
hash funkcija.

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

52
00:02:52,430 --> 00:02:55,610
>> Tako da stvarno ne treba
razumjeti to.

53
00:02:55,610 --> 00:02:59,460
I doista, samo mi je izvukao ovo
hash funkciju s interneta.

54
00:02:59,460 --> 00:03:04,010
Jedino što morate prepoznati je
da to traje const char * riječ,

55
00:03:04,010 --> 00:03:08,960
pa to je uzimanje niz kao ulaz i
povratka nepotpisani int kao izlaz.

56
00:03:08,960 --> 00:03:12,360
Dakle, to je sve hash funkcija, je li to
Potrebno je u ulazu, to vam daje

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

58
00:03:14,490 --> 00:03:18,530
Uočite da smo modding by NUM_BUCKETS
pa hash vrijednost vratio

59
00:03:18,530 --> 00:03:21,730
zapravo je indeks u hash tablicu
a ne indeks izvan

60
00:03:21,730 --> 00:03:24,320
Granica u nizu.

61
00:03:24,320 --> 00:03:27,855
>> Dakle, s obzirom da je hash funkcija, idemo
hash riječ da čitamo

62
00:03:27,855 --> 00:03:31,700
iz rječnika, a potom idemo
koristiti da ima za umetanje

63
00:03:31,700 --> 00:03:33,750
Ulazak u hash tablicu.

64
00:03:33,750 --> 00:03:38,830
Sada, hashtable hash je trenutna
povezani popis u hash tablici, a

65
00:03:38,830 --> 00:03:41,410
to je vrlo moguće da je samo NULL.

66
00:03:41,410 --> 00:03:45,640
Mi želimo umetnuti naš ulazak u
Početkom ovog popisa povezane, i tako

67
00:03:45,640 --> 00:03:48,910
ćemo imati naš trenutni unos
ukazuju na ono što je hash tablicu trenutno

68
00:03:48,910 --> 00:03:54,030
bodovi se i onda ćemo pohraniti
u hash tablicu na mljeveno meso

69
00:03:54,030 --> 00:03:55,350
tekući zapis.

70
00:03:55,350 --> 00:03:59,320
>> Dakle, ove dvije linije Uspješno umetanje
Ulazak na početku

71
00:03:59,320 --> 00:04:02,270
povezani popis u tom indeksu
u hash tablicu.

72
00:04:02,270 --> 00:04:04,900
Nakon što završimo s tim, znamo
da smo pronašli još jednu riječ u

73
00:04:04,900 --> 00:04:07,800
rječnik, a mi opet povećavati.

74
00:04:07,800 --> 00:04:13,960
Tako smo zadržati taj događaj dok fscanf
konačno vrati nešto ne 1 na

75
00:04:13,960 --> 00:04:18,560
kojem trenutku ne zaboravite da moramo
ulaz slobodan, tako da se ovdje, malloced smo

76
00:04:18,560 --> 00:04:21,329
Ulazak i mi pokušali pročitati nešto
iz rječnika.

77
00:04:21,329 --> 00:04:24,110
I nismo uspješno pročitati
nešto iz rječnika u kojoj

78
00:04:24,110 --> 00:04:27,440
Slučaj moramo osloboditi zapis koji smo
Nikad zapravo staviti u hash tablicu

79
00:04:27,440 --> 00:04:29,110
i na kraju slomiti.

80
00:04:29,110 --> 00:04:32,750
>> Nakon što smo izbijati, moramo vidjeti, dobro,
nije mi izbije jer postoji

81
00:04:32,750 --> 00:04:35,840
bila pogreška čitanja iz datoteke, ili
nije mi izbije jer smo postigli

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

83
00:04:37,120 --> 00:04:40,150
Ako je došlo do pogreške, onda želimo
povratak false, jer teret nije

84
00:04:40,150 --> 00:04:43,260
uspjeti, a u tom procesu, želimo
iskrcati sve riječi koje smo čitali

85
00:04:43,260 --> 00:04:45,670
i zatvoriti rječničku datoteku.

86
00:04:45,670 --> 00:04:48,740
Pod pretpostavkom da smo uspjeli, onda mi samo
Još uvijek je potrebno zatvoriti rječnik

87
00:04:48,740 --> 00:04:51,970
podnijeti, i na kraju se vratiti točno jer
smo uspješno ste učita

88
00:04:51,970 --> 00:04:53,040
rječnik.

89
00:04:53,040 --> 00:04:54,420
I to je to za opterećenja.

90
00:04:54,420 --> 00:04:59,020
>> Tako sada provjeriti, obzirom učita hash tablicu,
će izgledati ovako.

91
00:04:59,020 --> 00:05:02,690
Dakle, provjerite, to vraća bool, koji
će se naznačiti je li

92
00:05:02,690 --> 00:05:07,530
prošlo-u char * riječ, je li
prošlo-u niz je u našem rječniku.

93
00:05:07,530 --> 00:05:10,530
Dakle, ako je to u rječniku, ako je to
u našem hash tablicu, mi ćemo se vratiti

94
00:05:10,530 --> 00:05:13,380
istina, a ako to nije,
vratit ćemo se lažna.

95
00:05:13,380 --> 00:05:17,770
S obzirom na to prošli-u riječ, da smo
će hash riječ.

96
00:05:17,770 --> 00:05:22,020
>> Sada, važna stvar je da prepoznaju
da u opterećenju, znali smo da su sve

97
00:05:22,020 --> 00:05:25,820
riječi su idući u biti manji slučaj,
ali ovdje, nismo tako sigurni.

98
00:05:25,820 --> 00:05:29,510
Ako ćemo se pogled na naše hash funkcije,
naš hash funkcija zapravo

99
00:05:29,510 --> 00:05:32,700
je lowercasing svaki lik
od riječi.

100
00:05:32,700 --> 00:05:37,580
Dakle, bez obzira na kapitalizaciju
Riječ, naša hash funkcija će

101
00:05:37,580 --> 00:05:42,270
vratiti istu indeks za sve što
kapitalizacija je kao da će to imati

102
00:05:42,270 --> 00:05:45,280
vratio za potpuno slovu
Verzija od riječi.

103
00:05:45,280 --> 00:05:45,950
U redu.

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

105
00:05:47,410 --> 00:05:49,790
To je hash tablicu za tu riječ.

106
00:05:49,790 --> 00:05:52,940
Sada, to za petlje ide
na više popisa povezan

107
00:05:52,940 --> 00:05:55,000
koji je bio na tom indeksu.

108
00:05:55,000 --> 00:05:59,630
Dakle, primijetit ćemo se inicijalizacije unos
ukazati na taj indeks.

109
00:05:59,630 --> 00:06:03,480
Mi ćemo nastaviti dok ne entry
nije jednak NULL, i sjetite se da

110
00:06:03,480 --> 00:06:08,350
ažuriranje pokazivač na našem popisu povezanom
Ulazak jednako entry-> next, tako da su

111
00:06:08,350 --> 00:06:13,840
Naš trenutni polazna točka za
Sljedeća točka u povezanim popisu.

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

113
00:06:14,400 --> 00:06:19,150
>> Dakle, za svaki unos u popisu povezana,
ćemo koristiti strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Nije strcmp, jer opet, mi
želite učiniti stvari slučaj insensitively.

115
00:06:23,780 --> 00:06:28,830
Dakle, mi koristimo strcasecmp usporediti riječ
koji je donesen na ovu funkciju

116
00:06:28,830 --> 00:06:31,860
protiv riječi koje
je u tom ulasku.

117
00:06:31,860 --> 00:06:35,570
Ako se vrati 0, to znači da je
utakmicu, u kojem slučaju želimo

118
00:06:35,570 --> 00:06:36,630
povratak istina.

119
00:06:36,630 --> 00:06:39,590
Uspješno smo se našli
Riječ u našem hash tablicu.

120
00:06:39,590 --> 00:06:43,040
>> Da nije bilo utakmica, onda smo
ide na petlju i opet pogledati

121
00:06:43,040 --> 00:06:43,990
sljedeći unos.

122
00:06:43,990 --> 00:06:47,640
I mi ćemo nastaviti petlje dok postoji
su upisi u ovom popisu povezana.

123
00:06:47,640 --> 00:06:50,160
Što će se dogoditi ako se lomimo
iz toga za petlje?

124
00:06:50,160 --> 00:06:55,110
To znači da nisu pronašli zapis koji
uskladiti tu riječ, u kojem slučaju

125
00:06:55,110 --> 00:07:00,220
vraćamo lažno ukazuje da je naš
hash tablica ne sadrži tu riječ.

126
00:07:00,220 --> 00:07:01,910
I to je to za provjeru.

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

128
00:07:02,540 --> 00:07:04,790
>> Tako ćemo pogledati veličini.

129
00:07:04,790 --> 00:07:09,280
Sada, veličina će biti prilično jednostavno
jer zapamtite u opterećenjem, za svaku riječ

130
00:07:09,280 --> 00:07:12,880
našli smo mi porastao globalni
promjenjiva hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Tako je funkcija veličine je samo
će se vratiti da je globalno

132
00:07:15,830 --> 00:07:18,150
varijabla, i to je to.

133
00:07:18,150 --> 00:07:22,300
>> Sada napokon, moramo rasteretiti
rječnik odjednom se sve to radi.

134
00:07:22,300 --> 00:07:25,340
Pa kako ćemo to učiniti?

135
00:07:25,340 --> 00:07:30,440
Upravo ovdje, mi smo petlje preko svega
kante našeg hash tablicu.

136
00:07:30,440 --> 00:07:33,240
Dakle, postoje NUM_BUCKETS kante.

137
00:07:33,240 --> 00:07:37,490
A za svaki povezan popisu u našoj mljeveno meso
Stol, idemo na petlji preko

138
00:07:37,490 --> 00:07:41,070
Sveukupna popisu povezanom
oslobađajući svaki element.

139
00:07:41,070 --> 00:07:46,070
Sada, moramo biti oprezni, pa ovdje smo
imaju privremenu varijablu koja je

140
00:07:46,070 --> 00:07:49,740
spremanje pokazivača na sljedećoj
Element u popisu povezane.

141
00:07:49,740 --> 00:07:52,140
A onda ćemo besplatno
trenutna elementa.

142
00:07:52,140 --> 00:07:55,990
>> Moramo biti sigurni da smo to učinili jer smo mi
Ne mogu samo osloboditi trenutne element

143
00:07:55,990 --> 00:07:59,260
a zatim pokušati pristupili sljedećoj pokazivač
jer kad smo ga oslobodili

144
00:07:59,260 --> 00:08:00,870
memorije postaje nevažeći.

145
00:08:00,870 --> 00:08:04,990
Zato nam je potrebno da bi oko pokazivač na
Sljedeći element, onda možemo osloboditi

146
00:08:04,990 --> 00:08:08,360
Trenutna je element, a onda smo se ažurirati
Naš trenutni element ukazuju na

147
00:08:08,360 --> 00:08:09,590
Sljedeći element.

148
00:08:09,590 --> 00:08:12,770
>> Mi ćemo petlju dok postoje elementi
na ovom popisu povezane.

149
00:08:12,770 --> 00:08:16,450
Učinit ćemo to za sve vezane liste u
hash tablicu, a kad smo gotovi

150
00:08:16,450 --> 00:08:20,180
s tim, mi u potpunosti smo iskrcali
hash tablicu, i mi smo gotovi.

151
00:08:20,180 --> 00:08:24,050
Tako da je nemoguće da izbacuje ikada
povratak false, a kad smo gotovi, mi

152
00:08:24,050 --> 00:08:25,320
Samo povratak istina.

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