1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:01,900
[MUSIC SPILLE]

3
00:00:01,900 --> 00:00:05,710

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Nå har du
vet mye om matriser,

5
00:00:09,150 --> 00:00:11,610
og du vet mye om lenkede lister.

6
00:00:11,610 --> 00:00:13,650
Og vi har diskutere
argumenter for og imot, har vi

7
00:00:13,650 --> 00:00:16,620
diskutert som knyttet lister
kan få større og mindre,

8
00:00:16,620 --> 00:00:18,630
men de tar opp mer størrelse.

9
00:00:18,630 --> 00:00:22,359
Arrays er mye mer oversiktlig å
bruke, men de er restriktive i så mye

10
00:00:22,359 --> 00:00:24,900
som vi har til å angi størrelsen på
rekken helt i begynnelsen

11
00:00:24,900 --> 00:00:26,910
og da er vi stuck med det.

12
00:00:26,910 --> 00:00:30,470
>> Men det er, vi har ganske mye
brukt opp alle våre emner

13
00:00:30,470 --> 00:00:33,040
om lenkede lister og matriser.

14
00:00:33,040 --> 00:00:34,950
Eller har vi?

15
00:00:34,950 --> 00:00:37,720
Kanskje vi kan gjøre noe
enda mer kreativ.

16
00:00:37,720 --> 00:00:40,950
Og den slags låner
ideen om en hash table.

17
00:00:40,950 --> 00:00:46,680
>> Så i en hash table skal vi prøve
kombinere en matrise med en lenket liste.

18
00:00:46,680 --> 00:00:49,520
Vi kommer til å ta fordelene
i matrisen, slik tilfeldig tilgang,

19
00:00:49,520 --> 00:00:53,510
å kunne bare gå til matrise
element 4 eller array element 8

20
00:00:53,510 --> 00:00:55,560
uten å iterere over.

21
00:00:55,560 --> 00:00:57,260
Det er ganske fort, ikke sant?

22
00:00:57,260 --> 00:01:00,714
>> Men vi ønsker også å ha våre data
strukturen være i stand til å vokse og krympe.

23
00:01:00,714 --> 00:01:02,630
Vi trenger ikke, gjør vi ikke
ønsker å være begrenset.

24
00:01:02,630 --> 00:01:04,588
Og vi ønsker å kunne
å legge til og fjerne ting

25
00:01:04,588 --> 00:01:08,430
veldig lett, som om du husker,
er meget komplisert med en matrise.

26
00:01:08,430 --> 00:01:11,650
Og vi kan kalle dette
ny ting en hash table.

27
00:01:11,650 --> 00:01:15,190
>> Og hvis implementert riktig,
vi liksom ta

28
00:01:15,190 --> 00:01:18,150
fordelene ved begge data
strukturer du allerede har sett,

29
00:01:18,150 --> 00:01:19,880
arrays og koblede lister.

30
00:01:19,880 --> 00:01:23,070
Innsetting kan begynne å
tenderer mot theta av en.

31
00:01:23,070 --> 00:01:26,207
Theta vi har egentlig ikke diskutert,
men theta er bare den gjennomsnittlige tilfellet

32
00:01:26,207 --> 00:01:27,540
hva som faktisk kommer til å skje.

33
00:01:27,540 --> 00:01:29,680
Du er ikke alltid kommer til å
har worst case scenario,

34
00:01:29,680 --> 00:01:32,555
og du ikke alltid kommer til å ha
best case scenario, så hva er

35
00:01:32,555 --> 00:01:33,900
gjennomsnittlig scenario?

36
00:01:33,900 --> 00:01:36,500
>> Vel en gjennomsnittlig innsetting
inn i en hash table

37
00:01:36,500 --> 00:01:39,370
kan begynne å komme nær konstant tid.

38
00:01:39,370 --> 00:01:41,570
Og sletting kan få
nær konstant tid.

39
00:01:41,570 --> 00:01:44,440
Og oppslag kan få
nær konstant tid.

40
00:01:44,440 --> 00:01:48,600
That's-- vi ikke har en data
struktur ennå som kan gjøre det,

41
00:01:48,600 --> 00:01:51,180
og så dette allerede høres
som en ganske stor ting.

42
00:01:51,180 --> 00:01:57,010
Vi har virkelig dempet
Ulempene ved hver for seg.

43
00:01:57,010 --> 00:01:59,160
>> For å få denne ytelsen
oppgradere skjønt, vi

44
00:01:59,160 --> 00:02:03,580
trenger å tenke gjennom hvordan vi legger til
data inn i strukturen.

45
00:02:03,580 --> 00:02:07,380
Spesielt ønsker vi at
data i seg selv til å fortelle oss

46
00:02:07,380 --> 00:02:09,725
hvor den skal gå i strukturen.

47
00:02:09,725 --> 00:02:12,850
Og hvis vi da trenger å se om det er i
strukturen, hvis vi trenger å finne det,

48
00:02:12,850 --> 00:02:16,610
vi ønsker å se på data
igjen og være i stand til å effektivt,

49
00:02:16,610 --> 00:02:18,910
ved hjelp av data, tilfeldig tilgang til den.

50
00:02:18,910 --> 00:02:20,700
Bare ved å se på
data vi bør ha

51
00:02:20,700 --> 00:02:25,890
en idé om hvor vi er
kommer til å finne den i hash tabellen.

