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

2
00:00:00,500 --> 00:00:01,900
[Musik spiller]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Ved nu du
ved en masse om arrays,

5
00:00:09,150 --> 00:00:11,610
og du ved en masse om hægtede lister.

6
00:00:11,610 --> 00:00:13,650
Og vi har diskutere
fordele og ulemper, vi har

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

8
00:00:16,620 --> 00:00:18,630
men de fylder mere størrelse.

9
00:00:18,630 --> 00:00:22,359
Arrays er meget mere ligetil at
bruge, men de er restriktive i så meget

10
00:00:22,359 --> 00:00:24,900
som vi er nødt til at indstille størrelsen på
arrayet i begyndelsen

11
00:00:24,900 --> 00:00:26,910
og så er vi fast med det.

12
00:00:26,910 --> 00:00:30,470
>> Men det er, vi har temmelig meget
udtømt alle vores emner

13
00:00:30,470 --> 00:00:33,040
om hægtede lister og arrays.

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

15
00:00:34,950 --> 00:00:37,720
Måske kan vi gøre noget
endnu mere kreative.

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

17
00:00:40,950 --> 00:00:46,680
>> Så i en hash tabel vil vi forsøge
kombinere et array med en sammenkædet liste.

18
00:00:46,680 --> 00:00:49,520
Vi kommer til at tage fordelene
af array'et, som random access,

19
00:00:49,520 --> 00:00:53,510
at være i stand til at bare gå til matrix
element 4 eller arrayelement 8

20
00:00:53,510 --> 00:00:55,560
uden at skulle gentage tværs.

21
00:00:55,560 --> 00:00:57,260
Det er temmelig hurtigt, ikke?

22
00:00:57,260 --> 00:01:00,714
>> Men vi ønsker også at have vores data
struktur kunne vokse og skrumpe.

23
00:01:00,714 --> 00:01:02,630
Vi har ikke brug for, vi ikke
ønsker at være begrænset.

24
00:01:02,630 --> 00:01:04,588
Og vi ønsker at kunne
at tilføje og fjerne ting

25
00:01:04,588 --> 00:01:08,430
meget let, som hvis du husker,
er meget kompleks med et array.

26
00:01:08,430 --> 00:01:11,650
Og vi kan kalde denne
ny ting en hash tabel.

27
00:01:11,650 --> 00:01:15,190
>> Og hvis den gennemføres korrekt,
vi slags tager

28
00:01:15,190 --> 00:01:18,150
fordelene ved både data
strukturer, som du allerede har set,

29
00:01:18,150 --> 00:01:19,880
arrays og hægtede lister.

30
00:01:19,880 --> 00:01:23,070
Indsættelse kan begynde at
tenderer mod theta 1.

31
00:01:23,070 --> 00:01:26,207
Theta har vi ikke rigtig diskuteret,
men theta er bare den gennemsnitlige fald

32
00:01:26,207 --> 00:01:27,540
hvad der rent faktisk kommer til at ske.

33
00:01:27,540 --> 00:01:29,680
Du er ikke altid vil
har det værst tænkelige scenarie,

34
00:01:29,680 --> 00:01:32,555
og du ikke altid vil have
bedste fald, så hvad er

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

36
00:01:33,900 --> 00:01:36,500
>> Nå en gennemsnitlig indsættelse
i en hashtabel

37
00:01:36,500 --> 00:01:39,370
kan begynde at komme tæt på konstant tid.

38
00:01:39,370 --> 00:01:41,570
Og sletning kan få
tæt på konstant tid.

39
00:01:41,570 --> 00:01:44,440
Og opslag kan få
tæt på konstant tid.

40
00:01:44,440 --> 00:01:48,600
That's-- vi ikke har et data
struktur endnu, der kan gøre det,

41
00:01:48,600 --> 00:01:51,180
og så dette allerede lyder
som en temmelig stor ting.

42
00:01:51,180 --> 00:01:57,010
Vi har virkelig afbødes den
ulemper ved hver på egen hånd.

43
00:01:57,010 --> 00:01:59,160
>> For at få denne ydelse
opgradere selv, vi

44
00:01:59,160 --> 00:02:03,580
nødt til at genoverveje, hvordan vi tilføjer
data i strukturen.

45
00:02:03,580 --> 00:02:07,380
Konkret ønsker vi
data, selv at fortælle os

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

47
00:02:09,725 --> 00:02:12,850
Og hvis vi så nødt til at se, om det er i
strukturen, hvis vi har brug for at finde det,

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

49
00:02:16,610 --> 00:02:18,910
ved hjælp af data, tilfældigt adgang til den.

50
00:02:18,910 --> 00:02:20,700
Bare ved at se på
data, som vi skal have

51
00:02:20,700 --> 00:02:25,890
en idé om, hvor præcis er vi
kommer til at finde det i hash-tabellen.

