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
Ik ben Rob, en hasj laten we
deze oplossing uit.

4
00:00:16,210 --> 00:00:20,070
Dus hier gaan we implementeren
een algemene hash table.

5
00:00:20,070 --> 00:00:24,090
We zien dat de structuur knooppunt van onze hash
tafel gaat uitzien.

6
00:00:24,090 --> 00:00:28,710
Dus het gaat om een ​​char woord hebben
matrix van grootte lengte plus 1.

7
00:00:28,710 --> 00:00:32,259
Vergeet niet de 1 omdat de maximale
woord in het woordenboek is 45

8
00:00:32,259 --> 00:00:35,110
personages, en dan gaan we naar
moet een extra karakter voor de

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

10
00:00:37,070 --> 00:00:40,870
>> En dan is onze hash table in elk
emmer gaat slaan een

11
00:00:40,870 --> 00:00:42,320
gelinkte lijst van knooppunten.

12
00:00:42,320 --> 00:00:44,420
We zijn niet lineair hier indringende doen.

13
00:00:44,420 --> 00:00:48,430
En dus om te linken naar het volgende
element in de emmer, hebben we een

14
00:00:48,430 --> 00:00:51,110
struct knoop * volgende.

15
00:00:51,110 --> 00:00:53,090
Dus dat is wat een knooppunt eruit ziet.

16
00:00:53,090 --> 00:00:56,180
Nu, hier is de verklaring
van onze hash table.

17
00:00:56,180 --> 00:01:01,910
Het gaat om 16.384 bakken hebben, maar
dat aantal maakt niet echt uit.

18
00:01:01,910 --> 00:01:05,450
En tot slot, we gaan de
globale variabele hashtable_size die

19
00:01:05,450 --> 00:01:08,640
gaat beginnen als 0, en het is
gaan om bij te houden hoeveel woorden

20
00:01:08,640 --> 00:01:10,080
waren in onze woordenboek.

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

22
00:01:10,760 --> 00:01:13,190
>> Dus laten we eens een kijkje nemen op belasting.

23
00:01:13,190 --> 00:01:16,390
Dus merken dat de belasting,
retourneert een bool.

24
00:01:16,390 --> 00:01:20,530
U return true als het succesvol was
geladen en anders false.

25
00:01:20,530 --> 00:01:23,990
En het duurt een const char * sterren
woordenboek dat de woordenlijst

26
00:01:23,990 --> 00:01:25,280
dat we willen openen.

27
00:01:25,280 --> 00:01:27,170
Dus dat is het eerste wat
we gaan doen.

28
00:01:27,170 --> 00:01:30,420
We gaan naar het woordenboek fopen voor
lezen, en we gaan te hebben

29
00:01:30,420 --> 00:01:34,700
om ervoor te zorgen dat het gelukt dus als
het NULL terug, dan hebben we niet

30
00:01:34,700 --> 00:01:37,440
het woordenboek met succes te openen
en we moeten return false.

31
00:01:37,440 --> 00:01:41,580
>> Maar ervan uitgaande dat het met succes gedaan
geopend, dan willen we lezen de

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

33
00:01:42,400 --> 00:01:46,210
Dus houd looping tot we enkele
reden om uit te breken van deze

34
00:01:46,210 --> 00:01:47,570
lus die we zullen zien.

35
00:01:47,570 --> 00:01:51,780
Dus hou looping, en nu gaan we
om een ​​enkel knooppunt malloc.

36
00:01:51,780 --> 00:01:56,800
En natuurlijk moeten we check fout
weer dus als mallocing niet gelukt

37
00:01:56,800 --> 00:02:00,660
en we willen elke node die wij lossen
gebeurd met malloc voor, sluit de

38
00:02:00,660 --> 00:02:02,590
woordenboek en return false.

39
00:02:02,590 --> 00:02:07,440
>> Maar negeren dat, uitgaande we
gelukt, dan willen we fscanf gebruiken

40
00:02:07,440 --> 00:02:12,400
om een ​​enkel woord lezen uit onze
woordenboek in onze knooppunt.

41
00:02:12,400 --> 00:02:17,310
Dus onthoud dat entry-> woord is de char
woord buffer van grootte lengte plus