52
00:02:25,890 --> 00:02:28,770
>> Nå ulemper av en hash
Tabellen er at de er veldig

53
00:02:28,770 --> 00:02:31,770
ganske dårlig på bestilling eller sortering av data.

54
00:02:31,770 --> 00:02:34,970
Og faktisk, hvis du starter
å bruke dem til å bestille eller sort

55
00:02:34,970 --> 00:02:37,990
data du mister alt av
fordeler du tidligere

56
00:02:37,990 --> 00:02:40,710
hadde i form av innsetting og sletting.

57
00:02:40,710 --> 00:02:44,060
Tiden blir nærmere
theta av n, og vi har i utgangspunktet

58
00:02:44,060 --> 00:02:45,530
tilbakegang i en lenket liste.

59
00:02:45,530 --> 00:02:48,850
Og så vi bare ønsker å bruke hasj
tabeller hvis vi ikke bryr oss om

60
00:02:48,850 --> 00:02:51,490
om data blir sortert.

61
00:02:51,490 --> 00:02:54,290
For i hvilken sammenheng
du vil bruke dem i CS50

62
00:02:54,290 --> 00:02:58,900
du sannsynligvis ikke bryr seg
at dataene er sortert.

63
00:02:58,900 --> 00:03:03,170
>> Så en hash table er en kombinasjon
av to atskilte stykker

64
00:03:03,170 --> 00:03:04,980
som vi er kjent.

65
00:03:04,980 --> 00:03:07,930
Den første er en funksjon, hvilken
vi vanligvis kaller en hash-funksjon.

66
00:03:07,930 --> 00:03:11,760
Og at hash funksjon skal
returnere en ikke-negativt heltall, som

67
00:03:11,760 --> 00:03:14,870
vi vanligvis kaller en hashCode, OK?

68
00:03:14,870 --> 00:03:20,230
Den andre delen er en matrise, som er
i stand til å lagre data av den type vi

69
00:03:20,230 --> 00:03:22,190
ønsker å plassere i datastrukturen.

70
00:03:22,190 --> 00:03:24,310
Vi vil holde ut på
lenket liste element for nå

71
00:03:24,310 --> 00:03:27,810
og bare begynne med det grunnleggende av en
hash table å få hodet rundt det,

72
00:03:27,810 --> 00:03:30,210
og så får vi kanskje blåse
tankene dine litt når vi

73
00:03:30,210 --> 00:03:32,920
kombinere arrays og link lister sammen.

74
00:03:32,920 --> 00:03:35,590
>> Den grunnleggende ideen om
er vi ta noen data.

75
00:03:35,590 --> 00:03:37,860
Vi kjører som data gjennom
hash-funksjon.

76
00:03:37,860 --> 00:03:41,980
Og slik at dataene blir prosessert
og det spytter ut et tall, OK?

77
00:03:41,980 --> 00:03:44,890
Og deretter med det nummeret
vi bare lagre data

78
00:03:44,890 --> 00:03:48,930
vi ønsker å lagre i
matrise på det stedet.

79
00:03:48,930 --> 00:03:53,990
Så for eksempel har vi kanskje
dette hash table av strenger.

80
00:03:53,990 --> 00:03:57,350
Det har 10 elementer i det, så
vi kan passe 10 strenger i den.

81
00:03:57,350 --> 00:03:59,320
>> La oss si at vi ønsker å hash John.

82
00:03:59,320 --> 00:04:02,979
Så John som data vi ønsker å sette inn
inn i denne hash table et sted.

83
00:04:02,979 --> 00:04:03,770
Der setter vi det?

84
00:04:03,770 --> 00:04:05,728
Vel typisk med en
rekke så langt vi sannsynligvis

85
00:04:05,728 --> 00:04:07,610
ville sette den i matrisen plassering 0.

86
00:04:07,610 --> 00:04:09,960
Men nå har vi denne nye hash-funksjon.

87
00:04:09,960 --> 00:04:13,180
>> Og la oss si at vi kjører John
gjennom denne hash-funksjon

88
00:04:13,180 --> 00:04:15,417
og det spytter ut 4.

89
00:04:15,417 --> 00:04:17,500
Vel det er der vi er
kommer til å ønske å sette John.

90
00:04:17,500 --> 00:04:22,050
Vi ønsker å sette John i matrise plassering
4, fordi hvis vi hasj John igjen--

91
00:04:22,050 --> 00:04:23,810
la oss si senere vi
ønsker å søke og se

92
00:04:23,810 --> 00:04:26,960
Hvis John eksisterer i denne hash
table-- alt vi trenger å gjøre

93
00:04:26,960 --> 00:04:30,310
kjøres det gjennom den samme hash
funksjon, få nummer 4 ut,

94
00:04:30,310 --> 00:04:33,929
og være i stand til å finne John
umiddelbart i vår datastruktur.

95
00:04:33,929 --> 00:04:34,720
Det er ganske bra.

96
00:04:34,720 --> 00:04:36,928
>> La oss si at vi nå gjør dette
igjen, vil vi til hasj Paul.

97
00:04:36,928 --> 00:04:39,446
Vi ønsker å legge til Paul
inn i denne hash table.

98
00:04:39,446 --> 00:04:42,070
La oss si at denne gangen vi kjører
Paul gjennom hash-funksjon,

99
00:04:42,070 --> 00:04:44,600
den hashCode som er generert er seks.

