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

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

3
00:00:13,050 --> 00:00:16,210
Jeg er Rob, og la oss hash
denne løsningen ut.

4
00:00:16,210 --> 00:00:20,070
Så her kommer vi til å implementere
en generell hash table.

5
00:00:20,070 --> 00:00:24,090
Vi ser at struct node av vår hash
tabellen kommer til å se slik ut.

6
00:00:24,090 --> 00:00:28,710
Så det kommer til å ha en char ord
matrise av størrelse lengde pluss en.

7
00:00:28,710 --> 00:00:32,259
Ikke glem en siden den maksimale
ord i ordlisten er 45

8
00:00:32,259 --> 00:00:35,110
tegn, og da vi kommer til å
trenger en ekstra karakter for den

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

10
00:00:37,070 --> 00:00:40,870
>> Og da er vår hash table i hvert
bøtte kommer til å lagre en

11
00:00:40,870 --> 00:00:42,320
lenket liste av noder.

12
00:00:42,320 --> 00:00:44,420
Vi gjør ikke lineær sondering her.

13
00:00:44,420 --> 00:00:48,430
Og så for å koble til den neste
element i bøtta, trenger vi en

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

15
00:00:51,110 --> 00:00:53,090
Så det er hva en node ser ut.

16
00:00:53,090 --> 00:00:56,180
Nå, her er erklæringen
av vår hash table.

17
00:00:56,180 --> 00:01:01,910
Det kommer til å ha 16 384 bøtter, men
at antall spiller egentlig ingen rolle.

18
00:01:01,910 --> 00:01:05,450
Og til slutt, kommer vi til å ha den
global variabel hashtable_size, som

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

20
00:01:08,640 --> 00:01:10,080
var i vår ordbok.

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

22
00:01:10,760 --> 00:01:13,190
>> Så la oss ta en titt på lasten.

23
00:01:13,190 --> 00:01:16,390
Så merker at lasten,
den returnerer en bool.

24
00:01:16,390 --> 00:01:20,530
Du return true hvis det var vellykket
lastet og falsk ellers.

25
00:01:20,530 --> 00:01:23,990
Og det tar en const char * stjerners
ordboken, som er ordboken

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

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

28
00:01:27,170 --> 00:01:30,420
Vi kommer til å FÅpne ordboken for
lesing, og vi kommer til å ha

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

30
00:01:34,700 --> 00:01:37,440
hell åpne ordboken
og vi trenger å returnere false.

31
00:01:37,440 --> 00:01:41,580
>> Men forutsatt at det gjorde med hell
åpen, så vi ønsker å lese

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

33
00:01:42,400 --> 00:01:46,210
Så hold looping til vi finner noen
Grunnen til å bryte ut av denne

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

35
00:01:47,570 --> 00:01:51,780
Så hold looping, og nå skal vi
til malloc en enkelt node.

36
00:01:51,780 --> 00:01:56,800
Og selvfølgelig, må vi feil sjekk
igjen så hvis mallocing ikke lykkes

37
00:01:56,800 --> 00:02:00,660
og vi ønsker å losse noen node som vi
skjedde med malloc før, lukker

38
00:02:00,660 --> 00:02:02,590
ordbok og return false.

39
00:02:02,590 --> 00:02:07,440
>> Men ignorerer det, forutsatt at vi
lyktes, da vi ønsker å bruke fscanf

40
00:02:07,440 --> 00:02:12,400
å lese et eneste ord fra vår
ordlisten, i vår node.

41
00:02:12,400 --> 00:02:17,310
Så husk at entry-> Ordet er røye
Ordet buffer størrelse lengde pluss

42
00:02:17,310 --> 00:02:20,300
en som vi kommer til å
lagre ordet i.

43
00:02:20,300 --> 00:02:25,280
Så fscanf kommer til å returnere en så lang
som det var i stand til å lese 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 feil skjer eller vi nå
slutten av filen, vil det ikke

46
00:02:31,030 --> 00:02:34,950
returnere en i hvilket tilfelle dersom det ikke skjer
returnere en, vi endelig kommer til å bryte

47
00:02:34,950 --> 00:02:37,280
ut av denne, mens sløyfen.

48
00:02:37,280 --> 00:02:42,770
Så vi ser at når vi har lykkes
lese inn et ord i

49
00:02:42,770 --> 00:02:48,270
entry-> ord, så vi kommer til hasj
at ordet med vår hash-funksjon.

50
00:02:48,270 --> 00:02:49,580
La oss ta en titt på
hash-funksjon.

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

52
00:02:52,430 --> 00:02:55,610
>> Så du ikke virkelig trenger
å forstå dette.

53
00:02:55,610 --> 00:02:59,460
Og faktisk, vi bare trakk dette
hash-funksjon fra internett.

54
00:02:59,460 --> 00:03:04,010
Det eneste du trenger å anerkjenne er
at dette tar en const char * ord,

55
00:03:04,010 --> 00:03:08,960
så det tar en streng som input og
returnere en usignert int som utgang.

