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

2
00:00:00,500 --> 00:00:01,900
[TÓNLIST spila]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Við nú að þú
vita mikið um fylki,

5
00:00:09,150 --> 00:00:11,610
og þú veist mikið um tengd listum.

6
00:00:11,610 --> 00:00:13,650
Og við höfum ræða
kostir og gallar, þá erum við

7
00:00:13,650 --> 00:00:16,620
rætt um að tengja skrár
er hægt að fá stærri og minni,

8
00:00:16,620 --> 00:00:18,630
en þeir taka meira stærð.

9
00:00:18,630 --> 00:00:22,359
Fylki eru miklu meira einfalt að
nota, en þeir eru takmarkandi eins mikið

10
00:00:22,359 --> 00:00:24,900
eins og við höfum til að stilla stærð
array í upphafi

11
00:00:24,900 --> 00:00:26,910
og þá erum við fastur með það.

12
00:00:26,910 --> 00:00:30,470
>> En það er, að við höfum ansi mikið
búinn öllum efni okkar

13
00:00:30,470 --> 00:00:33,040
um sem tengjast listum og fylki.

14
00:00:33,040 --> 00:00:34,950
Eða höfum við?

15
00:00:34,950 --> 00:00:37,720
Kannski getum við gert eitthvað
jafnvel meira skapandi.

16
00:00:37,720 --> 00:00:40,950
Og þessi tegund af lánar
hugmyndin um kjötkássa töflunni.

17
00:00:40,950 --> 00:00:46,680
>> Svo í kjötkássa töflunni að við ætlum að reyna
sameina fjölda með tengda listanum.

18
00:00:46,680 --> 00:00:49,520
Við erum að fara að taka kostur
fylkisins, eins og af handahófi aðgang,

19
00:00:49,520 --> 00:00:53,510
að vera fær um að fara bara að array
þáttur 4 eða array þáttur 8

20
00:00:53,510 --> 00:00:55,560
án þess að þurfa að árétta yfir.

21
00:00:55,560 --> 00:00:57,260
Það er ansi hratt, ekki satt?

22
00:00:57,260 --> 00:01:00,714
>> En við viljum líka að hafa gögn okkar
uppbygging vera fær um að vaxa og skreppa.

23
00:01:00,714 --> 00:01:02,630
Við þurfum ekki, við gerum ekki
langar að vera takmarkaður.

24
00:01:02,630 --> 00:01:04,588
Og við viljum vera fær um
til að bæta við og fjarlægja hluti

25
00:01:04,588 --> 00:01:08,430
mjög auðveldlega, sem ef þú manst,
er mjög flókið með fjölda.

26
00:01:08,430 --> 00:01:11,650
Og við getum kallað þetta
nýr hlutur a kjötkássa borð.

27
00:01:11,650 --> 00:01:15,190
>> Og ef rétt útfærð,
við erum konar taka

28
00:01:15,190 --> 00:01:18,150
kostir beggja gögnum
mannvirki sem þú hefur nú þegar séð,

29
00:01:18,150 --> 00:01:19,880
fylki og tengd listum.

30
00:01:19,880 --> 00:01:23,070
Innsetning getur byrjað að
tilhneigingu til þeta af 1.

31
00:01:23,070 --> 00:01:26,207
Theta við höfum í raun ekki rætt,
en þeta er bara meðaltal ræða,

32
00:01:26,207 --> 00:01:27,540
hvað er í raun að fara að gerast.

33
00:01:27,540 --> 00:01:29,680
Þú ert ekki alltaf að fara að
hafa versta falli,

34
00:01:29,680 --> 00:01:32,555
og þú ert ekki alltaf að fara að hafa
besta falli, svo er það

35
00:01:32,555 --> 00:01:33,900
að meðaltali atburðarás?

36
00:01:33,900 --> 00:01:36,500
>> Jæja að meðaltali innsetning
í kjötkássa töflunni

37
00:01:36,500 --> 00:01:39,370
getur byrjað að fá nærri föstu tíma.

38
00:01:39,370 --> 00:01:41,570
Og eyðing er hægt að fá
nærri föstu tíma.

39
00:01:41,570 --> 00:01:44,440
Og útlit er hægt að fá
nærri föstu tíma.

40
00:01:44,440 --> 00:01:48,600
That's-- við höfum ekki gögn
uppbygging enn sem getur gert það,

41
00:01:48,600 --> 00:01:51,180
og svo þetta þegar hljómar
eins og a laglegur mikill hlutur.

42
00:01:51,180 --> 00:01:57,010
Við höfum í raun draga úr því
gallar hvers á eigin spýtur.

43
00:01:57,010 --> 00:01:59,160
>> Til að fá þessa frammistöðu
uppfærsla þó, við

44
00:01:59,160 --> 00:02:03,580
þarf að endurhugsa hvernig við bætum
gögn í uppbyggingu.

45
00:02:03,580 --> 00:02:07,380
Sérstaklega viljum við
Gögnin sjálf að segja okkur

46
00:02:07,380 --> 00:02:09,725
þar sem það ætti að fara í uppbyggingu.

47
00:02:09,725 --> 00:02:12,850
Og ef við þurfum þá að sjá hvort það er í
uppbyggingu, ef við þurfum að finna það,

48
00:02:12,850 --> 00:02:16,610
við viljum að líta á gögn
aftur og vera fær um að í raun,

49
00:02:16,610 --> 00:02:18,910
nota gögn, handahófi aðgang að honum.

50
00:02:18,910 --> 00:02:20,700
Bara með því að horfa á
gögn sem við ættum að hafa

51
00:02:20,700 --> 00:02:25,890
hugmynd um hvar nákvæmlega við erum
fara að finna það í kjötkássa töflunni.

