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
Es esmu Rob, un pieņemsim hash
Šis risinājums out.

4
00:00:16,210 --> 00:00:20,070
Tāpēc šeit mēs ejam, lai īstenotu
Kopumā hash tabulu.

5
00:00:20,070 --> 00:00:24,090
Mēs redzam, ka struktūrai mezgla mūsu hash
tabula gatavojas izskatās šādi.

6
00:00:24,090 --> 00:00:28,710
Tātad, tas notiek, lai būtu char vārds
masīvs izmēra garumu plus 1.

7
00:00:28,710 --> 00:00:32,259
Neaizmirstiet 1 kopš maksimāli
vārdu vārdnīcā ir 45

8
00:00:32,259 --> 00:00:35,110
rakstzīmes, un tad mēs ejam uz
vajag vienu papildus rakstzīmi

9
00:00:35,110 --> 00:00:37,070
slīpsvītru 0.

10
00:00:37,070 --> 00:00:40,870
>> Un tad mūsu hash tabulu katrā
kauss ir gatavojas glabāt

11
00:00:40,870 --> 00:00:42,320
saistīts saraksts mezglu.

12
00:00:42,320 --> 00:00:44,420
Mēs nedarām lineāra zondēšana šeit.

13
00:00:44,420 --> 00:00:48,430
Un tāpēc, lai saite uz nākamā
elements spainī, mums ir nepieciešams

14
00:00:48,430 --> 00:00:51,110
struct mezglā * nākamo.

15
00:00:51,110 --> 00:00:53,090
Tātad, tas ir tas, ko mezglā izskatās.

16
00:00:53,090 --> 00:00:56,180
Tagad šeit ir deklarācija
mūsu hash tabulu.

17
00:00:56,180 --> 00:01:01,910
Tas nāksies 16384 kausi, bet
šis numurs nav īsti jautājums.

18
00:01:01,910 --> 00:01:05,450
Un visbeidzot, mēs esam nāksies
globālo mainīgo hashtable_size, kas

19
00:01:05,450 --> 00:01:08,640
gatavojas sākt ar 0, un tas ir
būs izsekot, cik daudz vārdu

20
00:01:08,640 --> 00:01:10,080
bija mūsu vārdnīcā.

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

22
00:01:10,760 --> 00:01:13,190
>> Tātad, pieņemsim to apskatīt slodzes.

23
00:01:13,190 --> 00:01:16,390
Tāpēc ievērosiet, ka slodze,
tā atgriež bool.

24
00:01:16,390 --> 00:01:20,530
Jūs atgrieztos taisnība, ja tas bija veiksmīgi
piekrauts un viltus citādi.

25
00:01:20,530 --> 00:01:23,990
Un tas notiek const char * zvaigzne
vārdnīcā, kas ir vārdnīcā

26
00:01:23,990 --> 00:01:25,280
ka mēs vēlamies, lai atvērtu.

27
00:01:25,280 --> 00:01:27,170
Tā ka ir pirmā lieta,
mēs gatavojamies darīt.

28
00:01:27,170 --> 00:01:30,420
Mēs ejam, lai fopen vārdnīcu, lai
lasījumā, un mēs esam nāksies

29
00:01:30,420 --> 00:01:34,700
lai pārliecinātos, ka tas ir izdevies, tādēļ, ja
tas atgriezās NULL, tad mēs neesam

30
00:01:34,700 --> 00:01:37,440
veiksmīgi atvērt vārdnīcu
un mums ir nepieciešams, lai atgrieztos nepatiesa.

31
00:01:37,440 --> 00:01:41,580
>> Bet, pieņemot, ka tā veiksmīgi
atvērt, tad mēs vēlamies, lai izlasītu

32
00:01:41,580 --> 00:01:42,400
vārdnīca.

33
00:01:42,400 --> 00:01:46,210
Lai saglabātu looping kamēr mēs atrodam kādu
iemesls, lai izkļūt no šīs

34
00:01:46,210 --> 00:01:47,570
cilpa, ko mēs redzēsim.

