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
Olen Rob, ja lähdetään hash
tämä ratkaisu ulos.

4
00:00:16,210 --> 00:00:20,070
Joten tässä me aiomme toteuttaa
yleinen hash table.

5
00:00:20,070 --> 00:00:24,090
Näemme, että struct solmu meidän hash
taulukossa on menossa näyttää tältä.

6
00:00:24,090 --> 00:00:28,710
Niin se tulee olla char sana
taulukon koko pituus plus 1.

7
00:00:28,710 --> 00:00:32,259
Älä unohda 1 koska suurin
sanan sanakirjasta on 45

8
00:00:32,259 --> 00:00:35,110
merkkejä, ja sitten me aiomme
tarvitset enää yhden merkin

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

10
00:00:37,070 --> 00:00:40,870
>> Ja sitten meidän tiiviste kussakin
kauha on menossa tallentamaan

11
00:00:40,870 --> 00:00:42,320
linkitetyn listan solmuja.

12
00:00:42,320 --> 00:00:44,420
Emme tee lineaarinen luotaa täällä.

13
00:00:44,420 --> 00:00:48,430
Ja niin, jotta sen yhteys seuraavaan
elementti ämpäri, tarvitsemme

14
00:00:48,430 --> 00:00:51,110
struct solmu * seuraavaksi.

15
00:00:51,110 --> 00:00:53,090
Niin, että mitä solmu näyttää.

16
00:00:53,090 --> 00:00:56,180
Nyt tässä ilmoituksessa
meidän tiiviste.

17
00:00:56,180 --> 00:01:01,910
Se tulee olla 16384 kauhat, mutta
että määrä ei ole niin väliä.

18
00:01:01,910 --> 00:01:05,450
Ja lopuksi, me aiomme olla
globaali muuttuja hashtable_size, joka

19
00:01:05,450 --> 00:01:08,640
aikoo alkajaisiksi kuin 0, ja se on
aio pitää kirjaa siitä, kuinka monta sanaa

20
00:01:08,640 --> 00:01:10,080
olivat meidän sanakirja.

21
00:01:10,080 --> 00:01:10,760
Selvä.

22
00:01:10,760 --> 00:01:13,190
>> Joten katsotaanpa katsomaan kuormalla.

23
00:01:13,190 --> 00:01:16,390
Niin huomaa, että kuormitus,
se palauttaa bool.

24
00:01:16,390 --> 00:01:20,530
Palaat tosi, jos se onnistui
ladattu ja vääriä toisin.

25
00:01:20,530 --> 00:01:23,990
Ja se vie const char * tähden
sanakirja, joka on sanakirja

26
00:01:23,990 --> 00:01:25,280
että haluamme avata.

27
00:01:25,280 --> 00:01:27,170
Niin, että ensimmäinen asia
aiomme tehdä.

28
00:01:27,170 --> 00:01:30,420
Aiomme fopen sanakirja
lukeminen, ja me aiomme olla

29
00:01:30,420 --> 00:01:34,700
varmista, että se onnistui niin jos
se palasi NULL, niin emme

30
00:01:34,700 --> 00:01:37,440
onnistuneesti Avaa sanakirja
ja meidän täytyy palata vääriä.

31
00:01:37,440 --> 00:01:41,580
>> Mutta olettaen, että se teki onnistuneesti
auki, haluamme lukea

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

33
00:01:42,400 --> 00:01:46,210
Joten pitää kiehkura kunnes löydämme
syytä murtautua ulos tästä

34
00:01:46,210 --> 00:01:47,570
silmukka, joka näemme.

35
00:01:47,570 --> 00:01:51,780
Joten pitää kiehkura, ja nyt olemme menossa
to malloc yhden solmun.

36
00:01:51,780 --> 00:01:56,800
Ja tietenkin, meidän täytyy virhetarkistusarvot
uudelleen joten jos mallocing ei onnistunut

37
00:01:56,800 --> 00:02:00,660
ja haluamme purkaa tahansa solmuun, että me
tapahtui malloc ennen, sulje

38
00:02:00,660 --> 00:02:02,590
sanakirja ja palauttaa false.

39
00:02:02,590 --> 00:02:07,440
>> Mutta unohdetaan, että vaikka oletettaisiin me
onnistunut, niin haluamme käyttää fscanf

40
00:02:07,440 --> 00:02:12,400
lukea sanaakaan meidän
sanaston meidän solmuun.

41
00:02:12,400 --> 00:02:17,310
Niin muista, että maahantulo-> sana on char
sana puskurin koko pituutta plus