100
00:04:44,600 --> 00:04:47,340
Vel, nå kan vi sette Paul
i matrisen plassering 6.

101
00:04:47,340 --> 00:04:50,040
Og hvis vi trenger å slå opp om
Paul er i denne hash table,

102
00:04:50,040 --> 00:04:53,900
alt vi trenger å gjøre er å kjøre Paul
gjennom hash funksjonen igjen

103
00:04:53,900 --> 00:04:55,830
og vi kommer til å få seks ut igjen.

104
00:04:55,830 --> 00:04:57,590
>> Og så ser vi bare
på rekke plassering 6.

105
00:04:57,590 --> 00:04:58,910
Er Paul der?

106
00:04:58,910 --> 00:05:00,160
I så fall er han i hash tabellen.

107
00:05:00,160 --> 00:05:01,875
Er Paul ikke det?

108
00:05:01,875 --> 00:05:03,000
Han er ikke i hash tabellen.

109
00:05:03,000 --> 00:05:05,720
Det er ganske grei.

110
00:05:05,720 --> 00:05:07,770
>> Nå hvordan vil du definere en hash-funksjon?

111
00:05:07,770 --> 00:05:11,460
Vel det er egentlig ingen grense for
antallet mulige hash-funksjoner.

112
00:05:11,460 --> 00:05:14,350
Faktisk er det en rekke virkelig,
virkelig gode på internett.

113
00:05:14,350 --> 00:05:17,560
Det finnes en rekke virkelig,
virkelig dårlige seg på internett.

114
00:05:17,560 --> 00:05:21,080
Det er også ganske enkelt
å skrive en dårlig en.

115
00:05:21,080 --> 00:05:23,760
>> Så hva gjør opp en god
hash-funksjon, ikke sant?

116
00:05:23,760 --> 00:05:27,280
Vel en god hash-funksjon skal
bruker bare dataene som hashet,

117
00:05:27,280 --> 00:05:29,420
og alle data blir hashet.

118
00:05:29,420 --> 00:05:32,500
Så vi ikke ønsker å bruke anything--
vi ikke innlemme noe

119
00:05:32,500 --> 00:05:35,560
annet enn dataene.

120
00:05:35,560 --> 00:05:37,080
Og vi ønsker å bruke alle data.

121
00:05:37,080 --> 00:05:39,830
Vi ønsker ikke å bare bruke et stykke
av det, vi ønsker å bruke alt sammen.

122
00:05:39,830 --> 00:05:41,710
En hash-funksjon skal
også være deterministisk.

123
00:05:41,710 --> 00:05:42,550
Hva betyr det?

124
00:05:42,550 --> 00:05:46,200
Vel det betyr at hver gang vi
passere nøyaktig samme stykke data

125
00:05:46,200 --> 00:05:50,040
inn i hash-funksjon vi alltid
få samme hashCode ut.

126
00:05:50,040 --> 00:05:52,870
Hvis jeg passerer John inn i
hash-funksjon jeg kommer ut fire.

127
00:05:52,870 --> 00:05:56,110
Jeg burde være i stand til å gjøre det 10000
ganger, og jeg får alltid fire.

128
00:05:56,110 --> 00:06:00,810
Så ingen tilfeldige tall effektivt
kan være involvert i vår hash tables--

129
00:06:00,810 --> 00:06:02,750
i våre hash funksjoner.

130
00:06:02,750 --> 00:06:05,750
>> En hash-funksjon bør også
jevnt distribuere data.

131
00:06:05,750 --> 00:06:09,700
Hvis hver gang du kjører data gjennom
hash-funksjon du får hashCode 0,

132
00:06:09,700 --> 00:06:11,200
det er nok ikke så bra, ikke sant?

133
00:06:11,200 --> 00:06:14,600
Du sannsynligvis vil stort
et utvalg av hash-koder.

134
00:06:14,600 --> 00:06:17,190
Også ting kan spre seg
ut gjennom hele tabellen.

135
00:06:17,190 --> 00:06:23,210
Og også det ville være flott om virkelig
tilsvarende data, som John og Jonathan,

136
00:06:23,210 --> 00:06:26,320
kanskje ble spredt til veie
forskjellige steder i hash table.

137
00:06:26,320 --> 00:06:28,750
Det ville være en fin fordel.

138
00:06:28,750 --> 00:06:31,250
>> Her er et eksempel på en hash-funksjon.

139
00:06:31,250 --> 00:06:33,150
Jeg skrev dette opp tidligere.

140
00:06:33,150 --> 00:06:35,047
Det er ikke en spesielt
god hash-funksjon

141
00:06:35,047 --> 00:06:37,380
av grunner som ikke egentlig
bjørn kommer inn akkurat nå.

142
00:06:37,380 --> 00:06:41,040
Men ser du hva som skjer her?

143
00:06:41,040 --> 00:06:44,420
Det virker som om vi erklære en variabel
kalles sum- og sette den lik 0.

144
00:06:44,420 --> 00:06:50,010
Og så tilsynelatende jeg gjør noe
så lenge som strstr [j] er ikke lik

145
00:06:50,010 --> 00:06:52,490
til backslash 0.

146
00:06:52,490 --> 00:06:54,870
Hva gjør jeg det?

147
00:06:54,870 --> 00:06:57,440
>> Dette er i utgangspunktet bare en annen
måte å implementere [? strl?]

148
00:06:57,440 --> 00:06:59,773
og oppdager når du har
kommet til slutten av strengen.