56
00:03:08,960 --> 00:03:12,360
Så det er alt en hash-funksjon er, er det
tar i en inngang, det gir deg en

57
00:03:12,360 --> 00:03:14,490
indeks inn i nøkkeltabell.

58
00:03:14,490 --> 00:03:18,530
Legg merke til at vi er modding av NUM_BUCKETS
så hash-verdi returneres

59
00:03:18,530 --> 00:03:21,730
faktisk er en indeks inn i hash table
og indekserer ikke utover

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

61
00:03:24,320 --> 00:03:27,855
>> Så gitt at hash-funksjon, skal vi
til hasj ordet som vi leser

62
00:03:27,855 --> 00:03:31,700
fra ordboken og så skal vi
å bruke som har å sette inn

63
00:03:31,700 --> 00:03:33,750
inntreden i hash table.

64
00:03:33,750 --> 00:03:38,830
Nå er hashtabellen hash gjeldende
lenket liste i hash table, og

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

66
00:03:41,410 --> 00:03:45,640
Vi ønsker å sette vår inntreden på
I begynnelsen av dette lenket liste, og så

67
00:03:45,640 --> 00:03:48,910
vi kommer til å ha vår nåværende oppføring
peke på hva hash tabellen for øyeblikket

68
00:03:48,910 --> 00:03:54,030
poeng til og vi kommer til å lagre
i hash table på hash

69
00:03:54,030 --> 00:03:55,350
den gjeldende oppføringen.

70
00:03:55,350 --> 00:03:59,320
>> Så disse to linjene med hell sette
trer ved begynnelsen av

71
00:03:59,320 --> 00:04:02,270
lenket liste ved at indeksen
i hash tabellen.

72
00:04:02,270 --> 00:04:04,900
Når vi er ferdig med det, vi vet
at vi fant et annet ord i

73
00:04:04,900 --> 00:04:07,800
ordbok og vi øke igjen.

74
00:04:07,800 --> 00:04:13,960
Så vi fortsette med det inntil fscanf
endelig returnerer noe ikke en på

75
00:04:13,960 --> 00:04:18,560
hvilket punkt husk at vi trenger å
gratis inngang, så her oppe, vi malloced en

76
00:04:18,560 --> 00:04:21,329
oppføring og vi prøvde å lese noe
fra ordboken.

77
00:04:21,329 --> 00:04:24,110
Og om vi ikke lykkes lese
noe fra ordboken der

78
00:04:24,110 --> 00:04:27,440
tilfelle vi trenger å frigjøre oppføringen som vi
aldri faktisk satt i hash table

79
00:04:27,440 --> 00:04:29,110
og til slutt bryte.

80
00:04:29,110 --> 00:04:32,750
>> Når vi bryter ut, trenger vi å se, vel,
gjorde vi bryte ut fordi det

81
00:04:32,750 --> 00:04:35,840
ble en feil ved lesing fra filen, eller
gjorde vi bryte ut fordi vi nådd

82
00:04:35,840 --> 00:04:37,120
slutten av filen?

83
00:04:37,120 --> 00:04:40,150
Hvis det var en feil, så vi ønsker å
return false fordi belastningen ikke

84
00:04:40,150 --> 00:04:43,260
lykkes, og i prosessen, ønsker vi å
losse alle ordene som vi leser

85
00:04:43,260 --> 00:04:45,670
inn og lukke ordlistefilen.

86
00:04:45,670 --> 00:04:48,740
Antar vi lykkes, så vi bare
fortsatt trenger å lukke ordlisten

87
00:04:48,740 --> 00:04:51,970
fil, og til slutt returnere sant siden
vi har lastet inn

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

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

90
00:04:54,420 --> 00:04:59,020
>> Så nå sjekke, gitt en ladd hash table,
kommer til å se slik ut.

91
00:04:59,020 --> 00:05:02,690
Så sjekk, den returnerer en bool, som
kommer til å indikere hvorvidt

92
00:05:02,690 --> 00:05:07,530
gått-i char * ord, om
gått-i strengen er i vår ordbok.

93
00:05:07,530 --> 00:05:10,530
Så hvis det er i ordboken, hvis det er
i vår hash table, vil vi komme tilbake

94
00:05:10,530 --> 00:05:13,380
sant, og hvis det ikke er det,
vi vil returnere false.

95
00:05:13,380 --> 00:05:17,770
Gitt dette gått-i ord, er vi
kommer til hasj ordet.

96
00:05:17,770 --> 00:05:22,020
>> Nå, er en viktig ting å gjenkjenne
at i lasten, vi visste at alle

97
00:05:22,020 --> 00:05:25,820
ordene skulle skrives med små bokstaver,
men her er vi ikke så sikker.

98
00:05:25,820 --> 00:05:29,510
Hvis vi tar en titt på vår hash-funksjon,
vår hash-funksjon faktisk

99
00:05:29,510 --> 00:05:32,700
er lowercasing hvert tegn
av ordet.

100
00:05:32,700 --> 00:05:37,580
Så uavhengig av kapitalisering av
ord, er vår hash-funksjon kommer til å