35
00:01:47,570 --> 00:01:51,780
Tāpēc saglabājiet looping, un tagad mēs ejam
lai malloc vienu mezglu.

36
00:01:51,780 --> 00:01:56,800
Un, protams, mums ir nepieciešams, lai kļūdu pārbaude
vēlreiz, tāpēc, ja mallocing neizdevās

37
00:01:56,800 --> 00:02:00,660
, un mēs vēlamies, lai izkrautu jebkuru mezglu, ko mēs
notika ar malloc pirms slēgt

38
00:02:00,660 --> 00:02:02,590
vārdnīcu un atgriezties viltus.

39
00:02:02,590 --> 00:02:07,440
>> Bet ignorējot, ka, pieņemot, ka mēs
izdevies, tad mēs vēlamies izmantot fscanf

40
00:02:07,440 --> 00:02:12,400
lasīt vienu vārdu no mūsu
vārdnīca mūsu mezglā.

41
00:02:12,400 --> 00:02:17,310
Tātad, atcerieties, ka ieejas-> vārds ir char
vārdu bufera izmēra garumu plus

42
00:02:17,310 --> 00:02:20,300
viens, ka mēs ejam
uzglabāt vārdu iekšā

43
00:02:20,300 --> 00:02:25,280
Tāpēc fscanf gatavojas atgriezties 1 tik ilgi
jo tas varēja veiksmīgi nolasīt

44
00:02:25,280 --> 00:02:26,750
vārdu no lietas materiāliem.

45
00:02:26,750 --> 00:02:31,030
>> Ja nu kļūda notiek, vai mēs sasniegsim
faila beigas, tas nav

46
00:02:31,030 --> 00:02:34,950
return 1 tādā gadījumā, ja tā nav
atgriezties 1, mēs beidzot gatavojas lauzt

47
00:02:34,950 --> 00:02:37,280
no šīs kamēr cilpa.

48
00:02:37,280 --> 00:02:42,770
Tātad mēs redzam, ka tad, kad mēs esam veiksmīgi
lasīt vārdu uz

49
00:02:42,770 --> 00:02:48,270
Ierakstu-> vārdu, tad mēs ejam uz hash
šis vārds, izmantojot mūsu hash funkciju.

50
00:02:48,270 --> 00:02:49,580
Pieņemsim to apskatīt
hash funkciju.

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

52
00:02:52,430 --> 00:02:55,610
>> Tātad jums nav tiešām ir nepieciešams
saprast.

53
00:02:55,610 --> 00:02:59,460
Un patiesībā, mēs vienkārši velk to
hash funkciju no interneta.

54
00:02:59,460 --> 00:03:04,010
Vienīgais, kas jums ir nepieciešams atzīt,
ka tas aizņem const char * vārdu,

55
00:03:04,010 --> 00:03:08,960
tāpēc tas ir ņemot virkni kā priekšnodokli un
atgriešanās neparakstītu int kā produkciju.

56
00:03:08,960 --> 00:03:12,360
Tātad tas viss hash funkciju, tas ir
uzņem ieejas, tas dod jums

57
00:03:12,360 --> 00:03:14,490
indekss par hash tabulu.

58
00:03:14,490 --> 00:03:18,530
Ievērojiet, ka mēs esam modding ar NUM_BUCKETS
tāpēc hash vērtība atgriezās

59
00:03:18,530 --> 00:03:21,730
patiesībā ir rādītājs uz hash tabulu
un nav rādītājs pārsniedz

60
00:03:21,730 --> 00:03:24,320
robežas no masīva.

61
00:03:24,320 --> 00:03:27,855
>> Tāpēc, ka hash funkciju, mēs ejam
hash vārdu, ka mēs lasām

62
00:03:27,855 --> 00:03:31,700
No vārdnīcas, un tad mēs ejam
izmantot, kas ir, lai ievietotu

63
00:03:31,700 --> 00:03:33,750
stāšanās hash tabulu.

