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

2
00:00:00,500 --> 00:00:01,900
[Speel van musiek]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: By nou is jy
weet 'n baie oor skikkings,

5
00:00:09,150 --> 00:00:11,610
en jy weet 'n baie oor geskakelde lyste.

6
00:00:11,610 --> 00:00:13,650
En ons het bespreek die
voor- en nadele, ons het

7
00:00:13,650 --> 00:00:16,620
bespreek wat gekoppel lyste
kan groter en kleiner te kry,

8
00:00:16,620 --> 00:00:18,630
maar hulle neem meer grootte.

9
00:00:18,630 --> 00:00:22,359
Skikkings is baie meer eenvoudig om
gebruik, maar hulle is beperkende in soveel

10
00:00:22,359 --> 00:00:24,900
as ons die grootte van stel
die skikking aan die begin

11
00:00:24,900 --> 00:00:26,910
En dan is ons vas met dit.

12
00:00:26,910 --> 00:00:30,470
>> Maar dit is, ons het pretty much
uitgeput van al ons onderwerpe

13
00:00:30,470 --> 00:00:33,040
oor geskakelde lyste en skikkings.

14
00:00:33,040 --> 00:00:34,950
Of het ons?

15
00:00:34,950 --> 00:00:37,720
Miskien kan ons iets doen
selfs meer kreatief.

16
00:00:37,720 --> 00:00:40,950
En dat die soort van leen
die idee van 'n hash tafel.

17
00:00:40,950 --> 00:00:46,680
>> So in 'n gemors tafel gaan ons probeer
kombineer 'n verskeidenheid met 'n geskakelde lys.

18
00:00:46,680 --> 00:00:49,520
Ons gaan die voordele te neem
van die skikking, soos ewetoeganklike,

19
00:00:49,520 --> 00:00:53,510
om te gaan net na array staat
element 4 of skikking element 8

20
00:00:53,510 --> 00:00:55,560
sonder om oor Itereer.

21
00:00:55,560 --> 00:00:57,260
Dit is redelik vinnig, reg?

22
00:00:57,260 --> 00:01:00,714
>> Maar ons wil ook ons ​​data het
struktuur in staat wees om te groei en krimp.

23
00:01:00,714 --> 00:01:02,630
Ons hoef nie, ons doen nie
wil beperk.

24
00:01:02,630 --> 00:01:04,588
En ons wil in staat wees
om by te voeg en te verwyder dinge

25
00:01:04,588 --> 00:01:08,430
baie maklik, wat as jy onthou,
is baie kompleks met 'n skikking.

26
00:01:08,430 --> 00:01:11,650
En ons kan dit noem
nuwe ding wat 'n hash tafel.

27
00:01:11,650 --> 00:01:15,190
>> En indien dit korrek geïmplementeer word,
ons soort van die neem van

28
00:01:15,190 --> 00:01:18,150
die voordele van beide data
strukture wat jy reeds gesien het,

29
00:01:18,150 --> 00:01:19,880
skikkings en geskakelde lyste.

30
00:01:19,880 --> 00:01:23,070
Invoeging kan begin
neig na theta van 1.

31
00:01:23,070 --> 00:01:26,207
Theta ons het nie regtig bespreek,
maar theta is net die gemiddelde geval,

32
00:01:26,207 --> 00:01:27,540
wat eintlik gaan gebeur nie.

33
00:01:27,540 --> 00:01:29,680
Jy is nie altyd gaan
het die ergste geval scenario,

34
00:01:29,680 --> 00:01:32,555
en jy nie altyd gaan hê
die beste scenario, so wat is

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

36
00:01:33,900 --> 00:01:36,500
>> Wel 'n gemiddelde invoeging
in 'n hash tafel

37
00:01:36,500 --> 00:01:39,370
kan begin om naby aan konstante tyd.

38
00:01:39,370 --> 00:01:41,570
En skrap kan kry
sluit aan konstante tyd.

39
00:01:41,570 --> 00:01:44,440
En lookup kan kry
sluit aan konstante tyd.

40
00:01:44,440 --> 00:01:48,600
That's-- ons nie 'n data het
struktuur nog wat kan dit doen,

41
00:01:48,600 --> 00:01:51,180
en so dit alreeds klink
soos 'n mooi groot ding.

42
00:01:51,180 --> 00:01:57,010
Ons het regtig versag die
nadele van elk op sy eie.

43
00:01:57,010 --> 00:01:59,160
>> Om hierdie prestasie te kry
gradeer al is, ons

44
00:01:59,160 --> 00:02:03,580
moet dink hoe ons by te voeg
data in die struktuur.

45
00:02:03,580 --> 00:02:07,380
Spesifiek wil ons die
data self om ons te vertel

46
00:02:07,380 --> 00:02:09,725
waar dit moet gaan in die struktuur.

47
00:02:09,725 --> 00:02:12,850
En as ons dan nodig om te sien of dit is in
die struktuur, indien ons dit nodig om dit te vind,

48
00:02:12,850 --> 00:02:16,610
ons wil om te kyk na die data
weer en in staat wees om effektief,

49
00:02:16,610 --> 00:02:18,910
die gebruik van die data, lukraak toegang nie.

50
00:02:18,910 --> 00:02:20,700
Net deur te kyk na die
data wat ons moet hê

51
00:02:20,700 --> 00:02:25,890
'n idee van waar ons presies is
gaan om dit te vind in die hash tafel.