52
00:02:25,890 --> 00:02:28,770
>> Nu ulempen ved en hash
bordet er, at de er virkelig

53
00:02:28,770 --> 00:02:31,770
temmelig dårlig til at bestille eller sortering af data.

54
00:02:31,770 --> 00:02:34,970
Og i virkeligheden, hvis du starter
at bruge dem til orden eller sortere

55
00:02:34,970 --> 00:02:37,990
data, mister du alle de
fordele, du tidligere

56
00:02:37,990 --> 00:02:40,710
havde i form af indsættelse og sletning.

57
00:02:40,710 --> 00:02:44,060
Tiden bliver tættere på
theta på n, og vi har set

58
00:02:44,060 --> 00:02:45,530
svandt i en sammenkædet liste.

59
00:02:45,530 --> 00:02:48,850
Og så vi kun ønsker at bruge hash
tabeller, hvis vi ikke bekymrer sig om

60
00:02:48,850 --> 00:02:51,490
hvorvidt dataene er sorteret.

61
00:02:51,490 --> 00:02:54,290
For den sammenhæng, hvori
du skal bruge dem i CS50

62
00:02:54,290 --> 00:02:58,900
du sandsynligvis er ligeglad
at dataene er sorteret.

63
00:02:58,900 --> 00:03:03,170
>> Så en hash tabel er en kombination
af to adskilte stykker

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

65
00:03:04,980 --> 00:03:07,930
Den første er en funktion, som
vi normalt kalder en hash-funktion.

66
00:03:07,930 --> 00:03:11,760
Og at hash-funktion vil
vende tilbage en ikke-negativt heltal, som

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

68
00:03:14,870 --> 00:03:20,230
Det andet stykke er et array, som er
stand til at lagre data af typen vi

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

70
00:03:22,190 --> 00:03:24,310
Vi vil holde ud på den
sammenkædet liste element for nu

71
00:03:24,310 --> 00:03:27,810
og bare starte med det grundlæggende i en
hash tabel til at få dit hoved omkring det,

72
00:03:27,810 --> 00:03:30,210
og så vil vi måske blæse
dit sind en lille smule, 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 grundlæggende idé om
er vi tager nogle data.

75
00:03:35,590 --> 00:03:37,860
Vi kører, at data gennem
hash-funktionen.

76
00:03:37,860 --> 00:03:41,980
Og så data behandles
og det spytter et tal, OK?

77
00:03:41,980 --> 00:03:44,890
Og derefter med dette nummer
vi bare gemme data

78
00:03:44,890 --> 00:03:48,930
vi ønsker at gemme i
vifte på det sted.

79
00:03:48,930 --> 00:03:53,990
Så for eksempel har vi måske
denne hash tabel af strenge.

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

81
00:03:57,350 --> 00:03:59,320
>> Lad os sige, at vi ønsker at hash John.

82
00:03:59,320 --> 00:04:02,979
Så John som de data, vi vil indsætte
i denne hash tabellen sted.

83
00:04:02,979 --> 00:04:03,770
Hvor skal vi sætte det?

84
00:04:03,770 --> 00:04:05,728
Nå typisk med en
vifte hidtil vi sandsynligvis

85
00:04:05,728 --> 00:04:07,610
ville sætte det i matrix placering 0.

86
00:04:07,610 --> 00:04:09,960
Men nu har vi denne nye hash funktion.

87
00:04:09,960 --> 00:04:13,180
>> Og lad os sige, at vi kører John
gennem denne hash-funktion

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

89
00:04:15,417 --> 00:04:17,500
Nå det er, hvor vi er
lyst til at sætte John.

90
00:04:17,500 --> 00:04:22,050
Vi ønsker at sætte John i matrix placering
4, for hvis vi hash John igen--

91
00:04:22,050 --> 00:04:23,810
lad os sige senere vi
vil søge og se

92
00:04:23,810 --> 00:04:26,960
hvis John eksisterer i denne hash
table-- alt, hvad vi behøver at gøre

93
00:04:26,960 --> 00:04:30,310
køres det gennem den samme hash
funktion, få nummeret 4,

94
00:04:30,310 --> 00:04:33,929
og være i stand til at finde John
straks i vores datastruktur.

95
00:04:33,929 --> 00:04:34,720
Det er temmelig godt.

96
00:04:34,720 --> 00:04:36,928
>> Lad os sige, at vi nu gør det
igen, vi ønsker at hash Paul.

97
00:04:36,928 --> 00:04:39,446
Vi ønsker at tilføje Paul
i denne hash tabellen.

98
00:04:39,446 --> 00:04:42,070
Lad os sige, at vi denne gang køre
Paul gennem hash-funktionen,

99
00:04:42,070 --> 00:04:44,600
den hashCode, der genereres er 6.