149
00:06:59,773 --> 00:07:02,480
Så jeg trenger ikke å faktisk
beregne lengden av strengen,

150
00:07:02,480 --> 00:07:05,640
Jeg bare bruker når jeg treffer
backslash 0 karakteren jeg vet

151
00:07:05,640 --> 00:07:07,185
Jeg har nådd slutten av strengen.

152
00:07:07,185 --> 00:07:09,560
Og så kommer jeg til å holde
itera gjennom strengen,

153
00:07:09,560 --> 00:07:15,310
legge strstr [j] for å oppsummere, og deretter på
slutten av dagen kommer til å returnere sum mod

154
00:07:15,310 --> 00:07:16,200
HASH_MAX.

155
00:07:16,200 --> 00:07:18,700
>> I utgangspunktet er alt dette hash
funksjonen gjør er å legge opp

156
00:07:18,700 --> 00:07:23,450
alle verdier av ASCII
min streng, og da er det

157
00:07:23,450 --> 00:07:26,390
returnere en hashCode
modded av HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Det er sannsynligvis størrelsen
av min array, ikke sant?

159
00:07:29,790 --> 00:07:33,160
Jeg ønsker ikke å være å få hasj
koder hvis mitt utvalg er av størrelse 10,

160
00:07:33,160 --> 00:07:35,712
Jeg ønsker ikke å være å få
ut hash-koder 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, jeg kan ikke sette ting i
de steder på matrisen,

162
00:07:38,690 --> 00:07:39,790
det ville være ulovlig.

163
00:07:39,790 --> 00:07:42,130
Jeg ville lide en segmentering feil.

164
00:07:42,130 --> 00:07:45,230
>> Nå her er en annen rask til side.

165
00:07:45,230 --> 00:07:48,470
Vanligvis er du sannsynligvis ikke kommer til å
ønsker å skrive dine egne hash funksjoner.

166
00:07:48,470 --> 00:07:50,997
Det er faktisk litt av
en kunst, ikke en vitenskap.

167
00:07:50,997 --> 00:07:52,580
Og det er mye som går inn i dem.

168
00:07:52,580 --> 00:07:55,288
Internett, som jeg sa, er full
av virkelig god hash funksjoner,

169
00:07:55,288 --> 00:07:58,470
og du bør bruke internett til å
finne hash funksjoner fordi det er virkelig

170
00:07:58,470 --> 00:08:03,230
bare slags en unødvendig
bortkastet tid å lage dine egne.

171
00:08:03,230 --> 00:08:05,490
>> Du kan skrive enkle seg
for testformål.

172
00:08:05,490 --> 00:08:08,323
Men når du faktisk kommer til å
starte hashing data og lagre den

173
00:08:08,323 --> 00:08:10,780
inn i en hash table du er
sannsynligvis kommer til å ønske

174
00:08:10,780 --> 00:08:14,580
å bruke noen funksjon som ble generert
for deg, finnes det på internett.

175
00:08:14,580 --> 00:08:17,240
Hvis du bare være sikker
å sitere kilder.

176
00:08:17,240 --> 00:08:21,740
Det er ingen grunn til å
plagiere noe her.

177
00:08:21,740 --> 00:08:25,370
>> Informatikk samfunnet er
definitivt vokser, og virkelig verdier

178
00:08:25,370 --> 00:08:28,796
åpen kildekode, og det er veldig viktig
å sitere kilder, slik at folk

179
00:08:28,796 --> 00:08:30,670
kan få henvisning til
det arbeidet som de er

180
00:08:30,670 --> 00:08:32,312
gjør til beste for fellesskapet.

181
00:08:32,312 --> 00:08:34,020
Så alltid være sure--
og ikke bare for hasj

182
00:08:34,020 --> 00:08:37,270
funksjoner, men vanligvis når
bruke kode fra en ekstern kilde,

183
00:08:37,270 --> 00:08:38,299
alltid sitere kilden.

184
00:08:38,299 --> 00:08:43,500
Gi kreditt til den personen som gjorde
noe av arbeidet slik at du ikke må.

185
00:08:43,500 --> 00:08:46,720
>> OK så la oss se dette
hash table for et sekund.

186
00:08:46,720 --> 00:08:48,780
Det er der vi igjen
av etter at vi satt inn

187
00:08:48,780 --> 00:08:53,300
John og Paul i denne hash table.

188
00:08:53,300 --> 00:08:55,180
Ser du et problem her?

189
00:08:55,180 --> 00:08:58,410
Du kan se to.

190
00:08:58,410 --> 00:09:02,240
Men spesielt, gjør du
se dette mulig problem?

191
00:09:02,240 --> 00:09:06,770
>> Hva om jeg hasj Ringo, og det
viser seg at etter behandlingen

192
00:09:06,770 --> 00:09:14,000
at data gjennom hash-funksjon
Ringo også genererte hashCode 6.

193
00:09:14,000 --> 00:09:16,810
Jeg har allerede fått data på
hashcode-- rekke plassering 6.

194
00:09:16,810 --> 00:09:22,000
Så det er trolig kommer til å være litt
av et problem for meg nå, ikke sant?

195
00:09:22,000 --> 00:09:23,060
>> Vi kaller dette en kollisjon.

196
00:09:23,060 --> 00:09:26,460
Og kollisjonen oppstår når to
biter av data kjøres gjennom den samme hash