52
00:02:25,890 --> 00:02:28,770
>> Nou is die nadeel van 'n hash
tabel is dat hulle is regtig

53
00:02:28,770 --> 00:02:31,770
baie sleg by die bestel of sorteer data.

54
00:02:31,770 --> 00:02:34,970
En in die feit, as jy begin
om dit te gebruik om te bestel of soort

55
00:02:34,970 --> 00:02:37,990
data verloor jy al die
voordele wat jy voorheen

56
00:02:37,990 --> 00:02:40,710
het in terme van inplanting en skrap.

57
00:02:40,710 --> 00:02:44,060
Die tyd raak nader aan
theta van N, en ons het basies

58
00:02:44,060 --> 00:02:45,530
agteruitgang in 'n geskakelde lys.

59
00:02:45,530 --> 00:02:48,850
En so het ons net wil hash gebruik
tafels as ons nie omgee

60
00:02:48,850 --> 00:02:51,490
of data is gesorteer.

61
00:02:51,490 --> 00:02:54,290
Vir die konteks waarin
jy sal gebruik om hulle in CS50

62
00:02:54,290 --> 00:02:58,900
het jy waarskynlik nie omgee
dat die data is gesorteer.

63
00:02:58,900 --> 00:03:03,170
>> So 'n gemors tafel is 'n kombinasie
twee afsonderlike stukke

64
00:03:03,170 --> 00:03:04,980
waarmee ons bekend is.

65
00:03:04,980 --> 00:03:07,930
Die eerste is 'n funksie, wat
ons gewoonlik noem 'n hash funksie.

66
00:03:07,930 --> 00:03:11,760
En dat hash funksie gaan
terug sommige nie-negatiewe heelgetal wat

67
00:03:11,760 --> 00:03:14,870
ons gewoonlik noem 'n hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
Die tweede stuk is 'n skikking, wat
kan stoor data van die tipe wat ons

69
00:03:20,230 --> 00:03:22,190
wil plaas in die data struktuur.

70
00:03:22,190 --> 00:03:24,310
Ons sal te hou oor die
geskakelde lys element vir nou

71
00:03:24,310 --> 00:03:27,810
en net begin met die basiese beginsels van 'n
hash tabel om jou kop te kry om dit

72
00:03:27,810 --> 00:03:30,210
en dan sal ons dalk blaas
jou gedagtes 'n bietjie wanneer ons

73
00:03:30,210 --> 00:03:32,920
kombineer skikkings en skakel lyste saam.

74
00:03:32,920 --> 00:03:35,590
>> Die basiese idee al
is ons 'n paar data te neem.

75
00:03:35,590 --> 00:03:37,860
Ons loop dat die data deur middel van
die hash funksie.

76
00:03:37,860 --> 00:03:41,980
En so het die data verwerk
en dit spoeg 'n aantal, OK?

77
00:03:41,980 --> 00:03:44,890
En dan met dat die getal
ons het net die data te stoor

78
00:03:44,890 --> 00:03:48,930
ons wil slaan in die
opgestel by die plek.

79
00:03:48,930 --> 00:03:53,990
So byvoorbeeld het ons miskien
hierdie hash tafel snare.

80
00:03:53,990 --> 00:03:57,350
Dit het 10 elemente in dit, so
kan ons 10 snare inpas nie.

81
00:03:57,350 --> 00:03:59,320
>> Kom ons sê ons wil hash John.

82
00:03:59,320 --> 00:04:02,979
So John as die data wat ons wil voeg
in hierdie hash tafel iewers.

83
00:04:02,979 --> 00:04:03,770
Waar kom ons sit dit?

84
00:04:03,770 --> 00:04:05,728
Wel tipies met 'n
array so ver moontlik ons

85
00:04:05,728 --> 00:04:07,610
sou dit in verskeidenheid ligging 0.

86
00:04:07,610 --> 00:04:09,960
Maar nou het ons hierdie nuwe hash funksie.

87
00:04:09,960 --> 00:04:13,180
>> En laat ons sê dat ons hardloop John
deur middel van hierdie hash funksie

88
00:04:13,180 --> 00:04:15,417
en dit is spoeg 4.

89
00:04:15,417 --> 00:04:17,500
Wel, dit is waar ons
gaan wil John sit.

90
00:04:17,500 --> 00:04:22,050
Ons wil John opgestel plek sit
4, want as ons hash John again--

91
00:04:22,050 --> 00:04:23,810
Kom ons sê ons later
wil soek en kyk

92
00:04:23,810 --> 00:04:26,960
As John bestaan ​​in hierdie hash
table-- al wat ons moet doen

93
00:04:26,960 --> 00:04:30,310
is loop dit deur dieselfde hash
funksie, kry die nommer 4 uit

94
00:04:30,310 --> 00:04:33,929
en in staat wees om John te vind
onmiddellik in ons data struktuur.

95
00:04:33,929 --> 00:04:34,720
Dit is redelik goed.

96
00:04:34,720 --> 00:04:36,928
>> Kom ons sê dat ons dit nou te doen
weer, wil ons hash Paul.

97
00:04:36,928 --> 00:04:39,446
Ons wil Paul voeg
in hierdie hash tafel.

98
00:04:39,446 --> 00:04:42,070
Kom ons sê dat ons hierdie keer hardloop
Paulus deur die hash funksie,

99
00:04:42,070 --> 00:04:44,600
die hashcode wat gegenereer is 6.