100
00:04:44,600 --> 00:04:47,340
Nå nu kan vi sætte Paulus
i arrayet placeringen 6.

101
00:04:47,340 --> 00:04:50,040
Og hvis vi har brug for at slå op, om
Paulus er i denne hash tabel,

102
00:04:50,040 --> 00:04:53,900
alt, hvad vi skal gøre, er at køre Paul
gennem hash-funktionen igen

103
00:04:53,900 --> 00:04:55,830
og vi kommer til at få 6 ud igen.

104
00:04:55,830 --> 00:04:57,590
>> Og så har vi bare se
ved opstilling placering 6.

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

106
00:04:58,910 --> 00:05:00,160
Hvis ja, han er i hash tabellen.

107
00:05:00,160 --> 00:05:01,875
Er Paulus ikke er der?

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 ret ligetil.

110
00:05:05,720 --> 00:05:07,770
>> Nu hvordan kan du definere en hash-funktion?

111
00:05:07,770 --> 00:05:11,460
Tja der er virkelig ingen grænse for
Antallet af mulige hashfunktioner.

112
00:05:11,460 --> 00:05:14,350
Faktisk er der en række virkelig,
virkelig gode på internettet.

113
00:05:14,350 --> 00:05:17,560
Der er en række virkelig,
virkelig dårlige på internettet.

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

115
00:05:21,080 --> 00:05:23,760
>> Så hvad gør en god
hash-funktionen, ikke?

116
00:05:23,760 --> 00:05:27,280
Nå en god hash-funktion bør
bruger kun de data, der hashed,

117
00:05:27,280 --> 00:05:29,420
og alle de data, der hashed.

118
00:05:29,420 --> 00:05:32,500
Så vi ønsker ikke at bruge anything--
vi ikke indarbejde noget

119
00:05:32,500 --> 00:05:35,560
andet end dataene.

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

121
00:05:37,080 --> 00:05:39,830
Vi ønsker ikke at bare bruge et stykke
af det, vi ønsker at bruge det hele.

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

123
00:05:41,710 --> 00:05:42,550
Hvad betyder det?

124
00:05:42,550 --> 00:05:46,200
Nå det betyder, at hver gang vi
passere nøjagtig samme stykke data

125
00:05:46,200 --> 00:05:50,040
ind i hash-funktionen vi altid
får den samme hashCode ud.

126
00:05:50,040 --> 00:05:52,870
Hvis jeg passerer Johannes ind i
hash-funktion jeg kommer ud 4.

127
00:05:52,870 --> 00:05:56,110
Jeg skulle være i stand til at gøre det 10.000
gange, og jeg vil altid få 4.

128
00:05:56,110 --> 00:06:00,810
Så ingen tilfældige tal effektivt
kan inddrages i vores hash tables--

129
00:06:00,810 --> 00:06:02,750
i vores hashfunktioner.

130
00:06:02,750 --> 00:06:05,750
>> En hash-funktionen skal også
ensartet at fordele data.

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

132
00:06:09,700 --> 00:06:11,200
det er nok ikke så stor, højre?

133
00:06:11,200 --> 00:06:14,600
Du ønsker sikkert at store
en række hash-koder.

134
00:06:14,600 --> 00:06:17,190
Også ting kan spredes
i hele tabellen.

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

136
00:06:23,210 --> 00:06:26,320
måske blev spredt ud til at veje
forskellige steder i hash tabellen.

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

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

139
00:06:31,250 --> 00:06:33,150
Jeg skrev denne ene op tidligere.

140
00:06:33,150 --> 00:06:35,047
Det er ikke en særlig
god hashfunktion

141
00:06:35,047 --> 00:06:37,380
af årsager, der ikke rigtig
bære at gå ind lige nu.

142
00:06:37,380 --> 00:06:41,040
Men ser du, hvad der foregår her?

143
00:06:41,040 --> 00:06:44,420
Det ser ud som vi erklære en variabel
kaldet sum og sætte den lig med 0.

144
00:06:44,420 --> 00:06:50,010
Og så åbenbart jeg gør noget
så længe strstr [j] er ikke lig

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

146
00:06:52,490 --> 00:06:54,870
Hvad gør jeg der?

147
00:06:54,870 --> 00:06:57,440
>> Dette er dybest set bare et andet
måde at gennemføre [? strl?]

148
00:06:57,440 --> 00:06:59,773
og afsløre når du har
nået enden af ​​strengen.

149
00:06:59,773 --> 00:07:02,480
Så jeg behøver ikke at faktisk
beregne længden af ​​strengen,

150
00:07:02,480 --> 00:07:05,640
Jeg er bare at bruge, når jeg ramte
backslash 0 tegn jeg kender

151
00:07:05,640 --> 00:07:07,185
Jeg har nået slutningen af ​​strengen.