52
00:02:25,890 --> 00:02:28,770
>> Nú hæðir af kjötkássa
Taflan er að þeir eru í raun

53
00:02:28,770 --> 00:02:31,770
ansi slæmt á röðun eða flokkun gagna.

54
00:02:31,770 --> 00:02:34,970
Og í raun, ef þú byrjar
að nota þá til að panta eða tegund

55
00:02:34,970 --> 00:02:37,990
gögn sem þú tapa öllum af
Kostir Þú áður

56
00:02:37,990 --> 00:02:40,710
hafði í skilmálar af innsetningu og eyðingu.

57
00:02:40,710 --> 00:02:44,060
Tíminn verður nær
þeta n, og við höfum í rauninni

58
00:02:44,060 --> 00:02:45,530
hörfuðu í tengda listanum.

59
00:02:45,530 --> 00:02:48,850
Og svo við viljum bara að nota kjötkássa
töflur ef við ekki sama um

60
00:02:48,850 --> 00:02:51,490
hvort gögn eru flokkuð.

61
00:02:51,490 --> 00:02:54,290
Fyrir því í hvaða samhengi
þú munt nota þær í CS50

62
00:02:54,290 --> 00:02:58,900
þú sennilega ekki sama
að gögnin séu flokkuð.

63
00:02:58,900 --> 00:03:03,170
>> Svo er kjötkássa borð sambland
af tveimur aðskildum stykki

64
00:03:03,170 --> 00:03:04,980
sem við erum kunnugir.

65
00:03:04,980 --> 00:03:07,930
Í fyrsta lagi er fall, sem
við köllum yfirleitt kjötkássa virka.

66
00:03:07,930 --> 00:03:11,760
Og það kjötkássa virka er að fara að
aftur sumir non-neikvæð heiltala, sem

67
00:03:11,760 --> 00:03:14,870
við köllum yfirleitt Tætifall, OK?

68
00:03:14,870 --> 00:03:20,230
Annað stykki er fylki, sem er
fær um að geyma gögn af gerðinni vér

69
00:03:20,230 --> 00:03:22,190
langar að setja inn gögn uppbygging.

70
00:03:22,190 --> 00:03:24,310
Við munum halda utan um
tengda listanum þáttur nú

71
00:03:24,310 --> 00:03:27,810
og bara byrja með grunnatriði a
kjötkássa borð að fá höfuð þitt í kringum það,

72
00:03:27,810 --> 00:03:30,210
og þá munum við kannski blása
hugur þinn svolítið þegar við

73
00:03:30,210 --> 00:03:32,920
sameina fylki og tengil listum saman.

74
00:03:32,920 --> 00:03:35,590
>> Grunnhugmyndin þó
er við tökum nokkur gögn.

75
00:03:35,590 --> 00:03:37,860
Við keyra þessi gögn í gegnum
kjötkássa virka.

76
00:03:37,860 --> 00:03:41,980
Og svo er úr gögnum
og það spits út fjölda, OK?

77
00:03:41,980 --> 00:03:44,890
Og þá með því að tala
við geyma bara gögn

78
00:03:44,890 --> 00:03:48,930
við viljum geyma í
array á þeim stað.

79
00:03:48,930 --> 00:03:53,990
Svo til dæmis að við höfum kannski
þetta kjötkássa borð af strengjum.

80
00:03:53,990 --> 00:03:57,350
Það fékk 10 þætti í henni, svo
við getum passa 10 strengi í það.

81
00:03:57,350 --> 00:03:59,320
>> Segjum að við viljum að kjötkássa Jóhannes.

82
00:03:59,320 --> 00:04:02,979
Svo John sem gögn sem við viljum að setja
í þessum kjötkássa borð einhvers staðar.

83
00:04:02,979 --> 00:04:03,770
Hvar eigum við að setja það?

84
00:04:03,770 --> 00:04:05,728
Jæja oftast með að
array svo langt að við líklega

85
00:04:05,728 --> 00:04:07,610
myndi setja það í array stað 0.

86
00:04:07,610 --> 00:04:09,960
En nú höfum við þetta nýja kjötkássa virka.

87
00:04:09,960 --> 00:04:13,180
>> Og við skulum segja að við að keyra John
í gegnum þetta kjötkássa virka

88
00:04:13,180 --> 00:04:15,417
og það er spits út 4.

89
00:04:15,417 --> 00:04:17,500
Jæja það er þar sem við erum
fara til að vilja setja Jóhannes.

90
00:04:17,500 --> 00:04:22,050
Við viljum að setja Jóhannes í array stað
4, því ef við kjötkássa Jóhannes again--

91
00:04:22,050 --> 00:04:23,810
skulum segja síðar við
langar að leita og sjá

92
00:04:23,810 --> 00:04:26,960
ef John til í þessum kjötkássa
table-- allt sem við þurfum að gera

93
00:04:26,960 --> 00:04:30,310
er að keyra það í gegnum sömu kjötkássa
virka, fá númer 4 út,

94
00:04:30,310 --> 00:04:33,929
og vera fær um að finna John
strax í gögn uppbygging okkar.

95
00:04:33,929 --> 00:04:34,720
Það er nokkuð gott.

96
00:04:34,720 --> 00:04:36,928
>> Segjum að við gerum nú þetta
aftur, viljum við kjötkássa Pál.

97
00:04:36,928 --> 00:04:39,446
Við viljum bæta Pál
í þessum kjötkássa töflunni.

98
00:04:39,446 --> 00:04:42,070
Við skulum segja að þessi tími hlaupum
Paul gegnum kjötkássa virka,

99
00:04:42,070 --> 00:04:44,600
sem Tætifall sem er myndaður er 6.