100
00:04:44,600 --> 00:04:47,340
Wel nou kan ons Paulus sit
in die skikking plek 6.

101
00:04:47,340 --> 00:04:50,040
En as ons nodig het om te kyk of
Paul is in hierdie hash tafel,

102
00:04:50,040 --> 00:04:53,900
al wat ons nodig het om te doen, is hardloop Paul
deur die hash funksie weer

103
00:04:53,900 --> 00:04:55,830
en ons gaan weer uit te kry 6.

104
00:04:55,830 --> 00:04:57,590
>> En dan ons net kyk
op array plek 6.

105
00:04:57,590 --> 00:04:58,910
Paulus is daar?

106
00:04:58,910 --> 00:05:00,160
As dit so is, is hy in die hash tafel.

107
00:05:00,160 --> 00:05:01,875
Is Paulus nie daar?

108
00:05:01,875 --> 00:05:03,000
Hy is nie in die hash tafel.

109
00:05:03,000 --> 00:05:05,720
Dit is redelik eenvoudig.

110
00:05:05,720 --> 00:05:07,770
>> Nou hoe kan jy 'n hash funksie definieer?

111
00:05:07,770 --> 00:05:11,460
Wel daar is regtig geen beperking op die
aantal moontlike hash funksies.

112
00:05:11,460 --> 00:05:14,350
In werklikheid is daar is 'n aantal van die baie,
regtig 'n goeie kinders op die internet.

113
00:05:14,350 --> 00:05:17,560
Daar is 'n aantal van die baie,
regtig slegte mense op die internet.

114
00:05:17,560 --> 00:05:21,080
Dit is ook redelik maklik
om 'n slegte een te skryf.

115
00:05:21,080 --> 00:05:23,760
>> So, wat maak 'n goeie
hash funksie, reg?

116
00:05:23,760 --> 00:05:27,280
Wel, 'n goeie hash funksie moet
gebruik slegs die data wat hashed,

117
00:05:27,280 --> 00:05:29,420
en al die data wat hashed.

118
00:05:29,420 --> 00:05:32,500
Sodat ons nie wil anything-- gebruik
ons nie iets inkorporeer

119
00:05:32,500 --> 00:05:35,560
anders as die data.

120
00:05:35,560 --> 00:05:37,080
En ons wil al die data te gebruik.

121
00:05:37,080 --> 00:05:39,830
Ons wil nie net gebruik 'n stuk
dit, ons wil almal dit te gebruik.

122
00:05:39,830 --> 00:05:41,710
A hash funksie moet
ook deterministies wees.

123
00:05:41,710 --> 00:05:42,550
Wat beteken dit?

124
00:05:42,550 --> 00:05:46,200
Wel dit beteken dat elke keer as ons
slaag die presiese dieselfde stuk data

125
00:05:46,200 --> 00:05:50,040
in die hash funksie het ons altyd
kry dieselfde hashcode uit.

126
00:05:50,040 --> 00:05:52,870
As ek slaag John in die
hash funksie ek uit 4.

127
00:05:52,870 --> 00:05:56,110
Ek moet in staat wees om dit te doen 10000
keer en ek sal altyd 4.

128
00:05:56,110 --> 00:06:00,810
Sodat daar geen ewekansige getalle effektief
betrokke kan wees in ons hash tables--

129
00:06:00,810 --> 00:06:02,750
in ons hash funksies.

130
00:06:02,750 --> 00:06:05,750
>> A hash funksie moet ook
eenvormig versprei data.

131
00:06:05,750 --> 00:06:09,700
As elke keer as jy data loop deur die
hash funksie kry jy die hashcode 0,

132
00:06:09,700 --> 00:06:11,200
dit is waarskynlik nie so groot nie, reg?

133
00:06:11,200 --> 00:06:14,600
Jy wil waarskynlik groot
'n verskeidenheid van hash kodes.

134
00:06:14,600 --> 00:06:17,190
Ook dinge kan versprei
dwarsdeur die tafel.

135
00:06:17,190 --> 00:06:23,210
En ook dit sou 'n groot as werklik
soortgelyke data, soos John en Jonathan,

136
00:06:23,210 --> 00:06:26,320
Miskien is versprei om te weeg
verskillende plekke in die hash tafel.

137
00:06:26,320 --> 00:06:28,750
Dit sou 'n mooi voordeel wees.

138
00:06:28,750 --> 00:06:31,250
>> Hier is 'n voorbeeld van 'n hash funksie.

139
00:06:31,250 --> 00:06:33,150
Ek het hierdie een vroeër.

140
00:06:33,150 --> 00:06:35,047
Dit is nie 'n besonder
goeie hash funksie

141
00:06:35,047 --> 00:06:37,380
vir redes wat nie regtig
dra gaan in nou.

142
00:06:37,380 --> 00:06:41,040
Maar jy sien wat gaan hier aan?

143
00:06:41,040 --> 00:06:44,420
Dit lyk asof ons 'n veranderlike verklaar
genoem som en die opstel van dit gelyk aan 0.

144
00:06:44,420 --> 00:06:50,010
En dan glo ek om iets te doen
so lank as strstr [j] nie gelyk is

145
00:06:50,010 --> 00:06:52,490
om agteroorskuinsstreep 0.

146
00:06:52,490 --> 00:06:54,870
Wat kan ek daar?

147
00:06:54,870 --> 00:06:57,440
>> Dit is basies net 'n ander
manier van die implementering van [? strl?]