197
00:09:26,460 --> 00:09:29,200
Funksjonen gi samme hashCode.

198
00:09:29,200 --> 00:09:32,850
Antagelig vi ønsker fortsatt å få både
biter av data inn i hash table,

199
00:09:32,850 --> 00:09:36,330
ellers ville vi ikke kjøre Ringo
vilkårlig gjennom hash-funksjon.

200
00:09:36,330 --> 00:09:40,870
Vi vil antakelig for å få
Ringo inn i denne matrisen.

201
00:09:40,870 --> 00:09:46,070
>> Hvordan skal vi gjøre det selv, hvis han
og Paul både avkastning hashCode 6?

202
00:09:46,070 --> 00:09:49,520
Vi ønsker ikke å overskrive Paul,
vi ønsker Paul å være der også.

203
00:09:49,520 --> 00:09:52,790
Så vi må finne en måte å få
elementer inn i hash tabellen som

204
00:09:52,790 --> 00:09:56,550
fortsatt bevarer vår raske
innsetting og rask titt opp.

205
00:09:56,550 --> 00:10:01,350
Og en måte å håndtere det er å
gjøre noe som kalles lineær sondering.

206
00:10:01,350 --> 00:10:04,170
>> Ved hjelp av denne metoden hvis vi har en
kollisjon, vel, hva gjør vi?

207
00:10:04,170 --> 00:10:08,580
Vel, vi kan ikke sette ham i matrisen plassering
6, eller hva hashCode ble generert,

208
00:10:08,580 --> 00:10:10,820
la oss sette ham på hashCode pluss 1.

209
00:10:10,820 --> 00:10:13,670
Og hvis det er fullt la oss
satte ham i hashCode pluss to.

210
00:10:13,670 --> 00:10:17,420
Fordelen med dette vesenet om han er
ikke akkurat der vi tror han er,

211
00:10:17,420 --> 00:10:20,850
og vi må begynne å søke,
kanskje vi ikke trenger å gå for langt.

212
00:10:20,850 --> 00:10:23,900
Kanskje vi ikke trenger å søke
alle n elementene i nøkkeltabell.

213
00:10:23,900 --> 00:10:25,790
Kanskje vi må søke
et par av dem.

214
00:10:25,790 --> 00:10:30,680
>> Og så vi er fortsatt tenderer mot
at gjennomsnittlig saks være nær en vs

215
00:10:30,680 --> 00:10:34,280
nær n, så kanskje det vil fungere.

216
00:10:34,280 --> 00:10:38,010
Så la oss se hvordan dette
kunne arbeide ut i virkeligheten.

217
00:10:38,010 --> 00:10:41,460
Og la oss se om vi kanskje kan oppdage
problemet som kan oppstå her.

218
00:10:41,460 --> 00:10:42,540
>> La oss si at vi hash Bart.

219
00:10:42,540 --> 00:10:45,581
Så nå skal vi kjøre et nytt sett
strenger gjennom hash-funksjon,

220
00:10:45,581 --> 00:10:48,460
og vi kjører Bart gjennom hash
funksjon, får vi hashCode 6.

221
00:10:48,460 --> 00:10:52,100
Vi tar en titt, ser vi 6 er
tomt, så vi kan sette Bart der.

222
00:10:52,100 --> 00:10:55,410
>> Nå hash vi Lisa og at
genererer også hashCode 6.

223
00:10:55,410 --> 00:10:58,330
Vel nå at vi bruker denne
lineær sondering metoden vi starter på 6,

224
00:10:58,330 --> 00:10:59,330
Vi ser at 6 er full.

225
00:10:59,330 --> 00:11:00,990
Vi kan ikke sette Lisa i 6.

226
00:11:00,990 --> 00:11:02,090
Så hvor går vi?

227
00:11:02,090 --> 00:11:03,280
La oss gå til syv.

228
00:11:03,280 --> 00:11:04,610
7-er tom, så det fungerer.

229
00:11:04,610 --> 00:11:06,510
Så la oss sette Lisa der.

230
00:11:06,510 --> 00:11:10,200
>> Nå hash vi Homer og vi får 7.

231
00:11:10,200 --> 00:11:13,380
OK godt vi vet at syv fulle
nå, slik at vi ikke kan sette Homer der.

232
00:11:13,380 --> 00:11:14,850
Så la oss gå til åtte.

233
00:11:14,850 --> 00:11:15,664
Er 8 tilgjengelig?

234
00:11:15,664 --> 00:11:18,330
Ja, og 8 er nær 7, så hvis
vi må begynne å søke vi er

235
00:11:18,330 --> 00:11:20,020
ikke nødt til å gå for langt.

236
00:11:20,020 --> 00:11:22,860
Og så la oss sette Homer på åtte.

237
00:11:22,860 --> 00:11:25,151
>> Nå hash vi Maggie og
returnerer 3, takk og lov

238
00:11:25,151 --> 00:11:26,650
vi er i stand til å bare sette Maggie der.

239
00:11:26,650 --> 00:11:29,070
Vi trenger ikke å gjøre noe
slags sondering for det.

240
00:11:29,070 --> 00:11:32,000
Nå hash vi Marge, og
Marge returnerer også 6.

241
00:11:32,000 --> 00:11:39,560
>> Vel 6 er full, 7 er fullt, 8 er full,
9, greit takk Gud, 9 er tom.

