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
Jag är Rob, och låt oss hash
denna lösning ut.

4
00:00:16,210 --> 00:00:20,070
Så här är vi kommer att genomföra
en allmän hashtabell.

5
00:00:20,070 --> 00:00:24,090
Vi ser att struct nod i vår hash
tabellen kommer att se ut så här.

6
00:00:24,090 --> 00:00:28,710
Så det kommer att ha en char ord
matris av storlek längd plus ett.

7
00:00:28,710 --> 00:00:32,259
Glöm inte 1 eftersom den maximala
ord i ordlistan är 45

8
00:00:32,259 --> 00:00:35,110
tecken, och sedan ska vi
behöver en extra karaktär för

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

10
00:00:37,070 --> 00:00:40,870
>> Och då vår hashtabell i varje
skopan kommer att lagra en

11
00:00:40,870 --> 00:00:42,320
länkad lista av noder.

12
00:00:42,320 --> 00:00:44,420
Vi gör inte linjär sondering här.

13
00:00:44,420 --> 00:00:48,430
Och så för att länka till nästa
inslag i hinken, vi behöver en

14
00:00:48,430 --> 00:00:51,110
struct node * nästa.

15
00:00:51,110 --> 00:00:53,090
Så det är vad en nod ser ut.

16
00:00:53,090 --> 00:00:56,180
Nu, här är förklaringen
av vår hashtabell.

17
00:00:56,180 --> 00:01:01,910
Det kommer att ha 16,384 hinkar, men
den siffran spelar egentligen ingen roll.

18
00:01:01,910 --> 00:01:05,450
Och slutligen, kommer vi att ha
globala variabeln hashtable_size, vilket

19
00:01:05,450 --> 00:01:08,640
kommer att börja som 0, och det är
kommer att hålla reda på hur många ord

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

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

22
00:01:10,760 --> 00:01:13,190
>> Så låt oss ta en titt på last.

23
00:01:13,190 --> 00:01:16,390
Så märker att lasten,
den returnerar en bool.

24
00:01:16,390 --> 00:01:20,530
Du return true om det var lyckat
laddad och falskt annars.

25
00:01:20,530 --> 00:01:23,990
Och det tar en const char * stjärna
lexikon, som är ordboken

26
00:01:23,990 --> 00:01:25,280
att vi vill öppna.

27
00:01:25,280 --> 00:01:27,170
Så det är det första
vi ska göra.

28
00:01:27,170 --> 00:01:30,420
Vi ska fopen ordlistan för
läsning, och vi kommer att ha

29
00:01:30,420 --> 00:01:34,700
att se till att det lyckades så om
det tillbaka NULL, sedan gjorde vi inte

30
00:01:34,700 --> 00:01:37,440
framgångsrikt öppna ordlistan
och vi måste returnera false.

31
00:01:37,440 --> 00:01:41,580
>> Men om man antar att den gjorde med framgång
öppen, då vill vi att läsa

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

33
00:01:42,400 --> 00:01:46,210
Så håll looping tills vi hittar några
anledning att bryta sig ut ur detta

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

35
00:01:47,570 --> 00:01:51,780
Så håll looping, och nu ska vi
att malloc en enda nod.

36
00:01:51,780 --> 00:01:56,800
Och naturligtvis måste vi felkontroll
igen så om mallocing inte lyckades

37
00:01:56,800 --> 00:02:00,660
och vi vill lasta någon nod som vi
hänt med malloc innan, stänger

38
00:02:00,660 --> 00:02:02,590
ordbok och returnera false.

39
00:02:02,590 --> 00:02:07,440
>> Men ignorera det, förutsatt att vi
lyckats, då vill vi använda fscanf

40
00:02:07,440 --> 00:02:12,400
att läsa ett enda ord från vår
dictionary i vårt nod.

41
00:02:12,400 --> 00:02:17,310
Så kom ihåg att posten-> Ordet är rödingen
ordet buffert av storlek längd plus