148
00:06:57,440 --> 00:06:59,773
en die opsporing Wanneer jy
aan die einde van die tou.

149
00:06:59,773 --> 00:07:02,480
So ek het nie eintlik om
bereken die lengte van die string,

150
00:07:02,480 --> 00:07:05,640
Ek is net die gebruik toe ek die
backslash 0 karakter Ek weet

151
00:07:05,640 --> 00:07:07,185
Ek het die einde van die string bereik.

152
00:07:07,185 --> 00:07:09,560
En dan gaan ek hou
iterating deur daardie string,

153
00:07:09,560 --> 00:07:15,310
toevoeging van strstr [j] op te som, en dan aan die
einde van die dag gaan som mod terugkeer

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

155
00:07:16,200 --> 00:07:18,700
>> Basies al hierdie hash
funksie doen, is die toevoeging van

156
00:07:18,700 --> 00:07:23,450
al die ASCII waardes van
my string, en dan is dit

157
00:07:23,450 --> 00:07:26,390
terugkeer paar hashcode
Gemodificeerde deur HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Dit is waarskynlik die grootte
van my skikking, reg?

159
00:07:29,790 --> 00:07:33,160
Ek wil nie te wees om hash
kodes as my skikking is van die grootte 10,

160
00:07:33,160 --> 00:07:35,712
Ek wil nie te wees om
uit hash kodes 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, Ek kan nie dinge in
die plekke van die skikking,

162
00:07:38,690 --> 00:07:39,790
dat onwettige sou wees.

163
00:07:39,790 --> 00:07:42,130
Ek sal ly 'n segmentering skuld.

164
00:07:42,130 --> 00:07:45,230
>> Nou hier is nog 'n vinnige eenkant.

165
00:07:45,230 --> 00:07:48,470
Algemeen is jy waarskynlik nie van plan om
wil jou eie hash funksies te skryf.

166
00:07:48,470 --> 00:07:50,997
Dit is eintlik 'n bietjie van
'n kuns, nie 'n wetenskap.

167
00:07:50,997 --> 00:07:52,580
En daar is 'n baie wat gaan in hulle.

168
00:07:52,580 --> 00:07:55,288
Die internet, soos ek gesê het, is vol
van baie goeie hash funksies,

169
00:07:55,288 --> 00:07:58,470
en jy moet die internet te gebruik
vind hash funksies, want dit is regtig

170
00:07:58,470 --> 00:08:03,230
net soort van 'n onnodige
vermorsing van tyd om jou eie te skep.

171
00:08:03,230 --> 00:08:05,490
>> Jy kan eenvoudiges skryf
vir die toets doeleindes.

172
00:08:05,490 --> 00:08:08,323
Maar wanneer jy eintlik gaan
begin hashing data en om dit te stoor

173
00:08:08,323 --> 00:08:10,780
in 'n hash tafel jy
waarskynlik gaan om te wil

174
00:08:10,780 --> 00:08:14,580
om 'n funksie wat gegenereer gebruik
vir jou, wat bestaan ​​op die internet.

175
00:08:14,580 --> 00:08:17,240
As jy net seker
om jou bronne te noem.

176
00:08:17,240 --> 00:08:21,740
Daar is geen rede om
plagiaat pleeg hier nie.

177
00:08:21,740 --> 00:08:25,370
>> Die rekenaarwetenskap gemeenskap is
beslis groei, en regtig waardes

178
00:08:25,370 --> 00:08:28,796
open source, en dit is werklik belangrik
om jou bronne te noem, sodat mense

179
00:08:28,796 --> 00:08:30,670
kan toeskrywing te kry vir
die werk wat hulle is

180
00:08:30,670 --> 00:08:32,312
doen tot voordeel van die gemeenskap.

181
00:08:32,312 --> 00:08:34,020
So altyd sure-- wees
en nie net vir hash

182
00:08:34,020 --> 00:08:37,270
funksies, maar oor die algemeen as jy
gebruik van 'n buite-kode bron

183
00:08:37,270 --> 00:08:38,299
altyd noem jou bron.

184
00:08:38,299 --> 00:08:43,500
Gee krediet aan die persoon wat dit gedoen
sommige van die werk, sodat jy nie hoef te.

185
00:08:43,500 --> 00:08:46,720
>> OK so laat heroorweeg hierdie
hash tafel vir 'n tweede.

186
00:08:46,720 --> 00:08:48,780
Dit is waar ons opgehou
af na ons plaas

187
00:08:48,780 --> 00:08:53,300
John en Paul in hierdie hash tafel.

188
00:08:53,300 --> 00:08:55,180
Het jy 'n probleem hier te sien?

189
00:08:55,180 --> 00:08:58,410
Jy kan sien twee.

190
00:08:58,410 --> 00:09:02,240
Maar in die besonder, het jy
sien dit moontlike probleem?

191
00:09:02,240 --> 00:09:06,770
>> Wat gebeur as ek hash Ringo en dit
blyk dat na die verwerking

192
00:09:06,770 --> 00:09:14,000
dat die data deur die hash funksie
Ringo gegenereer ook die hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Ek het al 'data op
hashcode-- verskeidenheid ligging 6.

194
00:09:16,810 --> 00:09:22,000
So dit is waarskynlik gaan om 'n bietjie te wees
van 'n probleem vir my nou, reg?

195
00:09:22,000 --> 00:09:23,060
>> Ons noem dit 'n botsing.

