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

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

3
00:00:13,050 --> 00:00:16,210
Jeg er Rob, og lad os hash
denne løsning.

4
00:00:16,210 --> 00:00:20,070
Så her vi kommer til at gennemføre
en generel hash tabel.

5
00:00:20,070 --> 00:00:24,090
Vi ser, at struct node i vores hash
Tabellen kommer til at se sådan ud.

6
00:00:24,090 --> 00:00:28,710
Så det kommer til at have en char ord
vifte af størrelse længde plus 1.

7
00:00:28,710 --> 00:00:32,259
Glem ikke 1, da den maksimale
ord i ordbogen er 45

8
00:00:32,259 --> 00:00:35,110
tegn, og så vil vi
har brug for en ekstra karakter for

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

10
00:00:37,070 --> 00:00:40,870
>> Og så er vores hash tabel i hver
spand vil gemme en

11
00:00:40,870 --> 00:00:42,320
forbundet nodeliste.

12
00:00:42,320 --> 00:00:44,420
Vi laver ikke lineær probing her.

13
00:00:44,420 --> 00:00:48,430
Og så for at linke til den næste
element i spanden, vi har brug for en

14
00:00:48,430 --> 00:00:51,110
struct node * næste.

15
00:00:51,110 --> 00:00:53,090
Så det er hvad en knude ser ud.

16
00:00:53,090 --> 00:00:56,180
Nu, her er den erklæring
vores hash tabellen.

17
00:00:56,180 --> 00:01:01,910
Det kommer til at have 16.384 spande, men
dette nummer er faktisk ligegyldigt.

18
00:01:01,910 --> 00:01:05,450
Og endelig, vi kommer til at have den
global variabel hashtable_size, som

19
00:01:05,450 --> 00:01:08,640
kommer til at starte som 0, og det er
kommer til at holde styr på, hvor mange ord

20
00:01:08,640 --> 00:01:10,080
var i vores ordbog.

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

22
00:01:10,760 --> 00:01:13,190
>> Så lad os tage et kig på belastning.

23
00:01:13,190 --> 00:01:16,390
Så bemærke, at last,
den returnerer en bool.

24
00:01:16,390 --> 00:01:20,530
Du vender tilbage sandt, hvis det var lykkedes
lastet og falsk ellers.

25
00:01:20,530 --> 00:01:23,990
Og det tager en const char * stjerne
ordbog, som ordbogen

26
00:01:23,990 --> 00:01:25,280
at vi ønsker at åbne.

27
00:01:25,280 --> 00:01:27,170
Så det er den første ting
vi kommer til at gøre.

28
00:01:27,170 --> 00:01:30,420
Vi kommer til at fopen ordbogen for
læsning, og vi er nødt til

29
00:01:30,420 --> 00:01:34,700
at sørge for, at det lykkedes så hvis
det returnerede NULL, så vi ikke gjorde

30
00:01:34,700 --> 00:01:37,440
held åbne ordbogen
og vi er nødt til at returnere falsk.

31
00:01:37,440 --> 00:01:41,580
>> Men det antages, at den gjorde med succes
åben, så vi ønsker at læse

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

33
00:01:42,400 --> 00:01:46,210
Så hold looping indtil vi finder nogle
grund til at bryde ud af denne

34
00:01:46,210 --> 00:01:47,570
løkke, som vi vil se.

35
00:01:47,570 --> 00:01:51,780
Så holde looping, og nu skal vi
at allokere en enkelt node.

36
00:01:51,780 --> 00:01:56,800
Og selvfølgelig er vi nødt til fejl kontrol
igen, så hvis mallocing ikke lykkedes

37
00:01:56,800 --> 00:02:00,660
og vi ønsker at losse enhver knude, som vi
sket med malloc før, lukke

38
00:02:00,660 --> 00:02:02,590
ordbog og returnere falsk.

39
00:02:02,590 --> 00:02:07,440
>> Men at ignorere det, antager vi
lykkedes, så vi ønsker at bruge fscanf

40
00:02:07,440 --> 00:02:12,400
at læse et enkelt ord fra vores
ordbogen til vores knude.

41
00:02:12,400 --> 00:02:17,310
Så husk, at entry-> Ordet er char
ord buffer størrelse længde plus