64
00:03:33,750 --> 00:03:38,830
Tagad, Hashtable hash ir pašreizējā
saistīts saraksts hash tabulā, un

65
00:03:38,830 --> 00:03:41,410
tas ir ļoti iespējams, ka ir tikai NULL.

66
00:03:41,410 --> 00:03:45,640
Mēs vēlamies, lai ievietotu savu ienākšanu
sākot no šīs saistīta saraksta, un tā

67
00:03:45,640 --> 00:03:48,910
Mēs ejam, lai būtu mūsu pašreizējo ierakstu
norāda uz to, ko hash tabulā šobrīd

68
00:03:48,910 --> 00:03:54,030
punkti, un tad mēs ejam, lai saglabātu
hash tabulu, hash

69
00:03:54,030 --> 00:03:55,350
pašreizējais ieraksts.

70
00:03:55,350 --> 00:03:59,320
>> Tātad šīs divas līnijas veiksmīgi ievietot
ieraksts sākumā

71
00:03:59,320 --> 00:04:02,270
saistīts saraksts šajā indeksā
hash tabulā.

72
00:04:02,270 --> 00:04:04,900
Pēc tam, kad mēs esam darīts ar to, ka mēs zinām,
ka mēs atradām vēl vienu vārdu

73
00:04:04,900 --> 00:04:07,800
vārdnīcu un mēs solis vēlreiz.

74
00:04:07,800 --> 00:04:13,960
Tāpēc mēs turpinām darām līdz fscanf
beidzot atgriežas kaut kas nav 1 pie

75
00:04:13,960 --> 00:04:18,560
Kurā brīdī atcerēties, ka mums ir nepieciešams, lai
bezmaksas ieeja, tāpēc šeit mēs malloced

76
00:04:18,560 --> 00:04:21,329
ierakstu, un mēs mēģinājām lasīt kaut ko
no vārdnīcas.

77
00:04:21,329 --> 00:04:24,110
Un mēs neesam veiksmīgi nolasīt
kaut kas no vārdnīcas, kurā

78
00:04:24,110 --> 00:04:27,440
gadījumā mums ir nepieciešams, lai atbrīvotu ierakstu, ka mēs
nekad faktiski laisti hash tabulu

79
00:04:27,440 --> 00:04:29,110
un beidzot pauze.

80
00:04:29,110 --> 00:04:32,750
>> Kad mēs izcelties, mums ir nepieciešams, lai redzētu, labi,
mēs esam izcelties, jo tur

81
00:04:32,750 --> 00:04:35,840
bija kļūda lasot no lietas materiāliem, vai
mēs esam izcelties, jo mēs nonācām

82
00:04:35,840 --> 00:04:37,120
faila beigas?

83
00:04:37,120 --> 00:04:40,150
Ja tur bija kļūda, tad mēs vēlamies
atgriezties viltus jo slodze nebija

84
00:04:40,150 --> 00:04:43,260
panākumus, un šajā procesā, mēs vēlamies
izkraut visus vārdus, ka mēs lasām

85
00:04:43,260 --> 00:04:45,670
iekšā un aizveriet vārdnīcas faila.

86
00:04:45,670 --> 00:04:48,740
Pieņemot, ka mums izdosies, tad mēs vienkārši
joprojām ir nepieciešams, lai aizvērtu vārdnīcu

87
00:04:48,740 --> 00:04:51,970
failu, un visbeidzot atgriezties taisnība, jo
mēs esam veiksmīgi ielādēta

88
00:04:51,970 --> 00:04:53,040
vārdnīca.

89
00:04:53,040 --> 00:04:54,420
Un tas ir tas, lai slodze.

90
00:04:54,420 --> 00:04:59,020
>> Tāpēc tagad pārbaudiet, ņemot piekrauts hash tabulu,
gatavojas izskatās šādi.

91
00:04:59,020 --> 00:05:02,690
Lai pārbaudītu, tas atgriež bool, kas
gatavojas, lai norādītu, vai