196
00:09:23,060 --> 00:09:26,460
En die botsing vind plaas wanneer twee
stukkies data loop deur dieselfde hash

197
00:09:26,460 --> 00:09:29,200
funksie lewer dieselfde hashcode.

198
00:09:29,200 --> 00:09:32,850
Vermoedelik het ons nog wil beide kry
stukke data in die hash tafel,

199
00:09:32,850 --> 00:09:36,330
anders sou ons nie hardloop Ringo
arbitrêr deur die hash funksie.

200
00:09:36,330 --> 00:09:40,870
Ons wil vermoedelik te kry
Ringo in daardie skikking.

201
00:09:40,870 --> 00:09:46,070
>> Hoe doen ons dit al is, as hy
en Paul beide opbrengs hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Ons wil nie oorskryf Paul,
ons wil Paulus ook daar wees.

203
00:09:49,520 --> 00:09:52,790
So moet ons 'n manier te vind om te kry
elemente in die hash tafel wat

204
00:09:52,790 --> 00:09:56,550
steeds bewaar ons vinnige
inplanting en vinnige blik op.

205
00:09:56,550 --> 00:10:01,350
En een manier om dit te hanteer, is om
iets genoem lineêre indringende doen.

206
00:10:01,350 --> 00:10:04,170
>> Die gebruik van hierdie metode as ons 'n
botsing, wel, wat doen ons?

207
00:10:04,170 --> 00:10:08,580
Wel, ons kan hom nie in die rigting plek
6, of wat ook al hashcode was gegenereer,

208
00:10:08,580 --> 00:10:10,820
laat hom te hashcode plus 1.

209
00:10:10,820 --> 00:10:13,670
En as dit is vol laat se
het hom in hashcode plus 2.

210
00:10:13,670 --> 00:10:17,420
Die voordeel van hierdie wese as hy
nie presies waar ons dink hy is,

211
00:10:17,420 --> 00:10:20,850
en ons het om te begin soek,
Miskien het ons nie te ver gaan nie.

212
00:10:20,850 --> 00:10:23,900
Miskien het ons nie hoef te soek
alle n elemente van die hash tafel.

213
00:10:23,900 --> 00:10:25,790
Miskien moet ons soek
'n paar van hulle.

214
00:10:25,790 --> 00:10:30,680
>> En so is ons nog steeds neig na
dat die gemiddelde geval wat naby aan 1 vs

215
00:10:30,680 --> 00:10:34,280
naby aan n, so miskien is dit sal werk.

216
00:10:34,280 --> 00:10:38,010
So laat ons sien hoe dit
kan uit te werk in die werklikheid.

217
00:10:38,010 --> 00:10:41,460
En laat ons sien of miskien kan ons spoor
die probleem wat hier mag voorkom.

218
00:10:41,460 --> 00:10:42,540
>> Kom ons sê ons hash Bart.

219
00:10:42,540 --> 00:10:45,581
So nou gaan ons 'n nuwe stel hardloop
snare deur die hash funksie,

220
00:10:45,581 --> 00:10:48,460
en ons hardloop Bart deur die hash
funksie, kry ons hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Ons neem 'n blik, sien ons 6 is
leeg, sodat ons kan Bart daar te vestig.

222
00:10:52,100 --> 00:10:55,410
>> Nou hash ons Lisa en dat
genereer ook hashcode 6.

223
00:10:55,410 --> 00:10:58,330
Wel, nou dat ons die gebruik van hierdie
lineêre indringende metode begin ons op 6,

224
00:10:58,330 --> 00:10:59,330
ons sien dat 6 is vol.

225
00:10:59,330 --> 00:11:00,990
Ons kan nie 'Lisa in 6.

226
00:11:00,990 --> 00:11:02,090
So waar gaan ons heen?

227
00:11:02,090 --> 00:11:03,280
Kom ons gaan na 7.

228
00:11:03,280 --> 00:11:04,610
7 se leë, so wat werk.

229
00:11:04,610 --> 00:11:06,510
Kom ons stel Lisa daar.

230
00:11:06,510 --> 00:11:10,200
>> Nou hash ons Homer en ons kry 7.

231
00:11:10,200 --> 00:11:13,380
OK goed ons weet dat 7 se volle
nou, so ons kan nie daar sit Homer.

232
00:11:13,380 --> 00:11:14,850
So laat ons gaan na 8.

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

234
00:11:15,664 --> 00:11:18,330
Ja, en 8 se naby aan 7, so as
ons het om te begin soek ons

235
00:11:18,330 --> 00:11:20,020
nie van plan om te ver gaan.

236
00:11:20,020 --> 00:11:22,860
En so laat sit Homer op 8.

237
00:11:22,860 --> 00:11:25,151
>> Nou hash ons Maggie en
terug 3, dankie tog

238
00:11:25,151 --> 00:11:26,650
ons is in staat om net sit Maggie daar.

239
00:11:26,650 --> 00:11:29,070
Ons het nie nodig om enige te doen
soort van indringende vir daardie.

240
00:11:29,070 --> 00:11:32,000
Nou hash ons Marge, en
Marge terug ook 6.

241
00:11:32,000 --> 00:11:39,560
>> Wel 6 is vol, 7 is vol, 8 is vol,
9, alles reg dank God, 9 is leeg.

242
00:11:39,560 --> 00:11:41,600
Ek kan Marge sit op 9.

243
00:11:41,600 --> 00:11:45,280
Al wat ons kan sien dat ons begin
om hierdie probleem waar ons nou is het