42
00:02:17,310 --> 00:02:20,300
en, som vi kommer til at
gemme ord i.

43
00:02:20,300 --> 00:02:25,280
Så fscanf kommer til at returnere 1, så længe
som det var i stand til at læse en

44
00:02:25,280 --> 00:02:26,750
ord fra filen.

45
00:02:26,750 --> 00:02:31,030
>> Hvis enten en fejl sker, eller vi nå
slutningen af ​​filen, vil det ikke

46
00:02:31,030 --> 00:02:34,950
returnere 1, i hvilket tilfælde, hvis den ikke gør det
returnere 1, vi endelig kommer til at bryde

47
00:02:34,950 --> 00:02:37,280
ud af dette, mens løkken.

48
00:02:37,280 --> 00:02:42,770
Så vi kan se, at når vi har med succes
læse et ord i

49
00:02:42,770 --> 00:02:48,270
entry-> ord, så vi kommer til at hash
at ordet ved hjælp af vores hash funktion.

50
00:02:48,270 --> 00:02:49,580
Lad os tage et kig på
hash-funktionen.

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

52
00:02:52,430 --> 00:02:55,610
>> Så du behøver ikke virkelig har brug for
at forstå dette.

53
00:02:55,610 --> 00:02:59,460
Og faktisk, vi bare trak dette
hash funktion fra internettet.

54
00:02:59,460 --> 00:03:04,010
Det eneste, du skal erkende, er
at det tager en const char * ord,

55
00:03:04,010 --> 00:03:08,960
så det tager en streng som input og
returnere en usigneret int som output.

56
00:03:08,960 --> 00:03:12,360
Så det hele er en hash-funktion er, er det
tager i et input, det giver dig en

57
00:03:12,360 --> 00:03:14,490
indekset i hash tabellen.

58
00:03:14,490 --> 00:03:18,530
Bemærk, at vi er modding af NUM_BUCKETS
så den hash værdi, der returneres

59
00:03:18,530 --> 00:03:21,730
faktisk er et indeks i hash tabellen
og indekserer ikke ud over

60
00:03:21,730 --> 00:03:24,320
grænserne for array.

61
00:03:24,320 --> 00:03:27,855
>> Så da hash funktion, vi kommer
at hash det ord, vi læser

62
00:03:27,855 --> 00:03:31,700
fra ordbogen og så vil vi
at bruge, der har at indsætte

63
00:03:31,700 --> 00:03:33,750
indrejse i hash tabellen.

64
00:03:33,750 --> 00:03:38,830
Nu Hashtable hash er den aktuelle
linkede liste i hash tabellen, og

65
00:03:38,830 --> 00:03:41,410
det er meget muligt, at er bare NULL.

66
00:03:41,410 --> 00:03:45,640
Vi ønsker at indsætte vores indtræden på det
begyndelsen af ​​denne linkede liste, og så

67
00:03:45,640 --> 00:03:48,910
vi vil have vores aktuelle post
pege på, hvad hash tabellen i øjeblikket

68
00:03:48,910 --> 00:03:54,030
point til og så vi kommer til at gemme
i hash tabellen på hash

69
00:03:54,030 --> 00:03:55,350
den aktuelle indtastning.

70
00:03:55,350 --> 00:03:59,320
>> Så disse to linjer held indsætte
posten i begyndelsen af

71
00:03:59,320 --> 00:04:02,270
forbundet listen på det pågældende indeks
i hash tabellen.

72
00:04:02,270 --> 00:04:04,900
Når vi er færdig med det, vi kender
at vi fandt et andet ord i

73
00:04:04,900 --> 00:04:07,800
ordbog og vi tilvækst igen.

74
00:04:07,800 --> 00:04:13,960
Så vi holde gør, at indtil fscanf
Endelig returnerer noget ikke 1 ved

75
00:04:13,960 --> 00:04:18,560
hvilket punkt huske, at vi er nødt til
gratis adgang, så op her, vi malloced en

76
00:04:18,560 --> 00:04:21,329
indrejse og vi forsøgte at læse noget
fra ordbogen.

77
00:04:21,329 --> 00:04:24,110
Og vi havde ikke held læst
noget fra ordbogen, hvor