42
00:02:17,310 --> 00:02:20,300
en som vi kommer att
lagra ord i.

43
00:02:20,300 --> 00:02:25,280
Så fscanf kommer att återvända 1 så länge
eftersom det kunde framgångsrikt läsa en

44
00:02:25,280 --> 00:02:26,750
ord från filen.

45
00:02:26,750 --> 00:02:31,030
>> Om antingen ett fel inträffar eller vi når
slutet på filen, kommer den inte

46
00:02:31,030 --> 00:02:34,950
returnera ett i vilket fall, om den inte gör det
tillbaka 1, vi äntligen bryta

47
00:02:34,950 --> 00:02:37,280
ur denna while-slinga.

48
00:02:37,280 --> 00:02:42,770
Så vi ser att när vi har lyckats
läsa ett ord i

49
00:02:42,770 --> 00:02:48,270
post-> ord, då vi kommer att hash
det ordet med hjälp av vår hashfunktion.

50
00:02:48,270 --> 00:02:49,580
Låt oss ta en titt på
hashfunktionen.

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

52
00:02:52,430 --> 00:02:55,610
>> Så du behöver egentligen inte
att förstå detta.

53
00:02:55,610 --> 00:02:59,460
Och faktiskt, bara drog vi detta
hash funktion från internet.

54
00:02:59,460 --> 00:03:04,010
Det enda du behöver för att känna igen är
att det tar en const char * ord,

55
00:03:04,010 --> 00:03:08,960
så det tar en sträng som indata och
returnera en unsigned int som produktion.

56
00:03:08,960 --> 00:03:12,360
Så det är allt en hash-funktion, är det
tar på en ingång, det ger dig en

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

58
00:03:14,490 --> 00:03:18,530
Lägg märke till att vi modding av NUM_BUCKETS
så det hashvärde return

59
00:03:18,530 --> 00:03:21,730
faktiskt är ett index in i hashtabell
och inte index bortom

60
00:03:21,730 --> 00:03:24,320
gränserna för arrayen.

61
00:03:24,320 --> 00:03:27,855
>> Så med tanke på att hashfunktion, vi ska
att hash ordet som vi läser

62
00:03:27,855 --> 00:03:31,700
från ordlistan och sedan ska vi
att använda som har att sätta in

63
00:03:31,700 --> 00:03:33,750
inträde i hash-tabell.

64
00:03:33,750 --> 00:03:38,830
Nu är hashtable hash den aktuella
länkad lista i hash-tabellen, och

65
00:03:38,830 --> 00:03:41,410
det är mycket möjligt det är bara NULL.

66
00:03:41,410 --> 00:03:45,640
Vi vill sätta in vårt inträde på
början av denna länkade lista och så

67
00:03:45,640 --> 00:03:48,910
vi kommer att ha vår nuvarande posten
peka på vad hash tabellen för tillfället

68
00:03:48,910 --> 00:03:54,030
pekar på och sedan ska vi lagra
i hash-tabellen i hash

69
00:03:54,030 --> 00:03:55,350
den aktuella posten.

70
00:03:55,350 --> 00:03:59,320
>> Så dessa två linjer framgångsrikt sätt in
posten i början av

71
00:03:59,320 --> 00:04:02,270
länkade listan vid detta index
i hash-tabellen.

72
00:04:02,270 --> 00:04:04,900
När vi är klara med det, vi vet
att vi hittat ett annat ord i

73
00:04:04,900 --> 00:04:07,800
ordlista och vi öka igen.

74
00:04:07,800 --> 00:04:13,960
Så vi fortsätter att göra det tills fscanf
slutligen återvänder något icke en vid

75
00:04:13,960 --> 00:04:18,560
vilken punkt kommer ihåg att vi måste
fri entré, så här uppe, malloced vi en

76
00:04:18,560 --> 00:04:21,329
inresa och vi försökte läsa något
från ordlistan.

77
00:04:21,329 --> 00:04:24,110
Och vi har inte lyckats läsa
något från ordlistan i vilken