42
00:02:17,310 --> 00:02:20,300
joka aiomme
Säilytä sana sisään

43
00:02:20,300 --> 00:02:25,280
Joten fscanf aikoo palata 1 niin kauan
sillä se kykeni lukemaan

44
00:02:25,280 --> 00:02:26,750
sana tiedoston.

45
00:02:26,750 --> 00:02:31,030
>> Jos jompikumpi virhe tapahtuu, tai pääsemme
tiedoston loppuun, se ei

46
00:02:31,030 --> 00:02:34,950
palata 1 jolloin jos se ei
palata 1, olemme vihdoin menossa rikkoa

47
00:02:34,950 --> 00:02:37,280
pois tästä kun silmukka.

48
00:02:37,280 --> 00:02:42,770
Näemme siis, että kun meillä on onnistuneesti
lukea sanan

49
00:02:42,770 --> 00:02:48,270
entry-> sana, niin aiomme hash
että sana käyttämällä tiivistefunktiota.

50
00:02:48,270 --> 00:02:49,580
Katsotaanpa katsomaan
hash-funktio.

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

52
00:02:52,430 --> 00:02:55,610
>> Joten sinun ei todellakaan tarvitse
ymmärtää tätä.

53
00:02:55,610 --> 00:02:59,460
Ja oikeastaan ​​me vain veti tämän
hajautusfunktio Internetistä.

54
00:02:59,460 --> 00:03:04,010
Ainoa asia, sinun täytyy tunnustaa, on
että tämä vie const char * sana,

55
00:03:04,010 --> 00:03:08,960
joten se vie merkkijonon tulo ja
palaamassa unsigned int tuotokseksi.

56
00:03:08,960 --> 00:03:12,360
Niin, että kaikki hash-toiminto on, on se
vie tulo, se antaa sinulle

57
00:03:12,360 --> 00:03:14,490
indeksinä tiiviste.

58
00:03:14,490 --> 00:03:18,530
Huomaa, että olemme Modaus by NUM_BUCKETS
niin hash arvo palautetaan

59
00:03:18,530 --> 00:03:21,730
oikeastaan ​​on indeksinä tiiviste
ja ei indeksoi yli

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

61
00:03:24,320 --> 00:03:27,855
>> Joten koska hajautusfunktio, aiomme
hash sana, joka luemme

62
00:03:27,855 --> 00:03:31,700
sanakirjasta ja sitten menemme
käyttää, että on lisätä

63
00:03:31,700 --> 00:03:33,750
tuloa tiiviste.

64
00:03:33,750 --> 00:03:38,830
Nyt hashtable hash on nykyinen
linkitetty lista on tiiviste, ja

65
00:03:38,830 --> 00:03:41,410
se on hyvin mahdollista, että on vain NULL.

66
00:03:41,410 --> 00:03:45,640
Haluamme lisätä meidän käännyttämiseksi
Alussa tämän linkitetyn listan, ja niin

67
00:03:45,640 --> 00:03:48,910
aiomme olla meidän nykyisen merkinnän
osoittavat johonkin tiiviste hetkellä

68
00:03:48,910 --> 00:03:54,030
pistettä ja sitten aiomme säilyttää
hash pöytä hash

69
00:03:54,030 --> 00:03:55,350
Nykyisen tiedon.

70
00:03:55,350 --> 00:03:59,320
>> Joten nämä kaksi riviä onnistuneesti aseta
merkintä alussa

71
00:03:59,320 --> 00:04:02,270
linkitetty lista tuohon hakemisto
vuonna tiiviste.

72
00:04:02,270 --> 00:04:04,900
Kun olemme tehneet, että me tiedämme
että löysimme toinen sana

73
00:04:04,900 --> 00:04:07,800
sanakirja ja me kasvattaa uudelleen.

74
00:04:07,800 --> 00:04:13,960
Joten meidän pitää tehdä, että kunnes fscanf
lopulta palaa jotain ei 1 at

75
00:04:13,960 --> 00:04:18,560
missä vaiheessa muistaa, että meidän täytyy
vapaa pääsy, joten tänne, me malloced

76
00:04:18,560 --> 00:04:21,329
maahantulon ja yritimme lukea jotain
sanakirjasta.

77
00:04:21,329 --> 00:04:24,110
Ja emme onnistuttiin lukemaan
jotain sanakirjasta, jossa

78
00:04:24,110 --> 00:04:27,440
tapauksessa meidän täytyy vapauttaa merkintä, että me
koskaan itse laittaa tiiviste