92
00:05:02,690 --> 00:05:07,530
pagājis-in char * vārdu, vai
pagājis-in virkne ir mūsu vārdnīcā.

93
00:05:07,530 --> 00:05:10,530
Tātad, ja tas ir norādīts vārdnīcā, ja tas ir
mūsu hash tabulu, mēs atgriezīsimies

94
00:05:10,530 --> 00:05:13,380
taisnība, un, ja tā nav,
mēs atgriezīsimies nepatiesa.

95
00:05:13,380 --> 00:05:17,770
Ņemot vērā šo pagājis-in vārdu, mēs esam
gatavojas hash vārdu.

96
00:05:17,770 --> 00:05:22,020
>> Tagad svarīga lieta atzīt,
ka slodzes, zinājām, ka visi

97
00:05:22,020 --> 00:05:25,820
vārdi bija būs mazie burti,
bet šeit, mēs neesam tik pārliecināts.

98
00:05:25,820 --> 00:05:29,510
Ja mēs to apskatīt mūsu hash funkciju,
mūsu hash funkcija faktiski

99
00:05:29,510 --> 00:05:32,700
ir lowercasing katru rakstzīmi
vārda.

100
00:05:32,700 --> 00:05:37,580
Tāpēc neatkarīgi no kapitalizācijas
Vārds, mūsu hash funkcija būs

101
00:05:37,580 --> 00:05:42,270
atpakaļ to pašu indeksu neatkarīgi
kapitalizācija ir tā, kā būtu

102
00:05:42,270 --> 00:05:45,280
atpakaļ uz pavisam mazie burti
versija vārda.

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

104
00:05:45,950 --> 00:05:47,410
>> Tātad tas ir mūsu indeksa.

105
00:05:47,410 --> 00:05:49,790
Tas ir hash tabulu par šo vārdu.

106
00:05:49,790 --> 00:05:52,940
Tagad šis cilpa notiek
lai pār to saistīts saraksts

107
00:05:52,940 --> 00:05:55,000
tas bija šajā indeksā.

108
00:05:55,000 --> 00:05:59,630
Tāpēc paziņojums mums ir inicializēta ierakstu
, lai norādītu uz minētā indeksa.

109
00:05:59,630 --> 00:06:03,480
Mēs turpināsim, bet ieraksts nav
nav vienāds NULL, un atcerieties, ka

110
00:06:03,480 --> 00:06:08,350
atjauninot rādītāju mūsu saistīts sarakstā
ieraksts ir vienāds ieraksts-> blakus, tāpēc ir

111
00:06:08,350 --> 00:06:13,840
Mūsu pašreizējais sākumpunkts
Nākamais punkts saistītajā sarakstā.

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

113
00:06:14,400 --> 00:06:19,150
>> Tātad uz katru ierakstu saistītajā sarakstā,
mēs ejam, lai izmantotu strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Tas nav strcmp jo atkal mēs
gribu darīt lietas lietu insensitively.

115
00:06:23,780 --> 00:06:28,830
Tāpēc mēs izmantojam strcasecmp salīdzināt vārdu
, kas tika pieņemts, lai šo funkciju

116
00:06:28,830 --> 00:06:31,860
pret vārdu, kas
ir šajā ierakstā.

117
00:06:31,860 --> 00:06:35,570
Ja tas atgriež 0, tas nozīmē, ka tur bija
spēles, un tādā gadījumā mēs vēlamies

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

119
00:06:36,630 --> 00:06:39,590
Mēs veiksmīgi atraduši
vārdu mūsu hash tabulā.

120
00:06:39,590 --> 00:06:43,040
>> Ja nebija spēle, tad mēs esam
dodas uz cilpu atkal un apskatīt

121
00:06:43,040 --> 00:06:43,990
Nākamais ieraksts.

122
00:06:43,990 --> 00:06:47,640
Un mēs turpināsim looping, bet tur
Ir ieraksti šajā saistīta sarakstā.

123
00:06:47,640 --> 00:06:50,160
Kas notiek, ja mēs pārkāpjam
no šīs cilpa?