101
00:05:37,580 --> 00:05:42,270
returnere den samme indeksen for uansett
kapitalisering er som det ville ha

102
00:05:42,270 --> 00:05:45,280
returneres for et helt små bokstaver
versjon av ordet.

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

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

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

106
00:05:49,790 --> 00:05:52,940
Nå, dette for loop kommer
til over lenkeliste

107
00:05:52,940 --> 00:05:55,000
som var på den indeksen.

108
00:05:55,000 --> 00:05:59,630
Så oppdager vi initialisering oppføring
å peke på at indeksen.

109
00:05:59,630 --> 00:06:03,480
Vi kommer til å fortsette mens entry gjør
ikke lik NULL, og husk at

110
00:06:03,480 --> 00:06:08,350
oppdatere pekeren i vår lenket liste
entry tilsvarer entry-> neste, så har

111
00:06:08,350 --> 00:06:13,840
vår nåværende inngangspunkt til
neste element i lenket liste.

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

113
00:06:14,400 --> 00:06:19,150
>> Så for hver oppføring i lenket liste,
vi kommer til å bruke strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Det er ikke StrCmp fordi en gang, vi
ønsker å gjøre ting saken insensitively.

115
00:06:23,780 --> 00:06:28,830
Så vi bruker strcasecmp å sammenligne ordet
som ble sendt til denne funksjonen

116
00:06:28,830 --> 00:06:31,860
mot ordet som
er i dette innlegget.

117
00:06:31,860 --> 00:06:35,570
Hvis den gir 0, betyr at det ikke var
en kamp, ​​og da ønsker vi å

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

119
00:06:36,630 --> 00:06:39,590
Vi vellykket funnet
ord i vår hash table.

120
00:06:39,590 --> 00:06:43,040
>> Hvis det ikke var en kamp, ​​så vi er
kommer til å sløyfe igjen og se på

121
00:06:43,040 --> 00:06:43,990
neste oppføring.

122
00:06:43,990 --> 00:06:47,640
Og vi vil fortsette looping mens det
er oppføringer i denne lenket liste.

123
00:06:47,640 --> 00:06:50,160
Hva skjer hvis vi bryter
ut av dette for løkke?

124
00:06:50,160 --> 00:06:55,110
Det betyr at vi ikke finner en oppføring som
matchet dette ordet, i så fall

125
00:06:55,110 --> 00:07:00,220
vi return false for å vise at vår
hash table inneholdt ikke dette ordet.

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

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

128
00:07:02,540 --> 00:07:04,790
>> Så la oss ta en titt på størrelse.

129
00:07:04,790 --> 00:07:09,280
Nå er størrelsen kommer til å være ganske enkel
siden husker i lasten, for hvert ord

130
00:07:09,280 --> 00:07:12,880
vi fant vi økes en global
variable hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Så størrelsen funksjon er rett
kommer til å returnere 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
>> Nå endelig, trenger vi å losse
ordbok når alt er ferdig.

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

135
00:07:25,340 --> 00:07:30,440
Akkurat her er vi looping over alt
bøtter med vår hash table.

136
00:07:30,440 --> 00:07:33,240
Så det er NUM_BUCKETS bøtter.

137
00:07:33,240 --> 00:07:37,490
Og for hver lenket liste i vår hash
bordet, kommer vi til å sløyfe over

138
00:07:37,490 --> 00:07:41,070
Helheten av lenket liste
frigjør hvert element.

139
00:07:41,070 --> 00:07:46,070
Nå må vi være forsiktige, så her er vi
har en midlertidig variabel som er

140
00:07:46,070 --> 00:07:49,740
lagring av pekeren til den neste
element i lenket liste.

141
00:07:49,740 --> 00:07:52,140
Og så skal vi gratis
det aktuelle elementet.

142
00:07:52,140 --> 00:07:55,990
>> Vi må være sikker på at vi gjør dette fordi vi
kan ikke bare frigjøre det aktuelle elementet

143
00:07:55,990 --> 00:07:59,260
og deretter prøve å få tilgang til neste pekeren
siden når vi frigjort det

144
00:07:59,260 --> 00:08:00,870
minnet blir ugyldig.

145
00:08:00,870 --> 00:08:04,990
Så vi trenger å holde rundt en peker til
neste element, så vi kan frigjøre

146
00:08:04,990 --> 00:08:08,360
gjeldende element, og da kan vi oppdatere
vår nåværende element for å peke på

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

148
00:08:09,590 --> 00:08:12,770
>> Vi vil sløyfe mens det er elementer
i dette lenket liste.

149
00:08:12,770 --> 00:08:16,450
Vi vil gjøre det for alle lenkede lister i
hash tabellen, og når vi er ferdige

150
00:08:16,450 --> 00:08:20,180
med det, har vi helt losset
hash tabellen, og vi er ferdige.

151
00:08:20,180 --> 00:08:24,050
Så det er umulig for fjerninger å noensinne
return false, og når vi er ferdige, vi

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

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