42
00:02:17,310 --> 00:02:20,300
een die we gaan
bewaar het woord in

43
00:02:20,300 --> 00:02:25,280
Dus fscanf gaat terug 1 zolang
zoals het was in staat om succesvol te lezen een

44
00:02:25,280 --> 00:02:26,750
Het woord van het bestand.

45
00:02:26,750 --> 00:02:31,030
>> Als een van beide een fout gebeurt of we bereiken
het einde van het bestand, het zal niet

46
00:02:31,030 --> 00:02:34,950
return 1 in dat geval als het niet
return 1, we eindelijk gaat breken

47
00:02:34,950 --> 00:02:37,280
uit deze while lus.

48
00:02:37,280 --> 00:02:42,770
Zo zien we dat als we succes hebben
lees een woord in

49
00:02:42,770 --> 00:02:48,270
entry-> woord, dan gaan we naar hash
dat woord gebruik van onze hash-functie.

50
00:02:48,270 --> 00:02:49,580
Laten we eens een kijkje nemen op
de hash-functie.

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

52
00:02:52,430 --> 00:02:55,610
>> Zodat je niet echt nodig hebt
om dit te begrijpen.

53
00:02:55,610 --> 00:02:59,460
En eigenlijk hebben we alleen deze getrokken
hash-functie van het internet.

54
00:02:59,460 --> 00:03:04,010
Het enige wat je moet erkennen is
dat dit duurt een const char * woord,

55
00:03:04,010 --> 00:03:08,960
dus het is het nemen van een string als input en
retourneren van een unsigned int als output.

56
00:03:08,960 --> 00:03:12,360
Dus dat is al een hash-functie is, is het
neemt in een input, het geeft je een geeft

57
00:03:12,360 --> 00:03:14,490
index in de hash tabel.

58
00:03:14,490 --> 00:03:18,530
Merk op dat we modding door NUM_BUCKETS
dus de hash-waarde terug

59
00:03:18,530 --> 00:03:21,730
eigenlijk is een index in de hash table
en niet geïndexeerd dan de

60
00:03:21,730 --> 00:03:24,320
grenzen van de array.

61
00:03:24,320 --> 00:03:27,855
>> Zo bepaalde hash-functie, we gaan
aan het woord die we lezen hash

62
00:03:27,855 --> 00:03:31,700
uit het woordenboek en dan gaan we
te gebruiken dat moet steek de

63
00:03:31,700 --> 00:03:33,750
binnenkomst in de hash tabel.

64
00:03:33,750 --> 00:03:38,830
Nu, hash hash is de huidige
gelinkte lijst in de hash tabel en

65
00:03:38,830 --> 00:03:41,410
het is heel goed mogelijk dat is gewoon NULL.

66
00:03:41,410 --> 00:03:45,640
We willen onze toegang aan de voegen
begin van deze gelinkte lijst, en dus

67
00:03:45,640 --> 00:03:48,910
we gaan onze huidige item hebben
wijzen op wat de hash tabel momenteel

68
00:03:48,910 --> 00:03:54,030
punten aan en dan gaan we op te slaan
in de hash tabel aan het hekje

69
00:03:54,030 --> 00:03:55,350
de huidige vermelding.

70
00:03:55,350 --> 00:03:59,320
>> Dus deze twee lijnen met succes te voegen
de ingang aan het begin van de

71
00:03:59,320 --> 00:04:02,270
gelinkte lijst op die index
in de hash tabel.

72
00:04:02,270 --> 00:04:04,900
Zodra we klaar zijn met dat, we weten
dat vonden we een ander woord in de

73
00:04:04,900 --> 00:04:07,800
woordenboek en we verhogen opnieuw.

74
00:04:07,800 --> 00:04:13,960
Dus houden we dat doen totdat fscanf
eindelijk weer iets niet 1 op

75
00:04:13,960 --> 00:04:18,560
welk punt herinneren dat we moeten
gratis toegang, dus hier, we malloced een

76
00:04:18,560 --> 00:04:21,329
binnenkomst en we hebben geprobeerd om iets te lezen
uit het woordenboek.

77
00:04:21,329 --> 00:04:24,110
En we hebben niet met succes gelezen
iets uit het woordenboek waarin