152
00:07:07,185 --> 00:07:09,560
Og så jeg har tænkt mig at holde
iteration gennem denne streng,

153
00:07:09,560 --> 00:07:15,310
tilføjer strstr [j] for at opsummere, og derefter på
slutningen af ​​dagen vil returnere summen mod

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

155
00:07:16,200 --> 00:07:18,700
>> Dybest set alt dette hash
funktion gør, er at tilføje op

156
00:07:18,700 --> 00:07:23,450
alle de ASCII værdier
min snor, og så er det

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

158
00:07:26,390 --> 00:07:29,790
Det er nok på størrelse
af min matrix, ikke?

159
00:07:29,790 --> 00:07:33,160
Jeg ønsker ikke at være at få hash
koder, hvis min array er i størrelse 10,

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

161
00:07:35,712 --> 00:07:38,690
13, kan jeg ikke sætte tingene i
de steder af opstillingen,

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

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

164
00:07:42,130 --> 00:07:45,230
>> Nu her er en anden hurtig til side.

165
00:07:45,230 --> 00:07:48,470
Generelt er du sandsynligvis ikke kommer til at
ønsker at skrive dine egne hash funktioner.

166
00:07:48,470 --> 00:07:50,997
Det er faktisk lidt af
en kunst, ikke en videnskab.

167
00:07:50,997 --> 00:07:52,580
Og der er en masse, der går ind i dem.

168
00:07:52,580 --> 00:07:55,288
Internettet, som jeg sagde, er fuld
rigtig gode hashfunktioner,

169
00:07:55,288 --> 00:07:58,470
og du skal bruge internettet til at
find hashfunktioner fordi det er virkelig

170
00:07:58,470 --> 00:08:03,230
lige slags en unødvendig
spild af tid at oprette din egen.

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

172
00:08:05,490 --> 00:08:08,323
Men når du rent faktisk kommer til at
begynde hashing af data og lagring

173
00:08:08,323 --> 00:08:10,780
ind i en hash tabel, du er
sandsynligvis vil ønsker

174
00:08:10,780 --> 00:08:14,580
at bruge en funktion, der blev genereret
for dig, der findes på internettet.

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

176
00:08:17,240 --> 00:08:21,740
Der er ingen grund til at
plagiere noget her.

177
00:08:21,740 --> 00:08:25,370
>> Den datalogi samfund er
afgjort voksende, og virkelig værdier

178
00:08:25,370 --> 00:08:28,796
open source, og det er virkelig vigtigt
at citere dine kilder, så folk

179
00:08:28,796 --> 00:08:30,670
kan få tilskrivning til
det arbejde, de er

180
00:08:30,670 --> 00:08:32,312
gør til gavn for samfundet.

181
00:08:32,312 --> 00:08:34,020
Så altid være sure--
og ikke kun for hash

182
00:08:34,020 --> 00:08:37,270
funktioner, men generelt, når man
bruge kode fra en ekstern kilde,

183
00:08:37,270 --> 00:08:38,299
altid nævne din kilde.

184
00:08:38,299 --> 00:08:43,500
Give kredit til den person, der gjorde
en del af arbejdet, så du ikke behøver at.

185
00:08:43,500 --> 00:08:46,720
>> OK, så lad os revidere denne
hash tabel til en anden.

186
00:08:46,720 --> 00:08:48,780
Det er her, vi forlod
off efter vi indsat

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

188
00:08:53,300 --> 00:08:55,180
Kan du se 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 i særdeleshed, har du
se dette mulige problem?

191
00:09:02,240 --> 00:09:06,770
>> Hvad hvis jeg hash Ringo, og det
viser sig, at efter forarbejdning

192
00:09:06,770 --> 00:09:14,000
at data gennem hash-funktionen
Ringo også genereret hashCode 6.

193
00:09:14,000 --> 00:09:16,810
Jeg har allerede fået data
hashcode-- matrix placering 6.

194
00:09:16,810 --> 00:09:22,000
Så det er sandsynligvis kommer til at være en smule
af et problem for mig nu, ikke?

195
00:09:22,000 --> 00:09:23,060
>> Vi kalder det en kollision.

196
00:09:23,060 --> 00:09:26,460
Og kollisionen sker, når to
stykker af data løber gennem den samme hash

197
00:09:26,460 --> 00:09:29,200
Funktionen giver den samme hashCode.

198
00:09:29,200 --> 00:09:32,850
Formodentlig vi stadig ønsker at få både
stykker af data til hash tabellen,

199
00:09:32,850 --> 00:09:36,330
ellers ville vi ikke køre Ringo
vilkårligt gennem hash-funktionen.

200
00:09:36,330 --> 00:09:40,870
Vi formentlig ønsker at få
Ringo i den opstilling.