244
00:11:45,280 --> 00:11:48,780
begin om dinge soort rek
van ver weg van hul hash kodes.

245
00:11:48,780 --> 00:11:52,960
En dat theta van 1, dat die gemiddelde
geval van wat konstant tyd

246
00:11:52,960 --> 00:11:56,560
begin om 'n bietjie te kry more--
begin om 'n bietjie meer geneig

247
00:11:56,560 --> 00:11:58,050
teenoor theta van n.

248
00:11:58,050 --> 00:12:01,270
Ons begin om te verloor wat
voordeel van hash tabelle.

249
00:12:01,270 --> 00:12:03,902
>> Hierdie probleem dat ons nou net gesien het
is iets genoem clustering.

250
00:12:03,902 --> 00:12:06,360
En wat is regtig sleg oor
groepering is dat wanneer jy nou

251
00:12:06,360 --> 00:12:09,606
het twee elemente wat kant is deur
kant maak dit selfs meer waarskynlik,

252
00:12:09,606 --> 00:12:11,480
jy dubbel die het
kans dat jy gaan

253
00:12:11,480 --> 00:12:13,516
na 'n ander botsing het
met daardie cluster,

254
00:12:13,516 --> 00:12:14,890
en die cluster sal groei vir een.

255
00:12:14,890 --> 00:12:19,640
En jy sal aanhou groei en groei
jou waarskynlikheid van 'n botsing.

256
00:12:19,640 --> 00:12:24,470
En uiteindelik is dit net so erg
as nie sorteer die data op alle.

257
00:12:24,470 --> 00:12:27,590
>> Die ander probleem is egter ons
steeds, en so ver tot op hierdie punt,

258
00:12:27,590 --> 00:12:30,336
ons het net soort van nie
verstaan ​​wat 'n hash tafel is,

259
00:12:30,336 --> 00:12:31,960
ons nog net ruimte vir 10 snare.

260
00:12:31,960 --> 00:12:37,030
As ons wil voortgaan om hash
die burgers van Springfield,

261
00:12:37,030 --> 00:12:38,790
kan ons net kry 10 van hulle daar.

262
00:12:38,790 --> 00:12:42,619
En as ons probeer en voeg 'n 11de of 12de,
Ons het nie 'n plek om hulle te sit.

263
00:12:42,619 --> 00:12:45,660
Ons kon net spin rond in
sirkels probeer om 'n leë plek te vind,

264
00:12:45,660 --> 00:12:49,000
en ons dalk vashaak
in 'n oneindige lus.

265
00:12:49,000 --> 00:12:51,810
>> So hierdie soort van leen aan die idee
van iets genoem chaining.

266
00:12:51,810 --> 00:12:55,790
En dit is waar ons gaan bring
geskakelde lyste terug in die prentjie.

267
00:12:55,790 --> 00:13:01,300
Wat as in plaas van die stoor net
die data self in die skikking,

268
00:13:01,300 --> 00:13:04,471
elke element van die skikking kon
hou verskeie stukke data?

269
00:13:04,471 --> 00:13:05,970
Goed dat nie sin maak nie, reg?

270
00:13:05,970 --> 00:13:09,280
Ons weet dat 'n skikking kan net
hold-- elke element van 'n skikking

271
00:13:09,280 --> 00:13:12,930
kan slegs een stuk
van data van daardie tipe data.

272
00:13:12,930 --> 00:13:16,750
>> Maar wat as die tipe data
is 'n geskakelde lys, reg?

273
00:13:16,750 --> 00:13:19,830
So, wat as elke
element van die skikking was

274
00:13:19,830 --> 00:13:22,790
'n verwysing na die hoof van 'n geskakelde lys?

275
00:13:22,790 --> 00:13:24,680
En dan kan ons bou
diegene geskakelde lyste

276
00:13:24,680 --> 00:13:27,120
en groei hulle arbitrêr,
omdat geskakelde lyste toelaat

277
00:13:27,120 --> 00:13:32,090
ons om te groei en krimp 'n baie meer
buigsaam as 'n skikking nie.

278
00:13:32,090 --> 00:13:34,210
So, wat as ons nou gebruik,
Ons gebruik dit reg?

279
00:13:34,210 --> 00:13:37,760
Ons begin om die kettings te groei
Uit hierdie verskeidenheid plekke.

280
00:13:37,760 --> 00:13:40,740
>> Nou kan ons pas 'n oneindige
bedrag van data, of nie oneindig,

281
00:13:40,740 --> 00:13:44,170
'n arbitrêre bedrag van
data, in ons hash tafel

282
00:13:44,170 --> 00:13:47,760
sonder om ooit loop in
die probleem van 'n botsing.

283
00:13:47,760 --> 00:13:50,740
Ons het ook uitgeskakel
groepering deur dit te doen.

284
00:13:50,740 --> 00:13:54,380
En goed ons weet dat wanneer ons voeg
in 'n geskakelde lys, as jy onthou

285
00:13:54,380 --> 00:13:57,779
van ons video op geskakelde lyste, enkel
gekoppel lyste en dubbel geskakelde lyste,

286
00:13:57,779 --> 00:13:59,070
dit is 'n konstante werking.

287
00:13:59,070 --> 00:14:00,710
Ons is net die toevoeging aan die voorkant.

288
00:14:00,710 --> 00:14:04,400
>> En kyk op, en ons weet
wat lyk in 'n geskakelde lys