78
00:04:24,110 --> 00:04:27,440
geval moeten we het item dat we vrij
nooit daadwerkelijk in de hash tabel gezet

79
00:04:27,440 --> 00:04:29,110
en uiteindelijk breken.

80
00:04:29,110 --> 00:04:32,750
>> Zodra we uit te breken, moeten we zien, nou ja,
hebben we breken omdat er

81
00:04:32,750 --> 00:04:35,840
was een fout bij het lezen van het bestand, of
hebben we breken omdat we bereikt

82
00:04:35,840 --> 00:04:37,120
het einde van het bestand?

83
00:04:37,120 --> 00:04:40,150
Als er een fout, dan willen we
return false omdat belasting niet

84
00:04:40,150 --> 00:04:43,260
slagen, en in het proces, we willen
lossen alle woorden die we lezen

85
00:04:43,260 --> 00:04:45,670
in en sluit het woordenboek bestand.

86
00:04:45,670 --> 00:04:48,740
Ervan uitgaande dat we niet slagen, dan kunnen we gewoon
nog steeds nodig om het woordenboek te sluiten

87
00:04:48,740 --> 00:04:51,970
bestand, en tenslotte return true sinds
we hebben met succes geladen de

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

89
00:04:53,040 --> 00:04:54,420
En dat is het voor de belasting.

90
00:04:54,420 --> 00:04:59,020
>> Dus nu controleren, gegeven een geladen hash table,
gaat er zo uitzien.

91
00:04:59,020 --> 00:05:02,690
Dus check, het een bool terug, die
zal aangeven of de

92
00:05:02,690 --> 00:05:07,530
doorgegeven in char * woord, of de
doorgegeven in string is in ons woordenboek.

93
00:05:07,530 --> 00:05:10,530
Dus als het in het woordenboek, als het
in onze hash table, we zullen terugkeren

94
00:05:10,530 --> 00:05:13,380
waar, en als het niet,
we zullen valse terugkeren.

95
00:05:13,380 --> 00:05:17,770
Gezien deze doorgegeven in woord, we zijn
gaan naar het woord hash.

96
00:05:17,770 --> 00:05:22,020
>> Nu, een belangrijk ding te herkennen is
dat in de belasting, wisten we dat al

97
00:05:22,020 --> 00:05:25,820
de woorden zouden kleine letters,
maar hier, we zijn niet zo zeker van.

98
00:05:25,820 --> 00:05:29,510
Als we een kijkje nemen op onze hash-functie,
onze hash-functie eigenlijk

99
00:05:29,510 --> 00:05:32,700
wordt lowercasing elk karakter
van het woord.

100
00:05:32,700 --> 00:05:37,580
Dus ongeacht de kapitalisatie van
woord, is onze hash-functie gaat

101
00:05:37,580 --> 00:05:42,270
terug dezelfde index voor wat de
kapitalisatie is zoals het zou moeten

102
00:05:42,270 --> 00:05:45,280
terug voor een volledig kleine
versie van het woord.

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

104
00:05:45,950 --> 00:05:47,410
>> Dus dat is onze index.

105
00:05:47,410 --> 00:05:49,790
Het is de hash-tabel voor dit woord.

106
00:05:49,790 --> 00:05:52,940
Nu, deze lus gaat
de gekoppelde lijst OVER

107
00:05:52,940 --> 00:05:55,000
dat was die index.

108
00:05:55,000 --> 00:05:59,630
Zo merken we initialiseren binnenkomst
te wijzen die index.

109
00:05:59,630 --> 00:06:03,480
We gaan blijven terwijl binnenkomst doet
niet gelijk NULL, en vergeet niet dat

110
00:06:03,480 --> 00:06:08,350
bijwerken van de aanwijzer in onze gelinkte lijst
binnenkomst gelijk entry-> volgende, zo hebben

111
00:06:08,350 --> 00:06:13,840
onze huidige toegangspunt tot de
volgende item in gelinkte lijst.

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

113
00:06:14,400 --> 00:06:19,150
>> Dus voor elk item in de gelinkte lijst,
we gaan strcasecmp gebruiken.

114
00:06:19,150 --> 00:06:23,780
Het is niet strcmp want nogmaals, we
willen dingen geval ongevoelig doen.