242
00:11:39,560 --> 00:11:41,600
Jeg kan sette Marge på ni.

243
00:11:41,600 --> 00:11:45,280
Allerede ser vi at vi begynner
å ha dette problemet der nå er vi

244
00:11:45,280 --> 00:11:48,780
begynner å strekke ting slag
for langt borte fra sine hash-koder.

245
00:11:48,780 --> 00:11:52,960
Og at theta av en, som gjennomsnittlig
Ved å være konstant tid,

246
00:11:52,960 --> 00:11:56,560
begynner å bli litt mer--
begynner å tendens litt mer

247
00:11:56,560 --> 00:11:58,050
mot theta av n.

248
00:11:58,050 --> 00:12:01,270
Vi begynner å miste den
nytte av hasj tabeller.

249
00:12:01,270 --> 00:12:03,902
>> Dette problemet som vi nettopp så
er noe som heter clustering.

250
00:12:03,902 --> 00:12:06,360
Og hva er virkelig ille om
clustering er at når du nå

251
00:12:06,360 --> 00:12:09,606
har to elementer som er side etter
side det gjør det enda mer sannsynlig,

252
00:12:09,606 --> 00:12:11,480
du har dobbelt
sjanse, at du kommer

253
00:12:11,480 --> 00:12:13,516
å ha en annen kollisjon
med at klyngen,

254
00:12:13,516 --> 00:12:14,890
og klyngen vil vokse med en.

255
00:12:14,890 --> 00:12:19,640
Og du vil holde vokser og vokser
sannsynligheten for å ha en kollisjon.

256
00:12:19,640 --> 00:12:24,470
Og til slutt er det like ille
som ikke sortering av data i det hele tatt.

257
00:12:24,470 --> 00:12:27,590
>> Det andre problemet er om vi
fortsatt, og så langt opp til dette punktet,

258
00:12:27,590 --> 00:12:30,336
Vi har nettopp vært slags
forstå hva en hash table er,

259
00:12:30,336 --> 00:12:31,960
vi fortsatt bare har plass til 10 strenger.

260
00:12:31,960 --> 00:12:37,030
Hvis vi ønsker å fortsette til hasj
innbyggerne i Springfield,

261
00:12:37,030 --> 00:12:38,790
vi kan bare få 10 av dem i det.

262
00:12:38,790 --> 00:12:42,619
Og hvis vi prøver og legge til en 11. eller 12.,
vi ikke har et sted å sette dem.

263
00:12:42,619 --> 00:12:45,660
Vi kunne bare spinne rundt i
sirkler prøver å finne et tomt sted,

264
00:12:45,660 --> 00:12:49,000
og vi kanskje får problemer
i en uendelig loop.

265
00:12:49,000 --> 00:12:51,810
>> Så denne typen låner til ideen
av noe som kalles kjeding.

266
00:12:51,810 --> 00:12:55,790
Og det er her vi kommer til å bringe
lenkede lister tilbake inn i bildet.

267
00:12:55,790 --> 00:13:01,300
Hva om i stedet for å lagre bare
selve dataene i tabellen,

268
00:13:01,300 --> 00:13:04,471
hvert element i gruppen kunne
holde flere biter av data?

269
00:13:04,471 --> 00:13:05,970
Vel det ikke gir mening, ikke sant?

270
00:13:05,970 --> 00:13:09,280
Vi vet at en rekke kan bare
hold-- hvert element i en matrise

271
00:13:09,280 --> 00:13:12,930
kan kun ha en brikke
av dataene på den datatype.

272
00:13:12,930 --> 00:13:16,750
>> Men hva om den datatypen
er en lenket liste, ikke sant?

273
00:13:16,750 --> 00:13:19,830
Så hva om hver
element i gruppen var

274
00:13:19,830 --> 00:13:22,790
en peker til hodet på en lenket liste?

275
00:13:22,790 --> 00:13:24,680
Og så kan vi bygge
disse koblede lister

276
00:13:24,680 --> 00:13:27,120
og vokse dem vilkårlig,
fordi lenkede lister tillate

277
00:13:27,120 --> 00:13:32,090
oss å vokse og krympe mye mer
fleksibelt enn en matrise gjør.

278
00:13:32,090 --> 00:13:34,210
Så hva om vi nå bruker,
vi utnytte dette, ikke sant?

279
00:13:34,210 --> 00:13:37,760
Vi begynner å vokse disse kjedene
ut av disse array-stedene.

280
00:13:37,760 --> 00:13:40,740
>> Nå kan vi passer en uendelig
Mengden av data, eller ikke uendelig,

281
00:13:40,740 --> 00:13:44,170
en vilkårlig mengde
data, inn i vårt hash table

282
00:13:44,170 --> 00:13:47,760
uten noen gang å kjøre inn
problemet med kollisjoner.

283
00:13:47,760 --> 00:13:50,740
Vi har også eliminert
clustering ved å gjøre dette.

284
00:13:50,740 --> 00:13:54,380
Og godt vi vet at når vi setter inn
inn i en lenket liste, hvis du husker

285
00:13:54,380 --> 00:13:57,779
fra vår video på lenkede lister, enkeltvis
lenkede lister og dobbelt lenkede lister,

286
00:13:57,779 --> 00:13:59,070
det er en konstant tid operasjon.

287
00:13:59,070 --> 00:14:00,710
Vi er bare å legge til fronten.