100
00:04:44,600 --> 00:04:47,340
Jæja nú getum við sett Pál
í array stað 6.

101
00:04:47,340 --> 00:04:50,040
Og ef við þurfum að horfa upp hvort
Paul er í þessu kjötkássa borð,

102
00:04:50,040 --> 00:04:53,900
allt sem við þurfum að gera er að keyra Paul
gegnum kjötkássa virka aftur

103
00:04:53,900 --> 00:04:55,830
og við erum að fara að fá 6 út aftur.

104
00:04:55,830 --> 00:04:57,590
>> Og þá erum við að líta bara
á array stað 6.

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

106
00:04:58,910 --> 00:05:00,160
Ef svo er, er hann í kjötkássa töflunni.

107
00:05:00,160 --> 00:05:01,875
Er Paul ekki þar?

108
00:05:01,875 --> 00:05:03,000
Hann er ekki í kjötkássa töflunni.

109
00:05:03,000 --> 00:05:05,720
Það er frekar einfalt.

110
00:05:05,720 --> 00:05:07,770
>> Nú hvernig þú skilgreinir kjötkássa virka?

111
00:05:07,770 --> 00:05:11,460
Jæja það er í raun engin takmörk fyrir því
Fjöldi hugsanlegra kjötkássa virka.

112
00:05:11,460 --> 00:05:14,350
Í raun er a tala af mjög,
virkilega góður sjálfur á internetinu.

113
00:05:14,350 --> 00:05:17,560
There er a tala af mjög,
virkilega slæmur sjálfur á internetinu.

114
00:05:17,560 --> 00:05:21,080
Það er líka frekar auðvelt
til að skrifa a slæmur einn.

115
00:05:21,080 --> 00:05:23,760
>> Og hvað gerir upp gott
kjötkássa virka, ekki satt?

116
00:05:23,760 --> 00:05:27,280
Jæja gott kjötkássa virka ætti
nota aðeins gögn sem tætt,

117
00:05:27,280 --> 00:05:29,420
og öll gögn sem tætt.

118
00:05:29,420 --> 00:05:32,500
Þannig að við viljum ekki að nota anything--
við ekki fella ekki neitt

119
00:05:32,500 --> 00:05:35,560
annað annað en gögnunum.

120
00:05:35,560 --> 00:05:37,080
Og við viljum að nota öll gögn.

121
00:05:37,080 --> 00:05:39,830
Við viljum ekki bara að nota stykki
um það, viljum við nota allt það.

122
00:05:39,830 --> 00:05:41,710
A kjötkássa virka ætti
einnig að vera deterministic.

123
00:05:41,710 --> 00:05:42,550
Hvað þýðir það?

124
00:05:42,550 --> 00:05:46,200
Jæja það þýðir að í hvert skipti sem við
fara nákvæmlega sömu stykki af gögn

125
00:05:46,200 --> 00:05:50,040
í kjötkássa virka við alltaf
fá sömu Tætifall út.

126
00:05:50,040 --> 00:05:52,870
Ef ég fara Jóhannes inn í
kjötkássa virka ég út 4.

127
00:05:52,870 --> 00:05:56,110
Ég ætti að vera fær um að gera það 10.000
sinnum og ég alltaf fá 4.

128
00:05:56,110 --> 00:06:00,810
Svo ekki af handahófi tölur í raun
Hægt er að taka þátt í kjötkássa okkar tables--

129
00:06:00,810 --> 00:06:02,750
í kjötkássa virka okkar.

130
00:06:02,750 --> 00:06:05,750
>> A kjötkássa virka ætti einnig
dreifið gögn.

131
00:06:05,750 --> 00:06:09,700
Ef hvert skipti sem þú keyrir gögn í gegnum
kjötkássa virka þú færð Tætifall 0,

132
00:06:09,700 --> 00:06:11,200
það er sennilega ekki svo mikill, ekki satt?

133
00:06:11,200 --> 00:06:14,600
Þú vilt sennilega að stór
a svið af kjötkássa númerum.

134
00:06:14,600 --> 00:06:17,190
Einnig það er hægt að dreifa
út um töflunni.

135
00:06:17,190 --> 00:06:23,210
Og einnig það væri frábært ef virkilega
svipuð gögn, eins og John og Jónatan,

136
00:06:23,210 --> 00:06:26,320
kannski voru breiða út til að vega
mismunandi stöðum í kjötkássa töflunni.

137
00:06:26,320 --> 00:06:28,750
Það væri gott kostur.

138
00:06:28,750 --> 00:06:31,250
>> Hér er dæmi um kjötkássa virka.

139
00:06:31,250 --> 00:06:33,150
Ég skrifaði þetta einn upp áðan.

140
00:06:33,150 --> 00:06:35,047
Það er ekki sérlega
gott kjötkássa virka

141
00:06:35,047 --> 00:06:37,380
ástæðum sem gera í raun ekki
bera að fara inn núna.

142
00:06:37,380 --> 00:06:41,040
En sérðu hvað er að gerast hér?

143
00:06:41,040 --> 00:06:44,420
Það virðist eins og við erum að lýsa breytu
heitir summan og setja það jafn 0.

144
00:06:44,420 --> 00:06:50,010
Og þá virðist ég er að gera eitthvað
svo lengi sem strstr [J] er ekki jafnt

145
00:06:50,010 --> 00:06:52,490
að sviga 0.

146
00:06:52,490 --> 00:06:54,870
Hvað er ég að gera það?

147
00:06:54,870 --> 00:06:57,440
>> Þetta er í rauninni bara annar
leið til að innleiða [? strl?]

148
00:06:57,440 --> 00:06:59,773
og greiningu á því hvenær þú hefur
náð í lok band.