201
00:09:40,870 --> 00:09:46,070
>> Hvordan gør vi det selv, hvis han
og Paul begge udbytte hashCode 6?

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

203
00:09:49,520 --> 00:09:52,790
Så vi har brug for at finde en måde at få
elementer i hash tabel,

204
00:09:52,790 --> 00:09:56,550
stadig bevarer vores hurtige
indsættelse og hurtigt kig op.

205
00:09:56,550 --> 00:10:01,350
Og en måde at håndtere det er at
gøre noget, der hedder lineær sondering.

206
00:10:01,350 --> 00:10:04,170
>> Ved hjælp af denne metode, hvis vi har en
kollision, ja, hvad gør vi?

207
00:10:04,170 --> 00:10:08,580
Nå vi kan ikke sætte ham i matrix placering
6, eller hvad hashCode blev genereret,

208
00:10:08,580 --> 00:10:10,820
lad os sætte ham på hashCode plus 1.

209
00:10:10,820 --> 00:10:13,670
Og hvis der er fuld lad os
sætte ham i hashCode plus 2.

210
00:10:13,670 --> 00:10:17,420
Fordelen ved dette væsen, hvis han er
ikke præcis, hvor vi tror, ​​han er,

211
00:10:17,420 --> 00:10:20,850
og vi er nødt til at begynde at søge,
måske vi behøver ikke at gå for vidt.

212
00:10:20,850 --> 00:10:23,900
Måske har vi ikke at søge
alle n elementer af hash tabellen.

213
00:10:23,900 --> 00:10:25,790
Måske vi nødt til at søge
et par af dem.

214
00:10:25,790 --> 00:10:30,680
>> Og så vi er stadig en tendens i retning af
at den gennemsnitlige fald være tæt på 1 vs

215
00:10:30,680 --> 00:10:34,280
tæt på n, så måske kommer til at arbejde.

216
00:10:34,280 --> 00:10:38,010
Så lad os se, hvordan dette
kan arbejde ud i virkeligheden.

217
00:10:38,010 --> 00:10:41,460
Og lad os se om måske kan vi afsløre
det problem, at der kan forekomme her.

218
00:10:41,460 --> 00:10:42,540
>> Lad os sige, at vi hash Bart.

219
00:10:42,540 --> 00:10:45,581
Så nu vil vi til at køre et nyt sæt
af strenge gennem hash-funktionen,

220
00:10:45,581 --> 00:10:48,460
og vi kører Bart gennem hash
funktion, får vi hashCode 6.

221
00:10:48,460 --> 00:10:52,100
Vi tager et kig, ser vi 6
tom, så vi kan sætte Bart der.

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

223
00:10:55,410 --> 00:10:58,330
Nå nu, at vi bruger denne
lineære sondering metode vi starter ved 6,

224
00:10:58,330 --> 00:10:59,330
ser vi, at 6 er fuld.

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

226
00:11:00,990 --> 00:11:02,090
Så hvor skal vi hen?

227
00:11:02,090 --> 00:11:03,280
Lad os gå til 7.

228
00:11:03,280 --> 00:11:04,610
7 tomme, så der virker.

229
00:11:04,610 --> 00:11:06,510
Så lad os sætte Lisa der.

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

231
00:11:10,200 --> 00:11:13,380
OK godt vi ved, at 7 fulde
nu, så kan vi ikke sætte Homer der.

232
00:11:13,380 --> 00:11:14,850
Så lad os gå til 8.

233
00:11:14,850 --> 00:11:15,664
Er 8 til rådighed?

234
00:11:15,664 --> 00:11:18,330
Ja, og 8 er tæt på 7, så hvis
vi er nødt til at begynde at søge vi er

235
00:11:18,330 --> 00:11:20,020
ikke vil have til at gå for vidt.

236
00:11:20,020 --> 00:11:22,860
Og så lad os sætte Homer 8.

237
00:11:22,860 --> 00:11:25,151
>> Nu er vi hash Maggie og
returnerer 3, gudskelov

238
00:11:25,151 --> 00:11:26,650
vi er i stand til at bare sætte Maggie der.

239
00:11:26,650 --> 00:11:29,070
Vi behøver ikke at gøre noget
slags sondering for.

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

241
00:11:32,000 --> 00:11:39,560
>> Nå 6 er fuld, 7 er fuld, 8 er fuld,
9, okay gudskelov 9 er tom.

242
00:11:39,560 --> 00:11:41,600
Jeg kan sætte Marge ved 9.

243
00:11:41,600 --> 00:11:45,280
Vi kan allerede se, at vi er begyndt
at have dette problem, hvor nu er vi

244
00:11:45,280 --> 00:11:48,780
begynder at strække ting form
langt væk fra deres hash-koder.