288
00:14:00,710 --> 00:14:04,400
>> Og for titt opp, godt vi vet
som ser opp i en lenket liste

289
00:14:04,400 --> 00:14:05,785
kan være et problem, ikke sant?

290
00:14:05,785 --> 00:14:07,910
Vi må søke gjennom
det fra begynnelse til slutt.

291
00:14:07,910 --> 00:14:10,460
Det er ingen tilfeldig
tilgang i en lenket liste.

292
00:14:10,460 --> 00:14:15,610
Men hvis stedet for å ha en koblet
liste der en lookup ville være O av n,

293
00:14:15,610 --> 00:14:19,590
vi nå har 10 lenkede lister,
eller 1000 lenkede lister,

294
00:14:19,590 --> 00:14:24,120
nå er det O n dividert med 10,
eller O n dividert med 1000.

295
00:14:24,120 --> 00:14:26,940
>> Og mens vi snakker
teoretisk om kompleksitet

296
00:14:26,940 --> 00:14:30,061
vi ser bort konstanter, i den virkelige
verden disse tingene faktisk betyr noe,

297
00:14:30,061 --> 00:14:30,560
ikke sant?

298
00:14:30,560 --> 00:14:33,080
Vi har faktisk vil merke
at dette skjer

299
00:14:33,080 --> 00:14:36,610
for å kjøre 10 ganger raskere,
eller 1000 ganger raskere,

300
00:14:36,610 --> 00:14:41,570
fordi vi distribuerer en eneste lang
kjede over 1.000 mindre kjeder.

301
00:14:41,570 --> 00:14:45,090
Og så hver gang vi har til å søke
gjennom en av de kjedene vi kan

302
00:14:45,090 --> 00:14:50,290
ignorere 999 kjeder vi ikke bryr seg
om, og bare søke den.

303
00:14:50,290 --> 00:14:53,220
>> Som er på gjennomsnittet til
være 1000 ganger kortere.

304
00:14:53,220 --> 00:14:56,460
Og så har vi fortsatt er liksom
tenderer mot dette gjennomsnittlig saks

305
00:14:56,460 --> 00:15:01,610
for å være konstant tid, men
bare fordi vi er å utnytte

306
00:15:01,610 --> 00:15:03,730
dividere med noen enorme konstant faktor.

307
00:15:03,730 --> 00:15:05,804
La oss se hvordan dette kan
faktisk ser skjønt.

308
00:15:05,804 --> 00:15:08,720
Så dette var den hash table vi hadde
før vi erklært en hash tabell som

309
00:15:08,720 --> 00:15:10,270
var i stand til å lagre 10 strenger.

310
00:15:10,270 --> 00:15:11,728
Vi kommer ikke til å gjøre det lenger.

311
00:15:11,728 --> 00:15:13,880
Vi vet allerede at
begrensninger av denne metoden.

312
00:15:13,880 --> 00:15:20,170
Nå vår hash table kommer til å bli
en rekke 10 noder, pekere

313
00:15:20,170 --> 00:15:22,120
til hodene på lenkede lister.

314
00:15:22,120 --> 00:15:23,830
>> Og akkurat nå er det null.

315
00:15:23,830 --> 00:15:26,170
Hver og en av de 10 pekere er null.

316
00:15:26,170 --> 00:15:29,870
Det er ingenting i vår
hash table akkurat nå.

317
00:15:29,870 --> 00:15:32,690
>> Nå la oss begynne å sette noen
ting i denne hash table.

318
00:15:32,690 --> 00:15:35,440
Og la oss se hvordan denne metoden er
kommer til nytte for oss litt.

319
00:15:35,440 --> 00:15:36,760
La oss nå hash Joey.

320
00:15:36,760 --> 00:15:40,210
Vi vil vil kjøre strengen Joey gjennom
en hash-funksjon, og vi kommer tilbake 6.

321
00:15:40,210 --> 00:15:41,200
Vel, hva gjør vi nå?

322
00:15:41,200 --> 00:15:44,090
>> Vel nå arbeider med koblede lister,
Vi jobber ikke med arrays.

323
00:15:44,090 --> 00:15:45,881
Og når vi jobber
med koblede lister vi

324
00:15:45,881 --> 00:15:49,790
vet vi må begynne dynamisk
tildeling av plass og byggekjedene.

325
00:15:49,790 --> 00:15:54,020
Det er liksom how-- de er kjernen
elementer for å bygge en lenket liste.

326
00:15:54,020 --> 00:15:57,670
Så la oss dynamisk
tildele plass for Joey,

327
00:15:57,670 --> 00:16:00,390
og så la oss legge ham til kjeden.

328
00:16:00,390 --> 00:16:03,170
>> Så nå ser hva vi har gjort.

329
00:16:03,170 --> 00:16:06,440
Når vi hash Joey vi fikk hashCode 6.

330
00:16:06,440 --> 00:16:11,790
Nå peker på rekke plassering 6
peker på hodet av en lenket liste,

331
00:16:11,790 --> 00:16:14,900
og akkurat nå er det den eneste
element i en lenket liste.

332
00:16:14,900 --> 00:16:18,350
Og noden i det
lenket liste er Joey.

333
00:16:18,350 --> 00:16:22,300
>> Så hvis vi må se opp Joey
senere, vi bare hasj Joey igjen,

334
00:16:22,300 --> 00:16:26,300
vi får 6 igjen fordi vår
hash funksjonen er deterministisk.