149
00:06:59,773 --> 00:07:02,480
Svo ég þarf ekki að í raun
að reikna út lengd strengsins,

150
00:07:02,480 --> 00:07:05,640
Ég ætla bara að nota þegar ég lenti í
sviga 0 eðli ég veit

151
00:07:05,640 --> 00:07:07,185
Ég hef náð enda strengsins.

152
00:07:07,185 --> 00:07:09,560
Og þá er ég að fara að halda
iterating gegnum strengsins,

153
00:07:09,560 --> 00:07:15,310
bæta strstr [J] til að summa, og þá á
lok dagsins að fara að skila summu mod

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

155
00:07:16,200 --> 00:07:18,700
>> Í grundvallaratriðum allt þetta kjötkássa
virka er að gera er að bæta upp

156
00:07:18,700 --> 00:07:23,450
allar ASCII gildi
band mitt, og þá er það

157
00:07:23,450 --> 00:07:26,390
aftur sumir Tætifall
modded af HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Það er líklega stærð
af array minn, ekki satt?

159
00:07:29,790 --> 00:07:33,160
Ég vil ekki vera að fá kjötkássa
númer ef array minn er stærð 10,

160
00:07:33,160 --> 00:07:35,712
Ég vil ekki að vera að fá
út kjötkássa númer 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, ég get ekki sett hlutina í
þessum stöðum fylkisins,

162
00:07:38,690 --> 00:07:39,790
það væri ólöglegt.

163
00:07:39,790 --> 00:07:42,130
Ég myndi þjást skiptingu kenna.

164
00:07:42,130 --> 00:07:45,230
>> Nú er hér annar fljótur hliðar.

165
00:07:45,230 --> 00:07:48,470
Almennt þú ert líklega ekki að fara að
langar til að skrifa eigin kjötkássa þínar aðgerðir.

166
00:07:48,470 --> 00:07:50,997
Það er í raun hluti af
list, ekki vísindi.

167
00:07:50,997 --> 00:07:52,580
Og það er margt sem fer inn í þá.

168
00:07:52,580 --> 00:07:55,288
Netið, eins og ég sagði, er fullur
af mjög góðum kjötkássa virka,

169
00:07:55,288 --> 00:07:58,470
og þú ættir að nota internetið til
finna kjötkássa virka vegna þess að það er í raun

170
00:07:58,470 --> 00:08:03,230
bara svona óþarfa
tímasóun að búa til þinn eigin.

171
00:08:03,230 --> 00:08:05,490
>> Þú getur skrifað einföld og
prófanir.

172
00:08:05,490 --> 00:08:08,323
En þegar þú í raun ert að fara að
byrja hass gögn og geyma það

173
00:08:08,323 --> 00:08:10,780
í kjötkássa töflunni sem þú ert
líklega að fara til að vilja

174
00:08:10,780 --> 00:08:14,580
að nota sumir virka sem var mynda
fyrir þig, sem er til staðar á internetinu.

175
00:08:14,580 --> 00:08:17,240
Ef þú ekki vera bara viss
að vitna heimildir þínar.

176
00:08:17,240 --> 00:08:21,740
Það er engin ástæða til að
plagiarize neitt hér.

177
00:08:21,740 --> 00:08:25,370
>> The tölvunarfræði samfélag er
örugglega vaxa, og í raun gildi

178
00:08:25,370 --> 00:08:28,796
opinn uppspretta, og það er mjög mikilvægt
að vitna heimildir þínar þannig að fólk

179
00:08:28,796 --> 00:08:30,670
er hægt að fá heiður
þeirri vinnu sem þeir eru

180
00:08:30,670 --> 00:08:32,312
gera til hagsbóta fyrir samfélagið.

181
00:08:32,312 --> 00:08:34,020
Svo alltaf að vera sure--
og ekki bara fyrir kjötkássa

182
00:08:34,020 --> 00:08:37,270
virka, en yfirleitt þegar þér
nota kóða frá utanaðkomandi uppspretta,

183
00:08:37,270 --> 00:08:38,299
alltaf vitnað uppspretta.

184
00:08:38,299 --> 00:08:43,500
Gefðu inneign á mann sem gerði
sumir af the vinna svo þú þarft ekki að.

185
00:08:43,500 --> 00:08:46,720
>> OK þannig að við skulum rifja þetta
kjötkássa borð fyrir annað.

186
00:08:46,720 --> 00:08:48,780
Þetta er þar sem við fórum
burt eftir að við bætist

187
00:08:48,780 --> 00:08:53,300
John og Paul í þessum kjötkássa töflunni.

188
00:08:53,300 --> 00:08:55,180
Sérðu vandamál hér?

189
00:08:55,180 --> 00:08:58,410
Þú gætir séð tvo.

190
00:08:58,410 --> 00:09:02,240
En einkum gera þér
sjá þessi mögulegu vandamál?

191
00:09:02,240 --> 00:09:06,770
>> Hvað ef ég kjötkássa Ringo og það
kemur í ljós að eftir vinnslu

192
00:09:06,770 --> 00:09:14,000
að gögn um kjötkássa virka
Ringo mynda einnig Tætifall 6.

193
00:09:14,000 --> 00:09:16,810
Ég hef nú þegar fengið gögn á
hashcode-- array staðsetningu 6.

194
00:09:16,810 --> 00:09:22,000
Svo það er líklega að fara að vera svolítið
um vandamál fyrir mig núna, ekki satt?

195
00:09:22,000 --> 00:09:23,060
>> Við köllum þetta árekstur.

196
00:09:23,060 --> 00:09:26,460
Og árekstur á sér stað þegar tvær
stykki af gögnum keyra í gegnum sama kjötkássa