78
00:04:24,110 --> 00:04:27,440
fall måste vi befria den post som vi
aldrig tas i hash-tabellen

79
00:04:27,440 --> 00:04:29,110
och slutligen brytas.

80
00:04:29,110 --> 00:04:32,750
>> När vi bryter ut, måste vi se, ja,
vi bryta ut eftersom det

81
00:04:32,750 --> 00:04:35,840
var ett fel vid läsning från filen, eller
vi bryta ut eftersom vi nådde

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

83
00:04:37,120 --> 00:04:40,150
Om det fanns ett fel, då vill vi att
returnera false eftersom lasten inte

84
00:04:40,150 --> 00:04:43,260
lyckas, och i processen, vill vi
lasta av alla de ord som vi läser

85
00:04:43,260 --> 00:04:45,670
i och stäng ordlistefilen.

86
00:04:45,670 --> 00:04:48,740
Förutsatt att vi lyckades, då vi bara
ändå måste stänga i ordlistan

87
00:04:48,740 --> 00:04:51,970
fil, och slutligen återvänder sant eftersom
Vi har laddats i

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

89
00:04:53,040 --> 00:04:54,420
Och det är det för last.

90
00:04:54,420 --> 00:04:59,020
>> Så nu kontrollera, med tanke på en laddad hash-tabell,
kommer att se ut så här.

91
00:04:59,020 --> 00:05:02,690
Så kolla, den returnerar en bool, som
kommer att indikera om

92
00:05:02,690 --> 00:05:07,530
passerade-in char * ord, om
passerade-in sträng är i vår ordlista.

93
00:05:07,530 --> 00:05:10,530
Så om det är i ordlistan, om det är
i vårt hashtabell, kommer vi tillbaka

94
00:05:10,530 --> 00:05:13,380
sant, och om det inte är,
vi kommer att returnera false.

95
00:05:13,380 --> 00:05:17,770
Med tanke på detta passerade-in ord, vi är
kommer att hash ordet.

96
00:05:17,770 --> 00:05:22,020
>> Nu är en viktig sak att känna igen
att i lasten, vi visste att alla

97
00:05:22,020 --> 00:05:25,820
orden skulle bli små bokstäver,
men här är vi inte så säker.

98
00:05:25,820 --> 00:05:29,510
Om vi ​​tar en titt på hash-funktion,
vår hashfunktion faktiskt

99
00:05:29,510 --> 00:05:32,700
är lowercasing varje tecken
av ordet.

100
00:05:32,700 --> 00:05:37,580
Så oavsett kapitalisering av
ord, är vår hashfunktion går till

101
00:05:37,580 --> 00:05:42,270
tillbaka samma index för oavsett
aktivering är som det skulle ha

102
00:05:42,270 --> 00:05:45,280
returneras för en helt gement
version av ordet.

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

104
00:05:45,950 --> 00:05:47,410
>> Så det är vårt index.

105
00:05:47,410 --> 00:05:49,790
Det är hashtabell för detta ord.

106
00:05:49,790 --> 00:05:52,940
Nu, detta för slinga går
till över den länkade listan

107
00:05:52,940 --> 00:05:55,000
Det var vid detta index.

108
00:05:55,000 --> 00:05:59,630
Så märker vi att initiera inresa
att peka på detta index.

109
00:05:59,630 --> 00:06:03,480
Vi kommer att fortsätta medan posten gör
inte lika NULL, och kom ihåg att

110
00:06:03,480 --> 00:06:08,350
uppdaterar pekaren i vår länkad lista
posten är lika med posten-> nästa, så har

111
00:06:08,350 --> 00:06:13,840
vår nuvarande ingång till
Nästa objekt i länkad lista.

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

113
00:06:14,400 --> 00:06:19,150
>> Så för varje post i den länkade listan,
vi kommer att använda strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Det är inte StrCmp eftersom ännu en gång, vi
vill göra saker fallet okänsligt.