124
00:06:50,160 --> 00:06:55,110
Tas nozīmē, ka mēs neesam atrast ierakstu, kas
saskaņota šo vārdu, tādā gadījumā

125
00:06:55,110 --> 00:07:00,220
mēs atgriežamies viltus, lai norādītu, ka mūsu
hash tabulu neietvēra šo vārdu.

126
00:07:00,220 --> 00:07:01,910
Un tas ir tas, lai pārbaudi.

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

128
00:07:02,540 --> 00:07:04,790
>> Tātad, pieņemsim to apskatīt lieluma.

129
00:07:04,790 --> 00:07:09,280
Tagad lielums būs diezgan vienkāršs
jo atceros, slodzes, katram vārdam

130
00:07:09,280 --> 00:07:12,880
mēs noskaidrojām, mēs palielina globālās
mainīgais hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Tā lielums funkcija ir tikai
gatavojas atgriezties, ka globālās

132
00:07:15,830 --> 00:07:18,150
mainīgs, un tas arī viss.

133
00:07:18,150 --> 00:07:22,300
>> Beidzot, mums ir nepieciešams, lai izkrautu
vārdnīca, kad viss ir izdarīts.

134
00:07:22,300 --> 00:07:25,340
Tātad, kā mēs gatavojamies darīt?

135
00:07:25,340 --> 00:07:30,440
Tieši šeit, mēs esam looping visā
spaiņi mūsu hash tabulu.

136
00:07:30,440 --> 00:07:33,240
Tāpēc ir NUM_BUCKETS kausi.

137
00:07:33,240 --> 00:07:37,490
Un katram, kas saistīta saraksta mūsu hash
galda, mēs ejam, lai cilpa pār

138
00:07:37,490 --> 00:07:41,070
veselums saistītā saraksta
atbrīvojot katru elementu.

139
00:07:41,070 --> 00:07:46,070
Tagad, mums ir jābūt uzmanīgiem, tāpēc šeit mēs
ir pagaidu mainīgo, kas ir

140
00:07:46,070 --> 00:07:49,740
uzglabāšanas rādītāju uz nākamā
elements saistītajā sarakstā.

141
00:07:49,740 --> 00:07:52,140
Un tad mēs ejam uz brīvu
pašreizējais elements.

142
00:07:52,140 --> 00:07:55,990
>> Mums ir nepieciešams, lai pārliecinātos, mēs to darām, jo ​​mēs
var ne tikai brīvi Pašlaik skatītās elements

143
00:07:55,990 --> 00:07:59,260
un tad mēģināt piekļūtu nākamajai rādītāju
jo, kad mēs atbrīvojušies to

144
00:07:59,260 --> 00:08:00,870
atmiņa kļūst nederīgs.

145
00:08:00,870 --> 00:08:04,990
Tāpēc mums ir nepieciešams, lai saglabātu apmēram rādītāju uz
nākamais elements, tad mēs varam brīvi

146
00:08:04,990 --> 00:08:08,360
strāvas elements, un pēc tam, mēs var atjaunināt
Mūsu pašreizējais elements, lai norādītu

147
00:08:08,360 --> 00:08:09,590
nākamais elements.

148
00:08:09,590 --> 00:08:12,770
>> Mēs cilpas, bet tur ir elementi
Šajā saistīts sarakstā.

149
00:08:12,770 --> 00:08:16,450
Mēs darīsim, ka visiem, kas saistīti sarakstos
hash tabulu, un pēc tam, kad mēs esam darījuši

150
00:08:16,450 --> 00:08:20,180
ar to, ka mēs esam pilnīgi izkrauts
hash tabulu, un mēs esam darījuši.

151
00:08:20,180 --> 00:08:24,050
Tātad, tas ir neiespējami izkrauj kādreiz
atgriezties viltus, un, kad mēs esam darīts, mēs

152
00:08:24,050 --> 00:08:25,320
vienkārši atgriezties true.

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