197
00:09:26,460 --> 00:09:29,200
virka skila sömu Tætifall.

198
00:09:29,200 --> 00:09:32,850
Væntanlega við viljum samt að fá bæði
stykki af gögnum í kjötkássa töflunni,

199
00:09:32,850 --> 00:09:36,330
annars myndum við ekki vera að keyra Ringo
geðþótta gegnum kjötkássa virka.

200
00:09:36,330 --> 00:09:40,870
Við viljum væntanlega að fá
Ringo í því fylki.

201
00:09:40,870 --> 00:09:46,070
>> Hvernig gerum við það þó, ef hann
og Paul bæði ávöxtun Tætifall 6?

202
00:09:46,070 --> 00:09:49,520
Við viljum ekki að skrifa Páli
við viljum Paul að vera þar líka.

203
00:09:49,520 --> 00:09:52,790
Þannig að við þurfum að finna leið til að fá
þættir í kjötkássa töflunni sem

204
00:09:52,790 --> 00:09:56,550
enn varðveitir Quick okkar
innsetningu og fljótur líta upp.

205
00:09:56,550 --> 00:10:01,350
Og ein leið til að takast á við það er að
gera eitthvað sem kallast línuleg leit.

206
00:10:01,350 --> 00:10:04,170
>> Using this aðferð ef við höfum
árekstur, vel, hvað gerum við?

207
00:10:04,170 --> 00:10:08,580
Jæja við getum ekki sett hann í array stað
6, eða hvað Tætifall var mynda,

208
00:10:08,580 --> 00:10:10,820
við skulum setja hann á Tætifall plús 1.

209
00:10:10,820 --> 00:10:13,670
Og ef það er fullt skulum
setja hann í Tætifall plús 2.

210
00:10:13,670 --> 00:10:17,420
Ávinningur af þessari veru ef hann er
ekki nákvæmlega hvar við teljum hann er,

211
00:10:17,420 --> 00:10:20,850
og við verðum að byrja að leita,
kannski við þurfum ekki að fara of langt.

212
00:10:20,850 --> 00:10:23,900
Kannski við þurfum ekki að leita
allt n þættir kjötkássa töflunni.

213
00:10:23,900 --> 00:10:25,790
Kannski verðum við að leita
a par af þeim.

214
00:10:25,790 --> 00:10:30,680
>> Og svo við erum enn tending átt
að meðaltali málið vera nálægt 1 vs

215
00:10:30,680 --> 00:10:34,280
nálægt n, svo kannski að ætla að vinna.

216
00:10:34,280 --> 00:10:38,010
Þannig að við skulum sjá hvernig þetta
gæti virkað út í raun.

217
00:10:38,010 --> 00:10:41,460
Og við skulum sjá hvort kannski getum við greint
vandamálið sem gæti komið hér.

218
00:10:41,460 --> 00:10:42,540
>> Segjum að við kjötkássa Bart.

219
00:10:42,540 --> 00:10:45,581
Svo nú erum við að fara að keyra nýja sett
af strengjum í gegnum kjötkássa virka,

220
00:10:45,581 --> 00:10:48,460
og hlaupum Bart gegnum kjötkássa
virka, fáum við Tætifall 6.

221
00:10:48,460 --> 00:10:52,100
Við lítum, sjáum við 6 er
tóm, þannig að við getum sett Bart þar.

222
00:10:52,100 --> 00:10:55,410
>> Nú erum við kjötkássa Lisa og að
Einnig býr Tætifall 6.

223
00:10:55,410 --> 00:10:58,330
Jæja núna þegar við erum að nota þetta
línuleg leit aðferð við að byrja á 6,

224
00:10:58,330 --> 00:10:59,330
sjáum við að 6 er fullt.

225
00:10:59,330 --> 00:11:00,990
Við getum ekki sett Lisa í 6.

226
00:11:00,990 --> 00:11:02,090
Svo þar sem við förum?

227
00:11:02,090 --> 00:11:03,280
Við skulum fara til 7.

228
00:11:03,280 --> 00:11:04,610
7 er tóm, svo virkar það.

229
00:11:04,610 --> 00:11:06,510
Svo skulum við setja Lisa þar.

230
00:11:06,510 --> 00:11:10,200
>> Nú erum við kjötkássa Homer og við fáum 7.

231
00:11:10,200 --> 00:11:13,380
OK vel við vitum að 7 er fullur
nú, þannig að við getum ekki sett Homer þar.

232
00:11:13,380 --> 00:11:14,850
Svo skulum við fara til 8.

233
00:11:14,850 --> 00:11:15,664
Er 8 í boði?

234
00:11:15,664 --> 00:11:18,330
Já, og 8 er tæplega 7, þannig að ef
við verðum að byrja að leita að við erum

235
00:11:18,330 --> 00:11:20,020
ekki að fara að þurfa að fara of langt.

236
00:11:20,020 --> 00:11:22,860
Og svo skulum setja Homer á 8.

237
00:11:22,860 --> 00:11:25,151
>> Nú erum við kjötkássa Maggie og
skilar 3, þakka góðvild

238
00:11:25,151 --> 00:11:26,650
við erum fær um að setja bara Maggie þar.

239
00:11:26,650 --> 00:11:29,070
Við þurfum ekki að gera eitthvað
konar leit fyrir það.

240
00:11:29,070 --> 00:11:32,000
Nú erum við kjötkássa Marge, og
Marge skilar líka 6.

241
00:11:32,000 --> 00:11:39,560
>> Jæja 6 er fullt, 7 er fullur, 8 er fullt,
9, allt í lagi að þakka Guði, 9 er tóm.

242
00:11:39,560 --> 00:11:41,600
Ég get sett Marge á 9.