289
00:14:04,400 --> 00:14:05,785
kan 'n probleem wees, reg?

290
00:14:05,785 --> 00:14:07,910
Ons het om te soek deur
dit van begin tot einde.

291
00:14:07,910 --> 00:14:10,460
Daar is geen ewekansige
toegang in 'n geskakelde lys.

292
00:14:10,460 --> 00:14:15,610
Maar as in plaas van om 'n verband
lys waar 'n lookup O van n sal wees,

293
00:14:15,610 --> 00:14:19,590
ons het nou 10 geskakelde lyste,
of 1000 geskakelde lyste,

294
00:14:19,590 --> 00:14:24,120
nou is dit O van n gedeel deur 10,
of O van n gedeel deur 1000.

295
00:14:24,120 --> 00:14:26,940
>> En terwyl ons praat
teoreties oor kompleksiteit

296
00:14:26,940 --> 00:14:30,061
ons ignoreer konstantes, in die werklike
wêreld hierdie dinge eintlik saak,

297
00:14:30,061 --> 00:14:30,560
reg?

298
00:14:30,560 --> 00:14:33,080
Ons het eintlik sal sien
dat dit gebeur

299
00:14:33,080 --> 00:14:36,610
10 keer vinniger te hardloop,
of 1000 keer vinniger,

300
00:14:36,610 --> 00:14:41,570
omdat ons die verspreiding van 'n lang
ketting oor 1000 kleiner kettings.

301
00:14:41,570 --> 00:14:45,090
En so elke keer wanneer ons moet soek
deur een van daardie kettings wat ons kan

302
00:14:45,090 --> 00:14:50,290
ignoreer die 999 kettings ons nie omgee
oor, en net soek daardie een.

303
00:14:50,290 --> 00:14:53,220
>> Wat is gemiddeld tot
wees 1000 keer korter.

304
00:14:53,220 --> 00:14:56,460
En so het ons nog soort van
neig na dié gemiddelde geval

305
00:14:56,460 --> 00:15:01,610
om konstante tyd, maar
net omdat ons gebruik te maak

306
00:15:01,610 --> 00:15:03,730
verdeel deur sommige groot konstante faktor.

307
00:15:03,730 --> 00:15:05,804
Kom ons kyk hoe dit kan
eintlik lyk al is.

308
00:15:05,804 --> 00:15:08,720
So was dit die hash tafel moes ons
voordat ons verklaar hash tafel wat

309
00:15:08,720 --> 00:15:10,270
was in staat om van die stoor 10 snare.

310
00:15:10,270 --> 00:15:11,728
Ons is nie van plan om dit te doen nie.

311
00:15:11,728 --> 00:15:13,880
Ons weet reeds die
beperkinge van die metode.

312
00:15:13,880 --> 00:15:20,170
Nou ons hash tafel gaan wees
'n verskeidenheid van 10 knope, wysers

313
00:15:20,170 --> 00:15:22,120
aan hoofde van geskakelde lyste.

314
00:15:22,120 --> 00:15:23,830
>> En nou is dit null.

315
00:15:23,830 --> 00:15:26,170
Elkeen van die 10 wenke is van nul.

316
00:15:26,170 --> 00:15:29,870
Daar is niks in ons
hash tafel nou.

317
00:15:29,870 --> 00:15:32,690
>> Nou laat ons begin om 'n paar te sit
dinge in hierdie hash tafel.

318
00:15:32,690 --> 00:15:35,440
En laat ons sien hoe hierdie metode is
gaan baat ons 'n bietjie.

319
00:15:35,440 --> 00:15:36,760
Kom nou hash Joey.

320
00:15:36,760 --> 00:15:40,210
Ons sal die string Joey deur loop
'n hash funksie en ons terugkeer 6.

321
00:15:40,210 --> 00:15:41,200
Wel, wat doen ons nou?

322
00:15:41,200 --> 00:15:44,090
>> Wel, nou werk met geskakelde lyste,
ons is nie besig met skikkings.

323
00:15:44,090 --> 00:15:45,881
En toe ons werk
met geskakelde lyste ons

324
00:15:45,881 --> 00:15:49,790
weet ons nodig het om te begin dinamies
toekenning ruimte en die bou van kettings.

325
00:15:49,790 --> 00:15:54,020
Dit is soort van how-- dit is die kern
elemente van die bou van 'n geskakelde lys.

326
00:15:54,020 --> 00:15:57,670
So laat dinamies
toeken ruimte vir Joey,

327
00:15:57,670 --> 00:16:00,390
en dan laat hom toe te voeg tot die ketting.

328
00:16:00,390 --> 00:16:03,170
>> So nou kyk wat ons gedoen het.

329
00:16:03,170 --> 00:16:06,440
Wanneer ons hash Joey ons het die hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Nou is die wyser op array plek 6
dui op die hoof van 'n geskakelde lys,

331
00:16:11,790 --> 00:16:14,900
en nou is dit die enigste
element van 'n geskakelde lys.

332
00:16:14,900 --> 00:16:18,350
En die knoop in daardie
gekoppel lys is Joey.

333
00:16:18,350 --> 00:16:22,300
>> So as ons nodig het om te kyk Joey
later, het ons net weer hash Joey,

334
00:16:22,300 --> 00:16:26,300
ons kry 6 weer, want ons
hash funksie is deterministiese.

335
00:16:26,300 --> 00:16:30,400
En dan het ons begin by die hoof
van die geskakelde lys wys