78
00:04:24,110 --> 00:04:27,440
tilfælde har vi brug for at frigøre den post, vi
faktisk aldrig sat i hash tabellen

79
00:04:27,440 --> 00:04:29,110
og endelig at bryde.

80
00:04:29,110 --> 00:04:32,750
>> Når vi bryder ud, er vi nødt til at se, ja,
vi bryde ud, fordi der

81
00:04:32,750 --> 00:04:35,840
var en fejl ved læsning fra filen, eller
vi bryder ud, fordi vi nåede

82
00:04:35,840 --> 00:04:37,120
slutningen af ​​fil?

83
00:04:37,120 --> 00:04:40,150
Hvis der var en fejl, da vi ønsker at
return false fordi belastningen ikke

84
00:04:40,150 --> 00:04:43,260
lykkes, og i den proces, vi ønsker at
losse alle de ord, som vi læser

85
00:04:43,260 --> 00:04:45,670
ind og lukke ordbogen fil.

86
00:04:45,670 --> 00:04:48,740
Hvis man antager, vi lykkes, så vi bare
stadig nødt til at lukke ordbogen

87
00:04:48,740 --> 00:04:51,970
fil, og endelig returnere sandt, da
vi har indlæst

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

89
00:04:53,040 --> 00:04:54,420
Og det er det for belastning.

90
00:04:54,420 --> 00:04:59,020
>> Så nu kontrollere, givet en ladt hash tabel,
kommer til at se sådan ud.

91
00:04:59,020 --> 00:05:02,690
Så tjek det returnerer en bool, der
kommer til at angive, om

92
00:05:02,690 --> 00:05:07,530
passerede-in char * ord, hvorvidt den
passerede-i streng er i vores ordbog.

93
00:05:07,530 --> 00:05:10,530
Så hvis det er i ordbogen, hvis det er
i vores hash tabel, vi vil vende tilbage

94
00:05:10,530 --> 00:05:13,380
sandt, og hvis det ikke er,
vi vil vende tilbage falsk.

95
00:05:13,380 --> 00:05:17,770
I betragtning af denne passerede-i ord, er vi
kommer til hash ordet.

96
00:05:17,770 --> 00:05:22,020
>> Nu, en vigtig ting at erkende, er
at i lasten, vidste vi, at alle

97
00:05:22,020 --> 00:05:25,820
de ord, skulle være lavere fald
men her er vi ikke så sikker.

98
00:05:25,820 --> 00:05:29,510
Hvis vi tager et kig på vores hash funktion,
vores hash-funktionen faktisk

99
00:05:29,510 --> 00:05:32,700
er lowercasing hver karakter
af ordet.

100
00:05:32,700 --> 00:05:37,580
Så uanset kapitalisering af
ord, er vores hash funktion, der går til

101
00:05:37,580 --> 00:05:42,270
returnere det samme indeks for uanset
kapitalisering er som det ville have

102
00:05:42,270 --> 00:05:45,280
vendt tilbage til en helt små bogstaver
version af ord.

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

104
00:05:45,950 --> 00:05:47,410
>> Så det er vores indeks.

105
00:05:47,410 --> 00:05:49,790
Det er hash tabellen for dette ord.

106
00:05:49,790 --> 00:05:52,940
Nu, dette for-løkke går
til over den linkede liste

107
00:05:52,940 --> 00:05:55,000
der var på dette indeks.

108
00:05:55,000 --> 00:05:59,630
Så opdager vi initialiseres indgang
at pege på dette indeks.

109
00:05:59,630 --> 00:06:03,480
Vi kommer til at fortsætte, mens indgang gør
ikke lig NULL, og husk, at

110
00:06:03,480 --> 00:06:08,350
opdatering af markøren i vores linkede liste
entry lig entry-> næste, så har

111
00:06:08,350 --> 00:06:13,840
vores nuværende indgang til
Næste punkt på linkede liste.

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

113
00:06:14,400 --> 00:06:19,150
>> Så for hver post i den linkede liste,
vi kommer til at bruge strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Det er ikke strcmp fordi vi endnu en gang
ønsker at gøre tingene tilfælde ufølsomt.

115
00:06:23,780 --> 00:06:28,830
Så vi bruger strcasecmp at sammenligne ordet
som blev overført til denne funktion