243
00:11:41,600 --> 00:11:45,280
Nú þegar við sjáum að við erum að byrja
að hafa þetta vandamál þar sem nú við erum

244
00:11:45,280 --> 00:11:48,780
farin að teygja hlutina konar
af langt í burtu frá kjötkássa númerum þeirra.

245
00:11:48,780 --> 00:11:52,960
Og að þeta 1, að meðaltali
málið að vera stöðug tími,

246
00:11:52,960 --> 00:11:56,560
er farin að fá smá more--
farin að hafa smá meira

247
00:11:56,560 --> 00:11:58,050
að þeta á n.

248
00:11:58,050 --> 00:12:01,270
Við erum farin að missa það
Kosturinn við kjötkássa matskeið.

249
00:12:01,270 --> 00:12:03,902
>> Þetta vandamál sem við sáum bara
er eitthvað sem kallast Þyrping.

250
00:12:03,902 --> 00:12:06,360
Og hvað er raunverulega slæmt um
Þyrping er að þegar þú nú

251
00:12:06,360 --> 00:12:09,606
tvo hluti sem eru hlið við
hlið það gerir það enn líklegra,

252
00:12:09,606 --> 00:12:11,480
þú þarft tvöfalt
tækifæri, sem þú ert að fara

253
00:12:11,480 --> 00:12:13,516
að hafa aðra árekstur
með því þyrping,

254
00:12:13,516 --> 00:12:14,890
og þyrping mun vaxa um einn.

255
00:12:14,890 --> 00:12:19,640
Og þú munt halda að vaxa og vaxa
líkur á að fá árekstur.

256
00:12:19,640 --> 00:12:24,470
Og að lokum er það bara eins og slæmur
sem ekki flokka gögnin yfirleitt.

257
00:12:24,470 --> 00:12:27,590
>> Önnur vandamál er þó við
enn, og svo langt upp að þessum tímapunkti,

258
00:12:27,590 --> 00:12:30,336
við höfum bara verið svona
skilja hvað kjötkássa borð er,

259
00:12:30,336 --> 00:12:31,960
við enn bara pláss fyrir 10 strengi.

260
00:12:31,960 --> 00:12:37,030
Ef við viljum halda áfram að kjötkássa
íbúar Springfield,

261
00:12:37,030 --> 00:12:38,790
við getum aðeins fengið 10 af þeim þar.

262
00:12:38,790 --> 00:12:42,619
Og ef við reynum og bæta 11. eða 12.,
við höfum ekki stað til að setja þær.

263
00:12:42,619 --> 00:12:45,660
Við gætum bara að snúast um í
hringi að reyna að finna tóma blettur,

264
00:12:45,660 --> 00:12:49,000
og við kannski festast
í óendanlega lykkju.

265
00:12:49,000 --> 00:12:51,810
>> Þannig að þetta tegund af lánar hugmynd
eitthvað sem heitir læsa.

266
00:12:51,810 --> 00:12:55,790
Og þetta er þar sem við erum að fara að koma
tengd listum aftur inn í myndina.

267
00:12:55,790 --> 00:13:01,300
Hvað ef í stað þess að geyma bara
Gögnin sjálf í array,

268
00:13:01,300 --> 00:13:04,471
hvert þáttur í array gæti
halda mörg stykki af gögnum?

269
00:13:04,471 --> 00:13:05,970
Jæja það er ekki skynsamleg, ekki satt?

270
00:13:05,970 --> 00:13:09,280
Við vitum að array getur aðeins
hold-- hver þáttur af fjölda

271
00:13:09,280 --> 00:13:12,930
getur aðeins halda eitt stykki
af gögnum sem gögn tegund.

272
00:13:12,930 --> 00:13:16,750
>> En hvað ef að gögn gerð
er tengd lista, ekki satt?

273
00:13:16,750 --> 00:13:19,830
Svo hvað ef sérhver
þáttur í fylkinu var

274
00:13:19,830 --> 00:13:22,790
bendi á höfuð tengda listanum?

275
00:13:22,790 --> 00:13:24,680
Og þá erum við gætum byggt
þær sem tengjast listum

276
00:13:24,680 --> 00:13:27,120
og vaxa þeim geðþótta,
því tengd listum leyfa

277
00:13:27,120 --> 00:13:32,090
okkur að vaxa og skreppa a einhver fjöldi fleiri
sveigjanlegan en fylki gerir.

278
00:13:32,090 --> 00:13:34,210
Svo hvað ef við notum nú,
við að nýta þetta, ekki satt?

279
00:13:34,210 --> 00:13:37,760
Við byrjum að vaxa þessar keðjur
út af þessum array stöðum.

280
00:13:37,760 --> 00:13:40,740
>> Nú við getum passa óendanlega
Magn gagna, eða ekki óendanlegur,

281
00:13:40,740 --> 00:13:44,170
handahófskennt upphæð
gögn, í kjötkássa töflunni okkar

282
00:13:44,170 --> 00:13:47,760
án þess nokkurn tíma að keyra í
vandamálið á árekstri.

283
00:13:47,760 --> 00:13:50,740
Við höfum einnig eytt
Þyrping því að gera þetta.

284
00:13:50,740 --> 00:13:54,380
Og vel við vitum að þegar við setjum
í tengda listanum, ef þú manst

285
00:13:54,380 --> 00:13:57,779
frá vídeó okkar á tengd listum, ein
tengd listum og tvöfalt tengd listum,

286
00:13:57,779 --> 00:13:59,070
það er stöðug tími aðgerð.

287
00:13:59,070 --> 00:14:00,710
Við erum bara að bæta við að framan.

288
00:14:00,710 --> 00:14:04,400
>> Og fyrir að líta upp, vel við vitum
sem líta upp í tengda listanum