245
00:11:48,780 --> 00:11:52,960
Og at theta på 1, det gennemsnitlige
tilfælde af at være konstant tid,

246
00:11:52,960 --> 00:11:56,560
er begyndt at få lidt more--
begynder at tendens lidt mere

247
00:11:56,560 --> 00:11:58,050
mod theta på n.

248
00:11:58,050 --> 00:12:01,270
Vi er begyndt at miste denne
fordel af hash-tabeller.

249
00:12:01,270 --> 00:12:03,902
>> Dette problem, som vi lige har set
er noget, der hedder klyngedannelse.

250
00:12:03,902 --> 00:12:06,360
Og hvad er virkelig dårligt om
klyngedannelse er, at når du nu

251
00:12:06,360 --> 00:12:09,606
har to elementer, der ved siden af
side gør det endnu mere sandsynligt,

252
00:12:09,606 --> 00:12:11,480
du har dobbelt
chance, at du vil

253
00:12:11,480 --> 00:12:13,516
at have en anden kollision
med denne klynge,

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 voksende og voksende
din sandsynligheden for at have en kollision.

256
00:12:19,640 --> 00:12:24,470
Og i sidste ende er det lige så slemt
som ikke sortere data overhovedet.

257
00:12:24,470 --> 00:12:27,590
>> Det andet problem er dog, at vi
stadig, og så videre op til dette punkt,

258
00:12:27,590 --> 00:12:30,336
Vi har netop været en slags
at forstå, hvad en hash tabel er,

259
00:12:30,336 --> 00:12:31,960
vi stadig kun har plads til 10 strenge.

260
00:12:31,960 --> 00:12:37,030
Hvis vi ønsker at fortsætte med at hash
borgerne i Springfield,

261
00:12:37,030 --> 00:12:38,790
Vi kan kun få 10 af dem derinde.

262
00:12:38,790 --> 00:12:42,619
Og hvis vi forsøge at tilføje en 11. eller 12.,
vi ikke har et sted at sætte dem.

263
00:12:42,619 --> 00:12:45,660
Vi kunne bare være spinning rundt i
cirkler forsøger at finde et tomt sted,

264
00:12:45,660 --> 00:12:49,000
og vi måske går i stå
i en uendelig løkke.

265
00:12:49,000 --> 00:12:51,810
>> Så denne slags låner til idéen
af noget, der hedder kæde.

266
00:12:51,810 --> 00:12:55,790
Og det er her, vi kommer til at bringe
hægtede lister tilbage ind i billedet.

267
00:12:55,790 --> 00:13:01,300
Hvad hvis stedet for at lagre lige
selve dataene i arrayet,

268
00:13:01,300 --> 00:13:04,471
hvert element i arrayet kunne
holde flere stykker af data?

269
00:13:04,471 --> 00:13:05,970
Nå det giver ikke mening, ikke?

270
00:13:05,970 --> 00:13:09,280
Vi ved, at et array kan kun
hold-- hvert element i et array

271
00:13:09,280 --> 00:13:12,930
kan kun holde et stykke
af data for denne datatype.

272
00:13:12,930 --> 00:13:16,750
>> Men hvad hvis det datatype
er en linket liste, ikke?

273
00:13:16,750 --> 00:13:19,830
Så hvad nu hvis hver
element i arrayet var

274
00:13:19,830 --> 00:13:22,790
en pointer til lederen af ​​en linket liste?

275
00:13:22,790 --> 00:13:24,680
Og så kunne vi bygge
disse hægtede lister

276
00:13:24,680 --> 00:13:27,120
og dyrke dem vilkårligt,
fordi hægtede lister tillader

277
00:13:27,120 --> 00:13:32,090
os til at vokse og skrumpe meget mere
fleksibelt end et array gør.

278
00:13:32,090 --> 00:13:34,210
Så hvad nu hvis vi nu bruger,
vi udnytte dette, ikke?

279
00:13:34,210 --> 00:13:37,760
Vi begynder at vokse disse kæder
ud af disse Array steder.

280
00:13:37,760 --> 00:13:40,740
>> Nu kan vi passer en uendelig
datamængde, eller ikke uendelig,

281
00:13:40,740 --> 00:13:44,170
en vilkårlig mængde
data ind i vores hash tabel

282
00:13:44,170 --> 00:13:47,760
uden at løbe ind
problemet med kollision.

283
00:13:47,760 --> 00:13:50,740
Vi har også fjernet
klyngedannelse ved at gøre dette.

284
00:13:50,740 --> 00:13:54,380
Og godt vi ved, at når vi indsætter
ind i en linket liste, hvis du husker

285
00:13:54,380 --> 00:13:57,779
fra vores video på hægtede lister, enkeltvis
forbundne lister og dobbelt hægtede lister,

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

287
00:13:59,070 --> 00:14:00,710
Vi er blot at tilføje til fronten.