79
00:04:27,440 --> 00:04:29,110
ja lopulta purkaa.

80
00:04:29,110 --> 00:04:32,750
>> Kun me puhkeaa, meidän täytyy nähdä, hyvin,
me puhkeaa, koska siellä

81
00:04:32,750 --> 00:04:35,840
oli virhe luettaessa tiedostoa tai
me puhkeaa koska pääsimme

82
00:04:35,840 --> 00:04:37,120
tiedoston loppuun?

83
00:04:37,120 --> 00:04:40,150
Jos oli virhe, niin haluamme
palauttaa false, koska kuormitus ei

84
00:04:40,150 --> 00:04:43,260
menestyä, ja prosessi, haluamme
purkaa kaikki sanat, jotka luemme

85
00:04:43,260 --> 00:04:45,670
ja lähellä sanastotiedostoa.

86
00:04:45,670 --> 00:04:48,740
Olettaen emme onnistu, sitten me vain
vielä sulkea sanakirja

87
00:04:48,740 --> 00:04:51,970
tiedostoon, ja lopulta palata totta, sillä
olemme ladattu onnistuneesti

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

89
00:04:53,040 --> 00:04:54,420
Ja se on siinä kuorman.

90
00:04:54,420 --> 00:04:59,020
>> Joten nyt tarkistaa, koska ladattu tiiviste,
aikoo näyttää tältä.

91
00:04:59,020 --> 00:05:02,690
Joten tarkista, se palauttaa bool, joka
tulee ilmoittaa, onko

92
00:05:02,690 --> 00:05:07,530
kulunut-in char * sana, onko
läpäissyt-merkkijono on meidän sanakirja.

93
00:05:07,530 --> 00:05:10,530
Joten jos se on sanakirjassa, jos se on
meidän tiiviste, palaamme

94
00:05:10,530 --> 00:05:13,380
totta, ja jos se ei ole,
palaamme vääriä.

95
00:05:13,380 --> 00:05:17,770
Kun otetaan huomioon tämä kulunut tekstinkäsittelyohjelma, olemme
menossa hash sana.

96
00:05:17,770 --> 00:05:22,020
>> Nyt tärkeintä tunnistaa on
että kuorman, tiesimme, että kaikki

97
00:05:22,020 --> 00:05:25,820
sanat olivat menossa pieniä kirjaimia,
mutta täällä, emme ole niin varma.

98
00:05:25,820 --> 00:05:29,510
Jos me katsomaan meidän hajautusfunktio,
meidän hash-toiminto itse asiassa

99
00:05:29,510 --> 00:05:32,700
on lowercasing kunkin merkin
sanan.

100
00:05:32,700 --> 00:05:37,580
Joten riippumatta arvo
sana, meidän hash funktio on menossa

101
00:05:37,580 --> 00:05:42,270
palata sama indeksi jostain
-arvo on, koska se olisi

102
00:05:42,270 --> 00:05:45,280
palautetaan kokonaan pienillä kirjaimilla
versio sanasta.

103
00:05:45,280 --> 00:05:45,950
Selvä.

104
00:05:45,950 --> 00:05:47,410
>> Niin, että meidän indeksi.

105
00:05:47,410 --> 00:05:49,790
Se tiiviste sanaa.

106
00:05:49,790 --> 00:05:52,940
Nyt tämä silmukka on menossa
liikaa linkitetty lista

107
00:05:52,940 --> 00:05:55,000
joka oli tuohon indeksi.

108
00:05:55,000 --> 00:05:59,630
Joten huomaat olemme alustetaan merkintä
osoittamaan, että indeksiin.

109
00:05:59,630 --> 00:06:03,480
Aiomme jatkaa samalla merkintä ei
ole yhtä NULL, ja muistaa, että

110
00:06:03,480 --> 00:06:08,350
päivittäminen osoitin meidän linkitetty lista
entry vastaa entry-> seuraava, niin on

111
00:06:08,350 --> 00:06:13,840
nykyinen alkupisteestä
Esityslistalla on linkitetty lista.

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

113
00:06:14,400 --> 00:06:19,150
>> Joten jokaisen merkinnän linkitetty lista,
aiomme käyttää strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Se ei ole strcmp koska jälleen kerran, me
haluavat tehdä asioita tapauksessa insensitively.

115
00:06:23,780 --> 00:06:28,830
Joten käytämme strcasecmp vertailla sana
joka hyväksyttiin tämän toiminnon