289
00:14:04,400 --> 00:14:05,785
getur verið vandamál, ekki satt?

290
00:14:05,785 --> 00:14:07,910
Við að leita í gegnum
það frá upphafi til enda.

291
00:14:07,910 --> 00:14:10,460
Það er engin handahófi
aðgangur í tengda listanum.

292
00:14:10,460 --> 00:14:15,610
En ef í stað þess að hafa einn tengd
listi þar sem útlit væri O af N,

293
00:14:15,610 --> 00:14:19,590
við höfum nú 10 tengist listum,
eða 1.000 tengd listum,

294
00:14:19,590 --> 00:14:24,120
nú er það O n deilt með 10,
eða O n deilt með 1.000.

295
00:14:24,120 --> 00:14:26,940
>> Og á meðan við vorum að tala
fræðilega um flókið

296
00:14:26,940 --> 00:14:30,061
við lítilsvirðingu fastar, í alvöru
Heimurinn þetta máli í raun,

297
00:14:30,061 --> 00:14:30,560
ekki satt?

298
00:14:30,560 --> 00:14:33,080
Við reyndar vilja taka
að þetta gerist

299
00:14:33,080 --> 00:14:36,610
að hlaupa 10 sinnum hraðar,
eða 1.000 sinnum hraðar,

300
00:14:36,610 --> 00:14:41,570
vegna þess að við erum að dreifa einn langan
keðja yfir 1.000 smærri keðjur.

301
00:14:41,570 --> 00:14:45,090
Og svo í hvert sinn sem við höfum til að leita
gegnum einn af þeim keðjur sem við getum

302
00:14:45,090 --> 00:14:50,290
hunsa 999 keðjur Við sama
um, og bara leita að einn.

303
00:14:50,290 --> 00:14:53,220
>> Sem er að meðaltali í
vera 1.000 sinnum styttri.

304
00:14:53,220 --> 00:14:56,460
Og svo erum við enn konar
tending að þessu meðaltali tilfelli

305
00:14:56,460 --> 00:15:01,610
af því að vera stöðugt tíma, en
aðeins vegna þess að við erum að fá meira

306
00:15:01,610 --> 00:15:03,730
deila með von um mikinn stöðugum þáttur.

307
00:15:03,730 --> 00:15:05,804
Við skulum sjá hvernig þetta gæti
í raun líta þó.

308
00:15:05,804 --> 00:15:08,720
Þannig að þetta var kjötkássa borð við höfðum
áður en við lýst kjötkássa borð sem

309
00:15:08,720 --> 00:15:10,270
var fær um að geyma 10 strengi.

310
00:15:10,270 --> 00:15:11,728
Við erum ekki að fara að gera það lengur.

311
00:15:11,728 --> 00:15:13,880
Við vitum nú þegar að
takmarkanir þeirrar aðferðar.

312
00:15:13,880 --> 00:15:20,170
Nú kjötkássa borð okkar er að fara að vera
fjölbreytta 10 hnúta, ábendingum

313
00:15:20,170 --> 00:15:22,120
að forstöðumenn tengd listum.

314
00:15:22,120 --> 00:15:23,830
>> Og núna er það null.

315
00:15:23,830 --> 00:15:26,170
Hver einn af þeim 10 ábendingum er null.

316
00:15:26,170 --> 00:15:29,870
Það er ekkert í okkar
kjötkássa borð núna.

317
00:15:29,870 --> 00:15:32,690
>> Nú skulum byrja að setja nokkrar
hlutum í þessum kjötkássa töflunni.

318
00:15:32,690 --> 00:15:35,440
Og við skulum sjá hvernig þessi aðferð er
fara til að njóta okkur svolítið.

319
00:15:35,440 --> 00:15:36,760
Skulum nú kjötkássa Joey.

320
00:15:36,760 --> 00:15:40,210
Við munum mun keyra band Joey gegnum
a kjötkássa virka og við aftur 6.

321
00:15:40,210 --> 00:15:41,200
Jæja hvað gerum við nú?

322
00:15:41,200 --> 00:15:44,090
>> Jæja nú að vinna með tengd listum,
við erum ekki að vinna með fylki.

323
00:15:44,090 --> 00:15:45,881
Og þegar við erum að vinna
með tengd listum við

324
00:15:45,881 --> 00:15:49,790
veit að við þurfum að byrja breytilega
úthlutun rúm og byggja keðjur.

325
00:15:49,790 --> 00:15:54,020
Það er tegund af how-- þeir eru algerlega
þættir byggja tengda listanum.

326
00:15:54,020 --> 00:15:57,670
Svo skulum virk
úthluta pláss fyrir Joey,

327
00:15:57,670 --> 00:16:00,390
og þá skulum bæta honum við keðju.

328
00:16:00,390 --> 00:16:03,170
>> Svo nú líta hvað við höfum gert.

329
00:16:03,170 --> 00:16:06,440
Þegar við kjötkássa Joey við fengum Tætifall 6.

330
00:16:06,440 --> 00:16:11,790
Nú bendillinn á array stað 6
bendir til höfuð tengda listanum,

331
00:16:11,790 --> 00:16:14,900
og núna er það eina
þáttur í tengda listanum.

332
00:16:14,900 --> 00:16:18,350
Og hnút í að
tengda listanum er Joey.

333
00:16:18,350 --> 00:16:22,300
>> Þannig að ef við þurfum að líta upp Joey
síðar, kjötkássa við bara Joey aftur,

334
00:16:22,300 --> 00:16:26,300
fáum við 6 aftur því okkar
kjötkássa virka er deterministic.