115
00:06:23,780 --> 00:06:28,830
Så vi använder strcasecmp jämföra ordet
som skickades till denna funktion

116
00:06:28,830 --> 00:06:31,860
mot det ord som
är i denna post.

117
00:06:31,860 --> 00:06:35,570
Om den returnerar 0, betyder att det inte var
en match, i vilket fall vi vill

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

119
00:06:36,630 --> 00:06:39,590
Vi fann framgångsrikt
ord i vårt hashtabell.

120
00:06:39,590 --> 00:06:43,040
>> Om det fanns inte en match, då är vi
gå till loop igen och titta på

121
00:06:43,040 --> 00:06:43,990
nästa post.

122
00:06:43,990 --> 00:06:47,640
Och vi kommer att fortsätta looping medan det
är poster i detta länkad lista.

123
00:06:47,640 --> 00:06:50,160
Vad händer om vi bryter
ur detta för loop?

124
00:06:50,160 --> 00:06:55,110
Det betyder att vi inte hittade en post som
matchas detta ord, i vilket fall

125
00:06:55,110 --> 00:07:00,220
vi returnera false för att ange att vår
hashtabell inte innehöll detta ord.

126
00:07:00,220 --> 00:07:01,910
Och det är den för kontroll.

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

128
00:07:02,540 --> 00:07:04,790
>> Så låt oss ta en titt på storlek.

129
00:07:04,790 --> 00:07:09,280
Nu, storlek kommer att vara ganska enkelt
sedan minns i lasten, för varje ord

130
00:07:09,280 --> 00:07:12,880
vi hittade vi ökas en global
variabel hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Så storleken funktion är bara
kommer att returnera det globala

132
00:07:15,830 --> 00:07:18,150
variabel, och det är det.

133
00:07:18,150 --> 00:07:22,300
>> Nu äntligen, måste vi lasta av
dictionary när allt är gjort.

134
00:07:22,300 --> 00:07:25,340
Så hur ska vi göra det?

135
00:07:25,340 --> 00:07:30,440
Just här, vi loopa över alla
hinkar med vår hashtabell.

136
00:07:30,440 --> 00:07:33,240
Så det finns NUM_BUCKETS hinkar.

137
00:07:33,240 --> 00:07:37,490
Och för varje länkad lista i vår hash
bord, vi ska slinga över

138
00:07:37,490 --> 00:07:41,070
helheten av den länkade listan
frigöra varje element.

139
00:07:41,070 --> 00:07:46,070
Nu måste vi vara försiktiga, så här är vi
har en temporär variabel som är

140
00:07:46,070 --> 00:07:49,740
lagra pekare till nästa
elementet i den länkade listan.

141
00:07:49,740 --> 00:07:52,140
Och sedan ska vi gratis
det aktuella elementet.

142
00:07:52,140 --> 00:07:55,990
>> Vi måste vara säkra på att vi gör detta eftersom vi
kan inte bara befria det aktuella elementet

143
00:07:55,990 --> 00:07:59,260
och sedan försöka komma till nästa pekaren
sedan när vi befriade det

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

145
00:08:00,870 --> 00:08:04,990
Så vi måste hålla runt en pekare till
nästa element, då vi kan frigöra

146
00:08:04,990 --> 00:08:08,360
aktuellt element, och då kan vi uppdatera
vår nuvarande elementet att peka på

147
00:08:08,360 --> 00:08:09,590
nästa element.

148
00:08:09,590 --> 00:08:12,770
>> Vi ska slinga medan det finns inslag
i detta länkad lista.

149
00:08:12,770 --> 00:08:16,450
Vi kommer att göra det för alla länkade listor i
hash tabellen, och när vi är klara

150
00:08:16,450 --> 00:08:20,180
med det har vi helt lossas
hash tabellen, och vi är klara.

151
00:08:20,180 --> 00:08:24,050
Så det är omöjligt för lastar någonsin
returnera false, och när vi är klara, vi

152
00:08:24,050 --> 00:08:25,320
bara return true.

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