116
00:06:28,830 --> 00:06:31,860
vastaan ​​sana, joka
on tämä merkintä.

117
00:06:31,860 --> 00:06:35,570
Jos se palaa 0, se tarkoittaa, että oli
ottelu, jolloin haluamme

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

119
00:06:36,630 --> 00:06:39,590
Olemme löytäneet
sana meidän tiiviste.

120
00:06:39,590 --> 00:06:43,040
>> Jos ei ole ottelu, niin olemme
menossa silmukka uudelleen ja katsoa

121
00:06:43,040 --> 00:06:43,990
seuraava merkintä.

122
00:06:43,990 --> 00:06:47,640
Ja jatkamme silmukoiminen vaikka
ovat merkintöjä tähän linkitetty lista.

123
00:06:47,640 --> 00:06:50,160
Mitä tapahtuu, jos rikomme
pois tästä silmukan?

124
00:06:50,160 --> 00:06:55,110
Tämä tarkoittaa emme löytäneet merkinnän, joka
Hyväksytty tämä sana, jolloin

125
00:06:55,110 --> 00:07:00,220
palaamme epätosi ilmaisten, että
hash-taulukko ei sisällä tätä sanaa.

126
00:07:00,220 --> 00:07:01,910
Ja siinä se lähtöselvitykseen.

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

128
00:07:02,540 --> 00:07:04,790
>> Joten katsotaanpa katsomaan koko.

129
00:07:04,790 --> 00:07:09,280
Nyt koko tulee olemaan melko yksinkertainen
koska muistan kuorman, jokaista sanaa

130
00:07:09,280 --> 00:07:12,880
löysimme me kasvatetaan maailmanlaajuisen
muuttuja hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Joten koko toiminto on vain
aio palata, että maailmanlaajuinen

132
00:07:15,830 --> 00:07:18,150
muuttuja, ja se on siinä.

133
00:07:18,150 --> 00:07:22,300
>> Nyt vihdoin, meidän täytyy purkaa
sanakirjassa kerran kaiken tehtyä.

134
00:07:22,300 --> 00:07:25,340
Niin miten me sen teemme?

135
00:07:25,340 --> 00:07:30,440
Juuri täällä, me silmukoiden yli kaiken
ämpärillistä meidän tiiviste.

136
00:07:30,440 --> 00:07:33,240
Joten on NUM_BUCKETS kauhat.

137
00:07:33,240 --> 00:07:37,490
Ja kunkin linkitetyn listan meidän hash
pöytä, aiomme lenkki

138
00:07:37,490 --> 00:07:41,070
kokonaisuudessaan linkitetyn listan
vapauttaa jokaisen elementin.

139
00:07:41,070 --> 00:07:46,070
Nyt meidän on oltava varovaisia, joten tässä me
on väliaikainen muuttuja, joka on

140
00:07:46,070 --> 00:07:49,740
tallennetaan osoitin seuraavaan
elementti linkitetty lista.

141
00:07:49,740 --> 00:07:52,140
Ja sitten me aiomme ilmaiseksi
elementin.

142
00:07:52,140 --> 00:07:55,990
>> Meidän on oltava varmoja teemme tämän, koska meillä
voi vain vapauttaa elementin

143
00:07:55,990 --> 00:07:59,260
ja yritä sitten käyttää seuraavaan osoitin
sillä kun me vapautettu, sitä

144
00:07:59,260 --> 00:08:00,870
muisti mitätöityy.

145
00:08:00,870 --> 00:08:04,990
Joten meidän täytyy pitää noin osoitin
seuraavan osan, voimme vapauttaa

146
00:08:04,990 --> 00:08:08,360
elementin, ja sitten voimme päivittää
nykyinen elementti osoittamaan

147
00:08:08,360 --> 00:08:09,590
seuraavan osan.

148
00:08:09,590 --> 00:08:12,770
>> Me silmukka, kun on olemassa tekijöitä,
Tässä linkitetty lista.

149
00:08:12,770 --> 00:08:16,450
Teemme että kaikilla yhdistetyillä luettelot
tiiviste, ja kun olemme tehneet

150
00:08:16,450 --> 00:08:20,180
kanssa, että olemme täysin purettu
tiiviste, ja olemme valmiit.

151
00:08:20,180 --> 00:08:24,050
Joten se on mahdotonta kurmittamattomuuksiin koskaan
palauttaa false, ja kun olemme tehneet, me

152
00:08:24,050 --> 00:08:25,320
vain palata totta.

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