335
00:16:26,300 --> 00:16:30,400
Og þá erum við að byrja á höfði
af tengda listanum benti

336
00:16:30,400 --> 00:16:33,360
að því array stað
6, og við getum árétta

337
00:16:33,360 --> 00:16:35,650
yfir að reyna að finna Joey.

338
00:16:35,650 --> 00:16:37,780
Og ef við að byggja okkar
kjötkássa borð í raun,

339
00:16:37,780 --> 00:16:41,790
og kjötkássa virka okkar á áhrifaríkan hátt
að dreifa gögn vel,

340
00:16:41,790 --> 00:16:45,770
að meðaltali hver þeirra tengd
listum á öllum array stað

341
00:16:45,770 --> 00:16:50,110
verður 1/10 stærð ef við
bara haft það sem eitt gríðarstór

342
00:16:50,110 --> 00:16:51,650
tengda listanum með allt í það.

343
00:16:51,650 --> 00:16:55,670
>> Ef við dreifa að mikið tengd
Listinn yfir 10 tengd listum

344
00:16:55,670 --> 00:16:57,760
hver listi verður 1/10 stærð.

345
00:16:57,760 --> 00:17:01,432
Og þannig 10 sinnum hraðar
að leita í gegnum.

346
00:17:01,432 --> 00:17:02,390
Svo skulum gera þetta aftur.

347
00:17:02,390 --> 00:17:04,290
Skulum nú kjötkássa Ross.

348
00:17:04,290 --> 00:17:07,540
>> Og við skulum segja Ross, þegar við gerum það
kjötkássa kóða við komum til baka er 2.

349
00:17:07,540 --> 00:17:10,630
Jæja nú erum við að úthluta virk a
Ný hnút, setja við Ross í hnút,

350
00:17:10,630 --> 00:17:14,900
og við segjum nú array staðsetningu
2, í stað þess að benda á núll,

351
00:17:14,900 --> 00:17:18,579
bendir til höfuð tengdur
Listinn sem aðeins hnúturinn Ross.

352
00:17:18,579 --> 00:17:22,660
Og við getum gert þetta einu sinni, vér
getur kjötkássa Rakel og fá Tætifall 4.

353
00:17:22,660 --> 00:17:25,490
malloc nýja hnút, setja Rakel í
hnúturinn, og segja array stað

354
00:17:25,490 --> 00:17:27,839
4 nú bendir til höfuðs
af tengda listanum sem

355
00:17:27,839 --> 00:17:31,420
aðeins þáttur gerist að vera Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK en hvað gerist ef
við höfum árekstur?

357
00:17:33,470 --> 00:17:38,560
Við skulum sjá hvernig við tökum árekstra
nota sérstaka læsa aðferð.

358
00:17:38,560 --> 00:17:39,800
Skulum kjötkássa Phoebe.

359
00:17:39,800 --> 00:17:41,094
Við fáum Tætifall 6.

360
00:17:41,094 --> 00:17:44,010
Í fyrra dæminu okkar við vorum bara
geyma strengi í array.

361
00:17:44,010 --> 00:17:45,980
Þetta var vandamál.

362
00:17:45,980 --> 00:17:48,444
>> Við viljum ekki að clobber
Joey, og við höfum nú þegar

363
00:17:48,444 --> 00:17:51,110
séð að við getum fengið smá Þyrping
vandamál ef við reynum og skref

364
00:17:51,110 --> 00:17:52,202
gegnum og rannsaka.

365
00:17:52,202 --> 00:17:54,660
En hvað ef við bara svona
meðhöndla þetta á sama hátt, ekki satt?

366
00:17:54,660 --> 00:17:57,440
Það er bara eins og að bæta stak
höfuð tengda listanum.

367
00:17:57,440 --> 00:18:00,220
Við skulum bara malloc pláss fyrir Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Við munum segja næst bendi Phoebe stig
að gamla höfuð tengda listanum,

369
00:18:04,764 --> 00:18:07,180
og þá 6 bara bendir til
nýr yfirmaður tengda listanum.

370
00:18:07,180 --> 00:18:10,150
Og nú líta, að við höfum breytt Phoebe í.

371
00:18:10,150 --> 00:18:14,210
Við getum nú geymt tvö
þætti með Tætifall 6,

372
00:18:14,210 --> 00:18:17,170
og við höfum ekki nein vandamál.

373
00:18:17,170 --> 00:18:20,147
>> Það er ansi mikið allt
það er að chaining.

374
00:18:20,147 --> 00:18:21,980
Og chaining er ákveðið
aðferð sem er

375
00:18:21,980 --> 00:18:27,390
fara til vera árangursríkur fyrir þig ef
þú ert að geyma gögn í kjötkássa töflunni.

376
00:18:27,390 --> 00:18:30,890
En þessi blanda af
fylki og tengd skrár

377
00:18:30,890 --> 00:18:36,080
saman til að mynda kjötkássa töflunni mjög
bætir verulega getu þína

378
00:18:36,080 --> 00:18:40,550
að geyma mikið magn af gögnum, og
mjög fljótt og vel leit

379
00:18:40,550 --> 00:18:41,630
í gegnum þessi gögn.

380
00:18:41,630 --> 00:18:44,150
>> Það er enn eitt
gögn uppbygging þarna úti

381
00:18:44,150 --> 00:18:48,700
sem gæti jafnvel verið hluti
betri hvað varðar tryggja

382
00:18:48,700 --> 00:18:51,920
að okkar innsetning, eyðingu, og
líta upp tímar eru jafnvel hraðar.

383
00:18:51,920 --> 00:18:55,630
Og við munum sjá að í vídeó á reynir.

384
00:18:55,630 --> 00:18:58,930
Ég er Doug Lloyd, þetta er CS50.

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