288
00:14:00,710 --> 00:14:04,400
>> Og for udseende op, godt vi kender
at slå op i en sammenkædet liste

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

290
00:14:05,785 --> 00:14:07,910
Vi er nødt til at søge gennem
det fra start til slut.

291
00:14:07,910 --> 00:14:10,460
Der er ingen tilfældig
adgang i en sammenkædet liste.

292
00:14:10,460 --> 00:14:15,610
Men hvis man i stedet for at have en tilknytning
liste, hvor et opslag ville være O i n,

293
00:14:15,610 --> 00:14:19,590
vi nu har 10 hægtede lister,
eller 1.000 hægtede lister,

294
00:14:19,590 --> 00:14:24,120
nu er det O n divideret med 10,
eller O n divideret med 1.000.

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

296
00:14:26,940 --> 00:14:30,061
vi bort konstanter, i den virkelige
verden disse ting rent faktisk noget,

297
00:14:30,061 --> 00:14:30,560
højre?

298
00:14:30,560 --> 00:14:33,080
Vi vil faktisk mærke
at dette sker

299
00:14:33,080 --> 00:14:36,610
at køre 10 gange hurtigere,
eller 1.000 gange hurtigere,

300
00:14:36,610 --> 00:14:41,570
fordi vi distribuerer en lang
kæde på tværs af 1.000 mindre kæder.

301
00:14:41,570 --> 00:14:45,090
Og så hver gang vi nødt til at søge
gennem en af ​​disse kæder, vi kan

302
00:14:45,090 --> 00:14:50,290
ignorere de 999 kæder, vi er ligeglade
om, og bare søge at en.

303
00:14:50,290 --> 00:14:53,220
>> Som i gennemsnit til
være 1000 gange kortere.

304
00:14:53,220 --> 00:14:56,460
Og så vi stadig er slags
tendens i retning af dette gennemsnit sag

305
00:14:56,460 --> 00:15:01,610
for at være konstant tid, men
kun fordi vi udnytte

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

307
00:15:03,730 --> 00:15:05,804
Lad os se, hvordan dette kan
faktisk ser dog.

308
00:15:05,804 --> 00:15:08,720
Så det var hash tabellen havde vi
før vi erklærede en hash tabel,

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

310
00:15:10,270 --> 00:15:11,728
Vi kommer ikke til at gøre det længere.

311
00:15:11,728 --> 00:15:13,880
Vi kender allerede
begrænsninger af denne metode.

312
00:15:13,880 --> 00:15:20,170
Nu er vores hash tabellen kommer til at være
en vifte af 10 noder, pointers

313
00:15:20,170 --> 00:15:22,120
til lederne af hægtede lister.

314
00:15:22,120 --> 00:15:23,830
>> Og lige nu er det nul.

315
00:15:23,830 --> 00:15:26,170
Hver enkelt af de 10 pejlemærker er null.

316
00:15:26,170 --> 00:15:29,870
Der er ikke noget i vores
hash tabellen lige nu.

317
00:15:29,870 --> 00:15:32,690
>> Lad os begynde at sætte nogle
ting i denne hash tabel.

318
00:15:32,690 --> 00:15:35,440
Og lad os se, hvordan denne metode er
kommer til at gavne os lidt.

319
00:15:35,440 --> 00:15:36,760
Lad os nu hash Joey.

320
00:15:36,760 --> 00:15:40,210
Vi vil vil køre strengen Joey gennem
en hash-funktion, og vi vender tilbage 6.

321
00:15:40,210 --> 00:15:41,200
Nå, hvad gør vi nu?

322
00:15:41,200 --> 00:15:44,090
>> Nå nu arbejder med hægtede lister,
vi ikke arbejder med arrays.

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

324
00:15:45,881 --> 00:15:49,790
ved, at vi er nødt til at starte dynamisk
tildeling af plads og bygge kæder.

325
00:15:49,790 --> 00:15:54,020
Det er slags how-- disse er kernen
elementer af at opbygge en linket liste.

326
00:15:54,020 --> 00:15:57,670
Så lad os dynamisk
afsætte plads til Joey,

327
00:15:57,670 --> 00:16:00,390
og så lad os tilføje ham til kæden.

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

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

330
00:16:06,440 --> 00:16:11,790
Nu markøren på arrayet placering 6
peger på lederen af ​​en linket liste,

331
00:16:11,790 --> 00:16:14,900
og lige nu er det den eneste
element i en sammenkædet liste.

332
00:16:14,900 --> 00:16:18,350
Og knudepunktet ved, at
linket liste er Joey.

333
00:16:18,350 --> 00:16:22,300
>> Så hvis vi har brug for at slå op Joey
senere, vi bare hash Joey igen,