336
00:16:30,400 --> 00:16:33,360
om deur array plek
6, en ons kan Itereer

337
00:16:33,360 --> 00:16:35,650
oor wat probeer om Joey te vind.

338
00:16:35,650 --> 00:16:37,780
En as ons bou aan ons
hash tafel effektief,

339
00:16:37,780 --> 00:16:41,790
en ons hash funksie effektief
om data goed versprei,

340
00:16:41,790 --> 00:16:45,770
gemiddeld elk van daardie gekoppel
lyste by elke array plek

341
00:16:45,770 --> 00:16:50,110
sal wees 10/01 van die grootte van as ons
moes net dit as 'n enkele groot

342
00:16:50,110 --> 00:16:51,650
geskakelde lys met alles daarin.

343
00:16:51,650 --> 00:16:55,670
>> As ons versprei dat groot gekoppel
lys regoor 10 geskakelde lyste

344
00:16:55,670 --> 00:16:57,760
elke lys sal wees 10/01 die grootte.

345
00:16:57,760 --> 00:17:01,432
En dus 10 keer vinniger
om te soek deur.

346
00:17:01,432 --> 00:17:02,390
So laat dit weer te doen.

347
00:17:02,390 --> 00:17:04,290
Kom nou hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> En kom ons sê Ross, wanneer ons dit doen
die hash kode wat ons terug te kry is 2.

349
00:17:07,540 --> 00:17:10,630
Wel nou is ons dinamiese ken 'n
nuwe node, ons sit Ross in daardie knoop,

350
00:17:10,630 --> 00:17:14,900
en ons nou sê array plek
2, in plaas van om te wys nul

351
00:17:14,900 --> 00:17:18,579
dui op die hoof van 'n gekoppelde
lys wie se enigste node is Ross.

352
00:17:18,579 --> 00:17:22,660
En ons kan hierdie een meer tyd te doen, het ons
kan hash Rachel en kry hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc 'n nuwe node, sit Rachel in
die node, en sê 'n verskeidenheid plek

354
00:17:25,490 --> 00:17:27,839
4 wys nou aan die hoof
van 'n geskakelde lys wie

355
00:17:27,839 --> 00:17:31,420
enigste element gebeur met Rachel wees.

356
00:17:31,420 --> 00:17:33,470
>> OK, maar wat gebeur as
ons het 'n botsing?

357
00:17:33,470 --> 00:17:38,560
Kom ons kyk hoe ons omgaan botsings
die gebruik van die afsonderlike aaneenskakeling metode.

358
00:17:38,560 --> 00:17:39,800
Kom ons hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Ons kry die hashcode 6.

360
00:17:41,094 --> 00:17:44,010
In ons vorige voorbeeld het ons net
stoor die snare in die skikking.

361
00:17:44,010 --> 00:17:45,980
Dit was 'n probleem.

362
00:17:45,980 --> 00:17:48,444
>> Ons wil nie afranselen
Joey, en ons het reeds

363
00:17:48,444 --> 00:17:51,110
gesien dat ons 'n paar groepering kan kry
probleme as ons probeer en stap

364
00:17:51,110 --> 00:17:52,202
deur en ondersoek.

365
00:17:52,202 --> 00:17:54,660
Maar wat as ons net soort van
behandel dit op dieselfde manier, reg?

366
00:17:54,660 --> 00:17:57,440
Dit is net soos voeg 'n element
aan die hoof van 'n geskakelde lys.

367
00:17:57,440 --> 00:18:00,220
Laat ons net malloc ruimte vir Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Ons sal sê Phoebe se volgende wyser punte
om die ou hoof van die geskakelde lys,

369
00:18:04,764 --> 00:18:07,180
en dan 6 net verwys na die
nuwe hoof van die geskakelde lys.

370
00:18:07,180 --> 00:18:10,150
En kyk nou, ons het Phoebe verander in.

371
00:18:10,150 --> 00:18:14,210
Ons kan nou stoor twee
elemente met hashcode 6,

372
00:18:14,210 --> 00:18:17,170
en ons weet nie enige probleme.

373
00:18:17,170 --> 00:18:20,147
>> Dit is pretty much al
daar is om te aaneenskakeling.

374
00:18:20,147 --> 00:18:21,980
En aaneenskakeling is beslis
die metode wat

375
00:18:21,980 --> 00:18:27,390
gaan die mees doeltreffende vir jou as om te wees
jy data stoor in 'n hash tafel.

376
00:18:27,390 --> 00:18:30,890
Maar hierdie kombinasie van
skikkings en geskakelde lyste

377
00:18:30,890 --> 00:18:36,080
saam 'n hash tafel regtig vorm
dramaties verbeter jou vermoë

378
00:18:36,080 --> 00:18:40,550
om groot hoeveelhede data stoor, en
baie vinnig en doeltreffend te soek

379
00:18:40,550 --> 00:18:41,630
deur daardie data.

380
00:18:41,630 --> 00:18:44,150
>> Daar is nog een
data struktuur daar buite

381
00:18:44,150 --> 00:18:48,700
wat dalk selfs 'n bietjie wees
beter in terme van die waarborg van

382
00:18:48,700 --> 00:18:51,920
dat ons inplanting, skrap, en
opkyk tye is selfs vinniger.

383
00:18:51,920 --> 00:18:55,630
En ons sal sien dat in 'n video op drieë gedruk.

384
00:18:55,630 --> 00:18:58,930
Ek is Doug Lloyd, dit is CS50.

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