115
00:06:23,780 --> 00:06:28,830
We gebruiken dus strcasecmp om het woord te vergelijken
die werd doorgegeven aan deze functie

116
00:06:28,830 --> 00:06:31,860
tegen het woord dat
in deze ingang.

117
00:06:31,860 --> 00:06:35,570
Als het weer 0, dat betekent dat er
een wedstrijd, waarbij we willen

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

119
00:06:36,630 --> 00:06:39,590
Wij hebben met succes vonden de
woord in onze hash table.

120
00:06:39,590 --> 00:06:43,040
>> Als er geen match, dan zijn we
gaat lus opnieuw en kijk naar de

121
00:06:43,040 --> 00:06:43,990
volgende item.

122
00:06:43,990 --> 00:06:47,640
En we gaan terwijl er verder looping
zijn items in deze gelinkte lijst.

123
00:06:47,640 --> 00:06:50,160
Wat gebeurt er als we breken
uit deze lus?

124
00:06:50,160 --> 00:06:55,110
Dat betekent dat we een ingang niet vinden dat
paste dit woord, in welk geval

125
00:06:55,110 --> 00:07:00,220
we return false aangeven dat onze
hash table heeft dit woord niet bevatten.

126
00:07:00,220 --> 00:07:01,910
En dat is het voor controle.

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

128
00:07:02,540 --> 00:07:04,790
>> Dus laten we eens een kijkje nemen op grootte.

129
00:07:04,790 --> 00:07:09,280
Nu, de grootte gaat vrij eenvoudig te zijn
sinds herinneren in de belasting, voor elk woord

130
00:07:09,280 --> 00:07:12,880
we vonden we opgehoogd een globale
variabele hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Zodat de grootte functie is gewoon
gaan dat de wereldwijde terug

132
00:07:15,830 --> 00:07:18,150
variabele, en dat is het.

133
00:07:18,150 --> 00:07:22,300
>> Nu eindelijk, moeten we lossen het
woordenboek als alles klaar is.

134
00:07:22,300 --> 00:07:25,340
Dus hoe gaan we dat doen?

135
00:07:25,340 --> 00:07:30,440
Right here, we looping over alle
emmers van onze hash table.

136
00:07:30,440 --> 00:07:33,240
Dus er zijn NUM_BUCKETS emmers.

137
00:07:33,240 --> 00:07:37,490
En voor elke gekoppelde lijst in onze hash
tafel, gaan we lus over de

138
00:07:37,490 --> 00:07:41,070
onderdelen van de gekoppelde lijst
vrijmaken van elk element.

139
00:07:41,070 --> 00:07:46,070
Nu moeten we voorzichtig zijn, dus hier zijn we
een tijdelijke variabele die

140
00:07:46,070 --> 00:07:49,740
opslaan van de pointer naar de volgende
element in de gelinkte lijst.

141
00:07:49,740 --> 00:07:52,140
En dan gaan we gratis
het huidige element.

142
00:07:52,140 --> 00:07:55,990
>> We moeten zorgen dat we dit doen omdat we
kan niet alleen gratis de huidige element

143
00:07:55,990 --> 00:07:59,260
en dan proberen om naar de volgende pointer
want zodra we bevrijd het de

144
00:07:59,260 --> 00:08:00,870
geheugen wordt ongeldig.

145
00:08:00,870 --> 00:08:04,990
Dus moeten we houden rond een pointer naar
het volgende element, dan kunnen we gratis de

146
00:08:04,990 --> 00:08:08,360
huidige element, en dan kunnen we updaten
het actuele element wijzen

147
00:08:08,360 --> 00:08:09,590
het volgende element.

148
00:08:09,590 --> 00:08:12,770
>> We zullen lus terwijl er elementen
in deze gelinkte lijst.

149
00:08:12,770 --> 00:08:16,450
We zullen dat doen voor alle gekoppelde lijsten in
de hash table, en zodra we klaar zijn

150
00:08:16,450 --> 00:08:20,180
met dat, hebben we volledig gelost
de hash table, en we zijn klaar.

151
00:08:20,180 --> 00:08:24,050
Dus het is onmogelijk voor ontlaadt ooit
return false, en als we klaar zijn, we

152
00:08:24,050 --> 00:08:25,320
gewoon terug waar.

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