334
00:16:22,300 --> 00:16:26,300
vi får 6 igen fordi vores
hash-funktionen er deterministisk.

335
00:16:26,300 --> 00:16:30,400
Og så starter vi i spidsen
af den linkede liste pegede

336
00:16:30,400 --> 00:16:33,360
til med matrix placering
6, og vi kan gentage

337
00:16:33,360 --> 00:16:35,650
tværs, der forsøger at finde Joey.

338
00:16:35,650 --> 00:16:37,780
Og hvis vi bygger vores
hash tabel effektivt,

339
00:16:37,780 --> 00:16:41,790
og vores hash-funktionen effektivt
at distribuere data godt,

340
00:16:41,790 --> 00:16:45,770
i gennemsnit hver af dem der er knyttet
lister på hver matrix placering

341
00:16:45,770 --> 00:16:50,110
vil være 1/10 af størrelsen på hvis vi
lige haft det som en enkelt stor

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

343
00:16:51,650 --> 00:16:55,670
>> Hvis vi distribuerer, at enorme knyttet
liste over 10 hægtede lister

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

345
00:16:57,760 --> 00:17:01,432
Og dermed 10 gange hurtigere
at søge igennem.

346
00:17:01,432 --> 00:17:02,390
Så lad os gøre det igen.

347
00:17:02,390 --> 00:17:04,290
Lad os nu hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Og lad os sige Ross, når vi gør det
hash kode, vi får tilbage er 2.

349
00:17:07,540 --> 00:17:10,630
Nå nu er vi dynamisk allokere en
ny knude, vi sætter Ross i den knude,

350
00:17:10,630 --> 00:17:14,900
og vi siger nu vifte placering
2, i stedet for at pege til null,

351
00:17:14,900 --> 00:17:18,579
peger på hovedet af en knyttet
liste hvis eneste node er Ross.

352
00:17:18,579 --> 00:17:22,660
Og vi kan gøre det en gang mere, vi
kan hash Rachel og få hashCode 4.

353
00:17:22,660 --> 00:17:25,490
malloc en ny knude, sætte Rachel i
node, og sige en række placering

354
00:17:25,490 --> 00:17:27,839
4 nu peger på hovedet
en sammenkædet liste, hvis

355
00:17:27,839 --> 00:17:31,420
eneste element sker for at være Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, men hvad sker der, hvis
vi har en kollision?

357
00:17:33,470 --> 00:17:38,560
Lad os se, hvordan vi håndterer kollisioner
ved hjælp af den separate kæde metode.

358
00:17:38,560 --> 00:17:39,800
Lad os 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 vores tidligere eksempel var vi lige
lagring af strenge i arrayet.

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 at tæske
Joey, og vi har allerede

363
00:17:48,444 --> 00:17:51,110
set, at vi kan få nogle clustering
problemer, hvis vi forsøger og trin

364
00:17:51,110 --> 00:17:52,202
gennem og probe.

365
00:17:52,202 --> 00:17:54,660
Men hvad nu, hvis vi bare lidt
behandle denne på samme måde, ikke?

366
00:17:54,660 --> 00:17:57,440
Det er ligesom at tilføje et element
til lederen af ​​en linket liste.

367
00:17:57,440 --> 00:18:00,220
Lad os bare malloc plads til Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Vi vil sige Phoebe næste pointer punkter
til den gamle leder af den linkede liste,

369
00:18:04,764 --> 00:18:07,180
og derefter 6 lige peger på
nye leder af den linkede liste.

370
00:18:07,180 --> 00:18:10,150
Og nu ser vi har ændret Phoebe i.

371
00:18:10,150 --> 00:18:14,210
Vi kan nu gemme to
elementer med hashCode 6,

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

373
00:18:17,170 --> 00:18:20,147
>> Det er temmelig meget alle
der er at kæde.

374
00:18:20,147 --> 00:18:21,980
Og kæde er afgjort
den metode, der er

375
00:18:21,980 --> 00:18:27,390
vil være mest effektiv for dig, hvis
du gemmer data i en hash-tabel.

376
00:18:27,390 --> 00:18:30,890
Men denne kombination af
arrays og hægtede lister

377
00:18:30,890 --> 00:18:36,080
sammen for at danne en hashtabel virkelig
dramatisk forbedrer din evne

378
00:18:36,080 --> 00:18:40,550
til at lagre store mængder data, og
meget hurtigt og effektivt søge

379
00:18:40,550 --> 00:18:41,630
gennem disse data.

380
00:18:41,630 --> 00:18:44,150
>> Der er stadig en mere
datastruktur derude

381
00:18:44,150 --> 00:18:48,700
der kan endda være en smule
bedre med hensyn til at sikre

382
00:18:48,700 --> 00:18:51,920
at vores insertion, deletion og
ser op tider er endnu hurtigere.

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

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

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