335
00:16:26,300 --> 00:16:30,400
Og da vi starter på hodet
av lenket liste pekte

336
00:16:30,400 --> 00:16:33,360
til av matrise plassering
6, og vi kan iterere

337
00:16:33,360 --> 00:16:35,650
over som prøver å finne Joey.

338
00:16:35,650 --> 00:16:37,780
Og hvis vi bygger vår
hash table effektivt,

339
00:16:37,780 --> 00:16:41,790
og vår hash fungere effektivt
for å distribuere data godt,

340
00:16:41,790 --> 00:16:45,770
i gjennomsnitt hver av dem knyttet
lister på hver rekke plassering

341
00:16:45,770 --> 00:16:50,110
vil være 1/10 av størrelsen på hvis vi
bare hatt det som en eneste stor

342
00:16:50,110 --> 00:16:51,650
lenket liste med alt i det.

343
00:16:51,650 --> 00:16:55,670
>> Hvis vi distribuerer den digre linket
liste over 10 lenkede lister

344
00:16:55,670 --> 00:16:57,760
hver liste vil være 1/10 av størrelsen.

345
00:16:57,760 --> 00:17:01,432
Og dermed 10 ganger raskere
å søke gjennom.

346
00:17:01,432 --> 00:17:02,390
Så la oss gjøre dette igjen.

347
00:17:02,390 --> 00:17:04,290
La oss nå hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Og la oss si Ross, når vi gjør det
hash koden vi får tilbake er 2.

349
00:17:07,540 --> 00:17:10,630
Vel nå vi dynamisk tildele en
ny node, setter vi Ross i at node,

350
00:17:10,630 --> 00:17:14,900
og vi sier nå matrise plassering
2, i stedet for å peke til null,

351
00:17:14,900 --> 00:17:18,579
peker på hodet til en koblet
liste hvis eneste node er Ross.

352
00:17:18,579 --> 00:17:22,660
Og vi kan gjøre dette en gang til, vi
kan hash Rachel og få hashCode fire.

353
00:17:22,660 --> 00:17:25,490
malloc en ny node, satt Rachel i
noden, og si en rekke plassering

354
00:17:25,490 --> 00:17:27,839
4 nå peker mot hodet
av en lenket liste som

355
00:17:27,839 --> 00:17:31,420
eneste elementet skjer for å være Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, men hva skjer hvis
vi har en kollisjon?

357
00:17:33,470 --> 00:17:38,560
La oss se hvordan vi håndterer kollisjoner
bruker separate kjeding metoden.

358
00:17:38,560 --> 00:17:39,800
La oss hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Vi får hashCode 6.

360
00:17:41,094 --> 00:17:44,010
I vårt forrige eksempel var vi bare
lagring av strenger i rekken.

361
00:17:44,010 --> 00:17:45,980
Dette var et problem.

362
00:17:45,980 --> 00:17:48,444
>> Vi ønsker ikke å clobber
Joey, og vi har allerede

363
00:17:48,444 --> 00:17:51,110
sett at vi kan få noen clustering
problemer hvis vi prøver og trinn

364
00:17:51,110 --> 00:17:52,202
gjennom og sonde.

365
00:17:52,202 --> 00:17:54,660
Men hva om vi bare slags
behandle dette på samme måte, ikke sant?

366
00:17:54,660 --> 00:17:57,440
Det er akkurat som å legge et element
til hodet på en lenket liste.

367
00:17:57,440 --> 00:18:00,220
La oss bare malloc plass for Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Vi vil si Phoebe sin neste Pilen peker
til den gamle lederen for lenket liste,

369
00:18:04,764 --> 00:18:07,180
og deretter seks bare peker på
ny leder av lenket liste.

370
00:18:07,180 --> 00:18:10,150
Og nå ser, har vi endret Phoebe i.

371
00:18:10,150 --> 00:18:14,210
Vi kan nå lagre to
elementer med hashCode 6,

372
00:18:14,210 --> 00:18:17,170
og vi ikke har noen problemer.

373
00:18:17,170 --> 00:18:20,147
>> Det er ganske mye alt
det er å kjeding.

374
00:18:20,147 --> 00:18:21,980
Og kjeding er definitivt
den metoden som er

375
00:18:21,980 --> 00:18:27,390
kommer til å være mest effektive for deg hvis
du lagrer data i en hash table.

376
00:18:27,390 --> 00:18:30,890
Men denne kombinasjonen av
arrays og koblede lister

377
00:18:30,890 --> 00:18:36,080
sammen for å danne en nøkkeltabell virkelig
dramatisk forbedrer din evne

378
00:18:36,080 --> 00:18:40,550
til å lagre store mengder data, og
svært raskt og effektivt søk

379
00:18:40,550 --> 00:18:41,630
gjennom disse dataene.

380
00:18:41,630 --> 00:18:44,150
>> Det er fortsatt en mer
datastruktur der ute

381
00:18:44,150 --> 00:18:48,700
som kan selv være litt
bedre når det gjelder å garantere

382
00:18:48,700 --> 00:18:51,920
at vår innsetting, sletting, og
ser opp ganger er enda raskere.

383
00:18:51,920 --> 00:18:55,630
Og vi vil se at i en video på prøver.

384
00:18:55,630 --> 00:18:58,930
Jeg er Doug Lloyd, dette er CS50.

385
00:18:58,930 --> 00:19:00,214