116
00:06:28,830 --> 00:06:31,860
imod det ord,
er i denne post.

117
00:06:31,860 --> 00:06:35,570
Hvis den returnerer 0, som betyder, at der var
en kamp, ​​i hvilket tilfælde vil vi

118
00:06:35,570 --> 00:06:36,630
returnere sandt.

119
00:06:36,630 --> 00:06:39,590
Vi har med held fundet
ord i vores hash tabel.

120
00:06:39,590 --> 00:06:43,040
>> Hvis der ikke var en kamp, ​​så er vi
gå til loop igen og se på

121
00:06:43,040 --> 00:06:43,990
næste post.

122
00:06:43,990 --> 00:06:47,640
Og vi vil fortsætte looping mens der
er poster i denne linkede liste.

123
00:06:47,640 --> 00:06:50,160
Hvad sker der, hvis vi bryder
ud af denne for-løkke?

124
00:06:50,160 --> 00:06:55,110
Det betyder, at vi ikke finde en post, der
matches dette ord, i hvilket tilfælde

125
00:06:55,110 --> 00:07:00,220
vi vender tilbage falsk for at angive, at vores
hash tabel ikke indeholder dette ord.

126
00:07:00,220 --> 00:07:01,910
Og det er det for check.

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

128
00:07:02,540 --> 00:07:04,790
>> Så lad os tage et kig på størrelse.

129
00:07:04,790 --> 00:07:09,280
Nu størrelse kommer til at være temmelig simpel
da huske i belastning, for hvert ord

130
00:07:09,280 --> 00:07:12,880
vi fandt vi øges en global
variabel hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Så størrelsen funktion er kun
vil vende tilbage, at den globale

132
00:07:15,830 --> 00:07:18,150
variabel, og det er det.

133
00:07:18,150 --> 00:07:22,300
>> Nu endelig er vi nødt til at losse
ordbog når alt er gjort.

134
00:07:22,300 --> 00:07:25,340
Så hvordan skal vi gøre det?

135
00:07:25,340 --> 00:07:30,440
Lige her, vi springer over alle
spande af vores hash tabel.

136
00:07:30,440 --> 00:07:33,240
Så der er NUM_BUCKETS spande.

137
00:07:33,240 --> 00:07:37,490
Og for hver linkede liste i vores hash
tabel, vi kommer til at sløjfe over

138
00:07:37,490 --> 00:07:41,070
hele den linkede liste
frigøre hvert element.

139
00:07:41,070 --> 00:07:46,070
Nu er vi nødt til at være forsigtig, så her vi
have en midlertidig variabel, der er

140
00:07:46,070 --> 00:07:49,740
lagring markøren til den næste
element i den linkede liste.

141
00:07:49,740 --> 00:07:52,140
Og så vil vi fri
det aktuelle element.

142
00:07:52,140 --> 00:07:55,990
>> Vi er nødt til at være sikker på, vi gør dette, da vi
kan ikke bare frigøre det aktuelle element

143
00:07:55,990 --> 00:07:59,260
og derefter prøve at gå til det næste pointer
siden når vi befriede det

144
00:07:59,260 --> 00:08:00,870
hukommelse bliver ugyldig.

145
00:08:00,870 --> 00:08:04,990
Så vi nødt til at holde omkring en pegepind til
det næste element, så vi kan frigøre

146
00:08:04,990 --> 00:08:08,360
aktuelle element, og så vi kan opdatere
vores aktuelle element til at pege på

147
00:08:08,360 --> 00:08:09,590
det næste element.

148
00:08:09,590 --> 00:08:12,770
>> Vi vil sløjfe, mens der er elementer
i denne linkede liste.

149
00:08:12,770 --> 00:08:16,450
Vi vil gøre det for alle sammenkædede lister
hash tabellen, og når vi er færdig

150
00:08:16,450 --> 00:08:20,180
med det, har vi helt losses
hash tabellen, og vi er færdige.

151
00:08:20,180 --> 00:08:24,050
Så det er umuligt for losser til nogensinde
returnere falsk, og når vi er færdige, vi

152
00:08:24,050 --> 00:08:25,320
bare returnere sandt.

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