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

2
00:00:00,500 --> 00:00:01,900
[Zenelejátszási]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Mostanra
Sokat tud tömbök,

5
00:00:09,150 --> 00:00:11,610
és tudod, hogy sokat láncolt listák.

6
00:00:11,610 --> 00:00:13,650
És mi már megvitatására
érvek és ellenérvek, most már

7
00:00:13,650 --> 00:00:16,620
megvitatták, hogy a kapcsolt listák
kap nagyobb és kisebb,

8
00:00:16,620 --> 00:00:18,630
de ebben az esetben több méretben.

9
00:00:18,630 --> 00:00:22,359
A tömbök sokkal egyszerűbb a
használja, de ők korlátozó annyi

10
00:00:22,359 --> 00:00:24,900
valamint át kell állítani a méretét
A tömb a legelején

11
00:00:24,900 --> 00:00:26,910
majd ragadtunk vele.

12
00:00:26,910 --> 00:00:30,470
>> De ez, most már elég sok
kimerítette minden kedves témák

13
00:00:30,470 --> 00:00:33,040
mintegy kapcsolódó listák és tömbök.

14
00:00:33,040 --> 00:00:34,950
Vagy van még?

15
00:00:34,950 --> 00:00:37,720
Talán tehetünk valamit
még több kreatív.

16
00:00:37,720 --> 00:00:40,950
És ez a fajta kölcsönöz
Az ötlet egy hash tábla.

17
00:00:40,950 --> 00:00:46,680
>> Tehát egy hash tábla fogunk próbálni
egyesítik egy tömb, láncolt lista.

18
00:00:46,680 --> 00:00:49,520
Fogunk figyelembe előnyeit
a tömb, mint a véletlen hozzáférésű,

19
00:00:49,520 --> 00:00:53,510
hogy képes csak megy a tömb
4 elem vagy tömb elemek 8

20
00:00:53,510 --> 00:00:55,560
anélkül, hogy ismételget szerte.

21
00:00:55,560 --> 00:00:57,260
Ez elég gyors, nem igaz?

22
00:00:57,260 --> 00:01:00,714
>> De azt is szeretnénk, hogy adatainkat
struktúra képes növekedni, és összezsugorodik.

23
00:01:00,714 --> 00:01:02,630
Nem kell, mi nem
akarjuk korlátozni kell.

24
00:01:02,630 --> 00:01:04,588
És azt akarjuk, hogy képes
hozzáadása és eltávolítása a dolgokat

25
00:01:04,588 --> 00:01:08,430
nagyon könnyen, amelyek, ha emlékeznek rá,
nagyon komplex egy tömb.

26
00:01:08,430 --> 00:01:11,650
És nevezhetjük ezt
új dolog egy hash tábla.

27
00:01:11,650 --> 00:01:15,190
>> És ha végre rendesen,
mi fajta figyelembe

28
00:01:15,190 --> 00:01:18,150
előnyeit mindkét adat
struktúrák már láttad,

29
00:01:18,150 --> 00:01:19,880
tömbök és kapcsolt listák.

30
00:01:19,880 --> 00:01:23,070
Behelyezés lehet kezdeni
Hajlamos theta 1.

31
00:01:23,070 --> 00:01:26,207
Theta még nem igazán vitatták,
de théta csak átlagos esetre,

32
00:01:26,207 --> 00:01:27,540
mi valóban meg fog történni.

33
00:01:27,540 --> 00:01:29,680
Te nem mindig lesz
a legrosszabb forgatókönyv esetén,

34
00:01:29,680 --> 00:01:32,555
és te nem mindig megy, hogy
A legjobb esetben, tehát mi

35
00:01:32,555 --> 00:01:33,900
Az átlagos forgatókönyv?

36
00:01:33,900 --> 00:01:36,500
>> Nos átlagosan beillesztés
egy hash tábla

37
00:01:36,500 --> 00:01:39,370
lehet kezdeni, hogy közel állandó időt.

38
00:01:39,370 --> 00:01:41,570
És törlés kaphat
közel állandó időt.

39
00:01:41,570 --> 00:01:44,440
És keresési kaphat
közel állandó időt.

40
00:01:44,440 --> 00:01:48,600
That's-- nincs adat
szerkezete még, hogy meg tudom csinálni,

41
00:01:48,600 --> 00:01:51,180
és így ez már hangzik
mint egy szép nagy dolog.

42
00:01:51,180 --> 00:01:57,010
Már tényleg enyhíteni a
hátrányait az egyes saját.

43
00:01:57,010 --> 00:01:59,160
>> Ahhoz, hogy ez a teljesítmény
frissíteni mégis, akkor

44
00:01:59,160 --> 00:02:03,580
kell gondolnunk, hogyan tudjuk felvenni
adatok a szerkezet.

45
00:02:03,580 --> 00:02:07,380
Különösen szeretnénk a
adatok is, hogy elmondja nekünk

46
00:02:07,380 --> 00:02:09,725
ahol kell menni a szerkezetben.

47
00:02:09,725 --> 00:02:12,850
És ha majd kell, hogy ha ez a
a szerkezet, ha meg kell találni azt,

48
00:02:12,850 --> 00:02:16,610
azt akarjuk, hogy nézd meg az adatokat
újra és képes hatékonyan,

49
00:02:16,610 --> 00:02:18,910
adatok felhasználásával, véletlenszerűen hozzáférni.

50
00:02:18,910 --> 00:02:20,700
Ránézésre a
adatokat kellett volna

51
00:02:20,700 --> 00:02:25,890
egy ötlet, hogy pontosan hol vagyunk
fogja megtalálni a hash táblában.

52
00:02:25,890 --> 00:02:28,770
>> Most a hátránya a hash
asztalhoz, hogy ők nagyon

53
00:02:28,770 --> 00:02:31,770
Elég rossz a megrendelésnél vagy válogatás adatokat.

54
00:02:31,770 --> 00:02:34,970
És valóban, ha elkezd
használni őket rendelni, vagy egyfajta

55
00:02:34,970 --> 00:02:37,990
adatok elveszíti az összes
előnyök korábban

56
00:02:37,990 --> 00:02:40,710
Volt szempontjából behelyezés és törlése.

57
00:02:40,710 --> 00:02:44,060
Az idő lesz közelebb
téta N, és mi már alapvetően

58
00:02:44,060 --> 00:02:45,530
visszafejlődött egy láncolt lista.

59
00:02:45,530 --> 00:02:48,850
És így mi csak azt akarjuk használni hash
asztalok ha nem érdekel

60
00:02:48,850 --> 00:02:51,490
hogy az adatok megfelelően rendezve.

61
00:02:51,490 --> 00:02:54,290
A környezet, amelyben
akkor használja őket CS50

62
00:02:54,290 --> 00:02:58,900
akkor valószínűleg nem érdekel
hogy az adatok sorrendje.

63
00:02:58,900 --> 00:03:03,170
>> Tehát egy hash tábla kombinációja
két különálló darab

64
00:03:03,170 --> 00:03:04,980
amellyel vagyunk tisztában.

65
00:03:04,980 --> 00:03:07,930
Az első egy olyan funkció, amely
szoktunk hívni a hash függvény.

66
00:03:07,930 --> 00:03:11,760
És, hogy hash függvény fog
visszatérni néhány nem-negatív egész, ami

67
00:03:11,760 --> 00:03:14,870
szoktunk hívni a hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
A második darab egy tömb, amely
tárolására képes adatok a típus mi

69
00:03:20,230 --> 00:03:22,190
kívánja helyezni adatstruktúrájába.

70
00:03:22,190 --> 00:03:24,310
Majd tartja magát a
láncolt lista elem most

71
00:03:24,310 --> 00:03:27,810
és csak kezdeni az alapokat egy
hash tábla, hogy a fejed körül,

72
00:03:27,810 --> 00:03:30,210
aztán majd talán robbantani
az agyad egy kicsit, amikor

73
00:03:30,210 --> 00:03:32,920
egyesítik tömbök és linklisták együtt.

74
00:03:32,920 --> 00:03:35,590
>> Az alapötlet bár
van veszünk néhány adatot.

75
00:03:35,590 --> 00:03:37,860
Futunk, hogy az adatok a
A hash függvény.

76
00:03:37,860 --> 00:03:41,980
És így az adatfeldolgozás
és kiköpi több, OK?

77
00:03:41,980 --> 00:03:44,890
És akkor ez a szám
mi csak tárolja az adatokat

78
00:03:44,890 --> 00:03:48,930
szeretnénk tárolni a
tömb az adott helyen.

79
00:03:48,930 --> 00:03:53,990
Így például már talán
ez a hash tábla a szálakat.

80
00:03:53,990 --> 00:03:57,350
Van rajta 10 elemek is, így
Mi fér 10 húrok benne.

81
00:03:57,350 --> 00:03:59,320
>> Tegyük fel, hogy szeretnénk a hash John.

82
00:03:59,320 --> 00:04:02,979
Szóval John mivel az adatok azt szeretné szúrni
ebbe a hash tábla valahol.

83
00:04:02,979 --> 00:04:03,770
Hol rakjuk?

84
00:04:03,770 --> 00:04:05,728
Hát általában egy
tömb eddig mi valószínűleg

85
00:04:05,728 --> 00:04:07,610
azt tedd tömb 0 helyen.

86
00:04:07,610 --> 00:04:09,960
De most itt van ez az új hash függvény.

87
00:04:09,960 --> 00:04:13,180
>> És mondjuk, hogy mi fut John
ezen keresztül hash függvény

88
00:04:13,180 --> 00:04:15,417
és ez kiköpi 4.

89
00:04:15,417 --> 00:04:17,500
Hát ez az, ahol mi vagyunk
szeretne majd fel John.

90
00:04:17,500 --> 00:04:22,050
Azt szeretnénk, hogy John a tömb helyét
4, mert ha hash John again--

91
00:04:22,050 --> 00:04:23,810
mondjuk később
kíván keresni és látni

92
00:04:23,810 --> 00:04:26,960
ha John létezik ezen a hash
table-- minden meg kell tennie

93
00:04:26,960 --> 00:04:30,310
fut át ​​az azonos hash
funkciót, hogy a 4-es számú ki,

94
00:04:30,310 --> 00:04:33,929
és képes megtalálni John
Azonnal adataink szerkezete.

95
00:04:33,929 --> 00:04:34,720
Ez elég jó.

96
00:04:34,720 --> 00:04:36,928
>> Mondjuk most ezt
Még egyszer, a hash-Paul.

97
00:04:36,928 --> 00:04:39,446
Szeretnénk felvenni Pál
ebbe hash tábla.

98
00:04:39,446 --> 00:04:42,070
Tegyük fel, hogy ebben az időben futunk
Paul át a hash függvény,

99
00:04:42,070 --> 00:04:44,600
a hashcode generált 6.

100
00:04:44,600 --> 00:04:47,340
Hát most tehetünk bele Paul
A tömb helyen 6.

101
00:04:47,340 --> 00:04:50,040
És ha kell keresni, hogy
Pál ebben a hash tábla,

102
00:04:50,040 --> 00:04:53,900
minden meg kell tennie, hogy fut Pál
a hash függvény újra

103
00:04:53,900 --> 00:04:55,830
és mi lesz, hogy 6 ki újra.

104
00:04:55,830 --> 00:04:57,590
>> És akkor csak nézd
A tömb helyen 6.

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

106
00:04:58,910 --> 00:05:00,160
Ha igen, ő a hash táblában.

107
00:05:00,160 --> 00:05:01,875
Pál nem volt ott?

108
00:05:01,875 --> 00:05:03,000
Ő nem a hash táblában.

109
00:05:03,000 --> 00:05:05,720
Ez elég egyértelmű.

110
00:05:05,720 --> 00:05:07,770
>> Most hogyan határozná meg a hash függvény?

111
00:05:07,770 --> 00:05:11,460
Hát már tényleg nincs határa a
számú lehetséges hash függvények.

112
00:05:11,460 --> 00:05:14,350
Valójában van néhány igazán,
Nagyon jók az interneten.

113
00:05:14,350 --> 00:05:17,560
Van néhány igazán,
Nagyon rosszak az interneten.

114
00:05:17,560 --> 00:05:21,080
Ez is nagyon egyszerű
hogy írjon egy rossz.

115
00:05:21,080 --> 00:05:23,760
>> Szóval mit tesz egy jó
hash függvény, igaz?

116
00:05:23,760 --> 00:05:27,280
Hát jó hash függvényt
csak a továbbított adatok hashed,

117
00:05:27,280 --> 00:05:29,420
és az összes adatot, hogy hashed.

118
00:05:29,420 --> 00:05:32,500
Szóval nem akarjuk használni bármit
mi nem bele semmit

119
00:05:32,500 --> 00:05:35,560
mást eltérő az adatokat.

120
00:05:35,560 --> 00:05:37,080
És szeretnénk használni az összes adatot.

121
00:05:37,080 --> 00:05:39,830
Nem akarjuk, ha csak egy darab
azt, hogy szeretnénk használni az egészet.

122
00:05:39,830 --> 00:05:41,710
Egy hash függvényt
szintén determinisztikus.

123
00:05:41,710 --> 00:05:42,550
Az mit jelent?

124
00:05:42,550 --> 00:05:46,200
Nos ez azt jelenti, hogy minden alkalommal
át pontosan ugyanazt az adatot

125
00:05:46,200 --> 00:05:50,040
a hash függvény mindig
kap ugyanaz hashcode ki.

126
00:05:50,040 --> 00:05:52,870
Ha elmegyek Johnt a
hash függvény kikerülök 4.

127
00:05:52,870 --> 00:05:56,110
Azt kell tudni csinálni, hogy 10.000
idők és én mindig kap 4.

128
00:05:56,110 --> 00:06:00,810
Tehát nem véletlen számokat hatékonyan
bevonhatók a hasító tables--

129
00:06:00,810 --> 00:06:02,750
a hasító függvények.

130
00:06:02,750 --> 00:06:05,750
>> A hash funkció azt is
egyenletesen osszuk adatok.

131
00:06:05,750 --> 00:06:09,700
Ha minden alkalommal futtatja az adatokat a
hash függvény megkapja az hashcode 0,

132
00:06:09,700 --> 00:06:11,200
ez talán nem olyan nagy, igaz?

133
00:06:11,200 --> 00:06:14,600
Talán szeretnénk nagy
egy sor hash kódok.

134
00:06:14,600 --> 00:06:17,190
Szintén dolgokat is terjed
ki az egész táblázatot.

135
00:06:17,190 --> 00:06:23,210
És azt is, hogy jó lenne, ha tényleg
hasonló, mint John és Jonathan,

136
00:06:23,210 --> 00:06:26,320
Talán arra terjedt ki, hogy mérjük
különböző helyeken a hash táblában.

137
00:06:26,320 --> 00:06:28,750
Ez lenne a szép előnyt.

138
00:06:28,750 --> 00:06:31,250
>> Íme egy példa egy hash függvény.

139
00:06:31,250 --> 00:06:33,150
Írtam ezt fel korábban.

140
00:06:33,150 --> 00:06:35,047
Ez nem egy különösen
jó hash függvény

141
00:06:35,047 --> 00:06:37,380
okok miatt nem igazán
viselik megy most.

142
00:06:37,380 --> 00:06:41,040
De látod, mi folyik itt?

143
00:06:41,040 --> 00:06:44,420
Úgy tűnik, mintha mi nyilvánító változó
nevezett összeg és a beállítás, 0-val egyenlő.

144
00:06:44,420 --> 00:06:50,010
És akkor nyilván én csinálok valamit
mindaddig, amíg strstr [j] nem egyenlő

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

146
00:06:52,490 --> 00:06:54,870
Mit csinálok itt?

147
00:06:54,870 --> 00:06:57,440
>> Ez alapvetően csak egy újabb
végrehajtásán [? strl?]

148
00:06:57,440 --> 00:06:59,773
és felderítésére, ha már
végére ért a húr.

149
00:06:59,773 --> 00:07:02,480
Szóval nem kell ténylegesen
kiszámítja a hossza a húr,

150
00:07:02,480 --> 00:07:05,640
Én csak használ, amikor elütöttem a
backslash 0 karaktert tudom

151
00:07:05,640 --> 00:07:07,185
Én elérte a végén a húr.

152
00:07:07,185 --> 00:07:09,560
És akkor fogok tartani
iterációjával keresztül, hogy a húr,

153
00:07:09,560 --> 00:07:15,310
hozzátéve strstr [j] összefoglalni, majd a
A nap végén fog visszatérni összeget mod

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

155
00:07:16,200 --> 00:07:18,700
>> Alapvetően mindez hash
funkciót tesz, hogy összeadjuk

156
00:07:18,700 --> 00:07:23,450
az összes ASCII értékeinek
én húr, és akkor itt

157
00:07:23,450 --> 00:07:26,390
visszatérő néhány hashcode
Megvan a módosított által HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Valószínűleg ez a méret
Az én tömb, ugye?

159
00:07:29,790 --> 00:07:33,160
Nem akarom, hogy egyre hash
kódokat, ha a tömb mérete 10,

160
00:07:33,160 --> 00:07:35,712
Nem akarom, hogy egyre
ki hash kódok 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, nem tudom tenni a dolgokat
ezeken a helyeken a tömb,

162
00:07:38,690 --> 00:07:39,790
hogy jogellenes lenne.

163
00:07:39,790 --> 00:07:42,130
Én szenvednek szegmens hiba.

164
00:07:42,130 --> 00:07:45,230
>> Most itt van egy újabb gyors félre.

165
00:07:45,230 --> 00:07:48,470
Általában akkor valószínűleg nem fog
szeretné írni a saját hash függvények.

166
00:07:48,470 --> 00:07:50,997
Ez valójában egy kicsit
művészet, nem tudomány.

167
00:07:50,997 --> 00:07:52,580
És van egy csomó, hogy megy be őket.

168
00:07:52,580 --> 00:07:55,288
Az internet, mint mondtam, tele van
Az igazán jó hash függvények,

169
00:07:55,288 --> 00:07:58,470
és akkor használja az internetet
találni hash függvények, mert nagyon

170
00:07:58,470 --> 00:08:03,230
csak ilyen szükségtelen
időpocsékolás, hogy saját.

171
00:08:03,230 --> 00:08:05,490
>> Írhatsz egyszerű is
tesztelési célokra.

172
00:08:05,490 --> 00:08:08,323
De ha valóban lesz
kezdeni hashing adatok és tárolás

173
00:08:08,323 --> 00:08:10,780
hasító táblába te
Valószínűleg szeretne majd

174
00:08:10,780 --> 00:08:14,580
használni néhány funkciót, hogy keletkezett
Önnek, hogy létezik az interneten.

175
00:08:14,580 --> 00:08:17,240
Ha csak legyen biztos
hogy idézni a forrást.

176
00:08:17,240 --> 00:08:21,740
Nincs ok arra, hogy
plagizál itt semmit.

177
00:08:21,740 --> 00:08:25,370
>> A számítástechnika közösség
egyértelműen növekszik, és tényleg értékek

178
00:08:25,370 --> 00:08:28,796
nyílt forráskódú, és ez nagyon fontos
hogy idézni a forrást, hogy az emberek

179
00:08:28,796 --> 00:08:30,670
kaphat szerzőjének
a munkát, amit ők

180
00:08:30,670 --> 00:08:32,312
Ennek az a közösség javára.

181
00:08:32,312 --> 00:08:34,020
Így mindig sure--
és nem csak a hash

182
00:08:34,020 --> 00:08:37,270
funkciók, de általában ha
Használja kódot külső forrásból származó,

183
00:08:37,270 --> 00:08:38,299
Mindig idézni a forrást.

184
00:08:38,299 --> 00:08:43,500
Hitelt ad az a személy, aki nem
a munka egy részét, így nem kell.

185
00:08:43,500 --> 00:08:46,720
>> OK úgyhogy újra ezt
hash tábla egy pillanatra.

186
00:08:46,720 --> 00:08:48,780
Ez az, ahol hagytuk
off miután behelyezett

187
00:08:48,780 --> 00:08:53,300
János és Pál ebbe a hash tábla.

188
00:08:53,300 --> 00:08:55,180
Látsz egy probléma van?

189
00:08:55,180 --> 00:08:58,410
Lehet, hogy két.

190
00:08:58,410 --> 00:09:02,240
De különösen igaz
lásd erre a lehetséges problémára?

191
00:09:02,240 --> 00:09:06,770
>> Mit tegyek, ha hash Ringo, és ez
Kiderül, hogy a feldolgozás után

192
00:09:06,770 --> 00:09:14,000
hogy az adatokat a hash függvény
Ringo is előállítottak a hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Már van adatok
hashcode-- tömb helyen 6.

194
00:09:16,810 --> 00:09:22,000
Szóval ez valószínűleg lesz egy kicsit
A probléma most nekem, ugye?

195
00:09:22,000 --> 00:09:23,060
>> Hívjuk ezt az ütközést.

196
00:09:23,060 --> 00:09:26,460
És az ütközés fordul elő, amikor a két
adattartalommal végigmenni ugyanazon a hash

197
00:09:26,460 --> 00:09:29,200
funkciót, így azonos hashcode.

198
00:09:29,200 --> 00:09:32,850
Feltehetően még mindig szeretné, hogy a két
adattartalommal a hash tábla,

199
00:09:32,850 --> 00:09:36,330
különben nem fut Ringo
önkényesen át a hash függvény.

200
00:09:36,330 --> 00:09:40,870
Azt szeretnénk, hogy feltehetően
Ringo be a tömbben.

201
00:09:40,870 --> 00:09:46,070
>> Hogy csináljuk, hogy mégis, ha
és Paul mindkét hozam hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Mi nem akarja felülírni Pál,
akarunk Pál is ott lesz.

203
00:09:49,520 --> 00:09:52,790
Tehát meg kell találni a módját, hogy
elemek a hash tábla

204
00:09:52,790 --> 00:09:56,550
még ma is őrzi a gyors
behelyezése és gyors pillantást fel.

205
00:09:56,550 --> 00:10:01,350
És az egyik módja, hogy foglalkozzon vele, hogy
tenni valamit az úgynevezett lineáris szondázás.

206
00:10:01,350 --> 00:10:04,170
>> Ezzel a módszerrel, ha van egy
ütközés, nos, mit csináljunk?

207
00:10:04,170 --> 00:10:08,580
Hát nem tudunk vele tömb helyét
6, vagy bármi hashcode keletkezett,

208
00:10:08,580 --> 00:10:10,820
tegyük rá a hashcode plusz 1.

209
00:10:10,820 --> 00:10:13,670
És ha ez a teljes nézzük
tedd rá hashcode plusz 2.

210
00:10:13,670 --> 00:10:17,420
Az előnye ennek a lénynek, ha ő
Nem pontosan hol azt gondoljuk, ő,

211
00:10:17,420 --> 00:10:20,850
és meg kell kezdeni a keresést,
talán nem kell túl messzire menni.

212
00:10:20,850 --> 00:10:23,900
Talán nem kell keresni
minden n eleme a hash tábla.

213
00:10:23,900 --> 00:10:25,790
Talán meg kell keresni
egy pár közülük.

214
00:10:25,790 --> 00:10:30,680
>> És ezért vagyunk még hajló
hogy egy átlagos esetben, hogy közel 1 vs

215
00:10:30,680 --> 00:10:34,280
közel n, így lehet, hogy működni fog.

216
00:10:34,280 --> 00:10:38,010
Nézzük, hogy ez hogyan
Lehet, dolgozzanak ki a valóságban.

217
00:10:38,010 --> 00:10:41,460
És lássuk, talán tudunk észlelni
Az előforduló probléma, hogy itt.

218
00:10:41,460 --> 00:10:42,540
>> Mondjuk hash Bart.

219
00:10:42,540 --> 00:10:45,581
Tehát most fogunk futni egy sor új
A húrok át a hash függvény,

220
00:10:45,581 --> 00:10:48,460
és mi fut Bart át a hash
funkciót, kapunk hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Veszünk egy pillantást, látjuk a 6.
üres, így tudjuk Bart van.

222
00:10:52,100 --> 00:10:55,410
>> Most hash Lisa és hogy
is generál hashcode 6.

223
00:10:55,410 --> 00:10:58,330
Hát most, hogy ezt a
lineáris szondázás módszerrel kezdjük 6,

224
00:10:58,330 --> 00:10:59,330
azt látjuk, hogy a 6. megtelt.

225
00:10:59,330 --> 00:11:00,990
Nem tudunk Lisa 6.

226
00:11:00,990 --> 00:11:02,090
Szóval, ha nem megyünk?

227
00:11:02,090 --> 00:11:03,280
Menjünk 7.

228
00:11:03,280 --> 00:11:04,610
7-es üres, hogy működik.

229
00:11:04,610 --> 00:11:06,510
Tehát mondjuk Lisa ott.

230
00:11:06,510 --> 00:11:10,200
>> Most hash Homer és kapunk 7.

231
00:11:10,200 --> 00:11:13,380
OK jól tudjuk, hogy a 7-es teljes
most, így nem tudunk tenni Homer ott.

232
00:11:13,380 --> 00:11:14,850
Szóval menjünk 8.

233
00:11:14,850 --> 00:11:15,664
8 rendelkezésre?

234
00:11:15,664 --> 00:11:18,330
Ja, és a 8-as közel 7, így ha
meg kell keresni kezdi vagyunk

235
00:11:18,330 --> 00:11:20,020
nem megy, hogy túl messzire megy.

236
00:11:20,020 --> 00:11:22,860
És így tegyük Homer 8.

237
00:11:22,860 --> 00:11:25,151
>> Most hash Maggie és
vissza 3, hála az égnek

238
00:11:25,151 --> 00:11:26,650
képesek vagyunk csak fel Maggie ott.

239
00:11:26,650 --> 00:11:29,070
Nem kell, hogy nem minden
egyfajta tapintási erre.

240
00:11:29,070 --> 00:11:32,000
Most hash Marge, és
Marge is visszaadja 6.

241
00:11:32,000 --> 00:11:39,560
>> Nos 6 megtelt, 7 tele van, 8 tele van,
9, rendben hála Istennek, 9 üres.

242
00:11:39,560 --> 00:11:41,600
Én nem tud Marge 9.

243
00:11:41,600 --> 00:11:45,280
Már látjuk, hogy kezdünk
hogy ez a probléma, ahol most vagyunk

244
00:11:45,280 --> 00:11:48,780
kezd nyúlik dolgokat természetbeni
A távol a hash kódok.

245
00:11:48,780 --> 00:11:52,960
És, hogy theta 1, hogy az átlagos
esetében pedig állandó idő,

246
00:11:52,960 --> 00:11:56,560
már kezd egy kicsit more--
kiindulva, hogy inkább egy kicsit

247
00:11:56,560 --> 00:11:58,050
felé theta n.

248
00:11:58,050 --> 00:12:01,270
Elkezdjük elveszíteni
Használja ki hash táblák.

249
00:12:01,270 --> 00:12:03,902
>> Ez a probléma, hogy most láttam
egy úgynevezett klaszterek kialakulását.

250
00:12:03,902 --> 00:12:06,360
És ami igazán rosszul
csoportosítás az, hogy ha egyszer már

251
00:12:06,360 --> 00:12:09,606
Van két elemeket, amelyek egymás
másikra ez teszi még inkább,

252
00:12:09,606 --> 00:12:11,480
Van dupla
esélye, hogy fogsz

253
00:12:11,480 --> 00:12:13,516
hogy még egy ütközés
azzal a klaszter,

254
00:12:13,516 --> 00:12:14,890
és a klaszter fog nőni az egyik.

255
00:12:14,890 --> 00:12:19,640
És akkor folyamatosan növekvő és egyre
Ön valószínűsége annak ütközés.

256
00:12:19,640 --> 00:12:24,470
És végül ez ugyanolyan rossz
ne válogatás az adatok egyáltalán.

257
00:12:24,470 --> 00:12:27,590
>> A másik probléma mégis az, hogy mi
Mégis, és eddig a pontig,

258
00:12:27,590 --> 00:12:30,336
most voltunk valami
megértése, hogy mi a hash tábla,

259
00:12:30,336 --> 00:12:31,960
még mindig csak van hely a 10 szálakat.

260
00:12:31,960 --> 00:12:37,030
Ha azt akarjuk, hogy továbbra is a hash
polgárai Springfield,

261
00:12:37,030 --> 00:12:38,790
csak akkor tudjuk, hogy 10 oket oda.

262
00:12:38,790 --> 00:12:42,619
És ha megpróbáljuk, és adjunk hozzá egy 11. vagy 12.,
nincs olyan hely, hogy őket.

263
00:12:42,619 --> 00:12:45,660
Így egyszerűen forog körbe-
körökben próbál találni egy üres helyre,

264
00:12:45,660 --> 00:12:49,000
és mi talán elakad
végtelen ciklusba.

265
00:12:49,000 --> 00:12:51,810
>> Tehát ez a fajta kölcsönöz az ötlet
Az úgynevezett láncolt.

266
00:12:51,810 --> 00:12:55,790
És ez az, hogy hová megyünk, hogy
láncolt listák vissza a képet.

267
00:12:55,790 --> 00:13:01,300
Mi van, ha tárolása helyett csak
az adatok is a tömbben,

268
00:13:01,300 --> 00:13:04,471
minden eleme a tömb lehetett
tartsa több darab adatokat?

269
00:13:04,471 --> 00:13:05,970
Nos, hogy nincs értelme, nem igaz?

270
00:13:05,970 --> 00:13:09,280
Tudjuk, hogy egy tömb csak
hold-- minden eleme egy tömb

271
00:13:09,280 --> 00:13:12,930
csak tartani egy darabban
Az adatok ugyanilyen típusra.

272
00:13:12,930 --> 00:13:16,750
>> De mi van, ha ugyanilyen típusra
egy láncolt lista, ugye?

273
00:13:16,750 --> 00:13:19,830
Szóval mi van, ha minden
elem a tömb volt

274
00:13:19,830 --> 00:13:22,790
egy mutatót a fejét egy láncolt lista?

275
00:13:22,790 --> 00:13:24,680
És akkor tudnánk építeni
azok láncolt listák

276
00:13:24,680 --> 00:13:27,120
és növekedni őket önkényesen,
mert láncolt listák lehetővé teszik

277
00:13:27,120 --> 00:13:32,090
számunkra, hogy nő, és összezsugorodik sokkal több
rugalmasan, mint egy tömb nem.

278
00:13:32,090 --> 00:13:34,210
Szóval mi van, ha most használni,
Kihasználva ezt, ugye?

279
00:13:34,210 --> 00:13:37,760
Mi növekedni kezdenek ezek a láncok
ezek közül tömb helyeken.

280
00:13:37,760 --> 00:13:40,740
>> Most elfér egy végtelen
adatok mennyisége, vagy nem végtelen,

281
00:13:40,740 --> 00:13:44,170
tetszőleges mennyiségű
adatok, a mi hash tábla

282
00:13:44,170 --> 00:13:47,760
anélkül, hogy valaha fut be
A probléma az ütközés.

283
00:13:47,760 --> 00:13:50,740
Már azt is megszűnt
csoportosítás ezt.

284
00:13:50,740 --> 00:13:54,380
És jól tudjuk, hogy ha betesszük
egy láncolt lista, ha visszaemlékeztek

285
00:13:54,380 --> 00:13:57,779
a mi videót láncolt listák, önmagukban
kapcsolt listák és kétszeresen láncolt listák,

286
00:13:57,779 --> 00:13:59,070
ez egy folyamatos működést.

287
00:13:59,070 --> 00:14:00,710
Mi csak hozzá a frontra.

288
00:14:00,710 --> 00:14:04,400
>> És felnéz, jól tudjuk,
hogy felnéz egy láncolt lista

289
00:14:04,400 --> 00:14:05,785
lehet probléma, ugye?

290
00:14:05,785 --> 00:14:07,910
Meg kell keresni
ez az elejétől a végéig.

291
00:14:07,910 --> 00:14:10,460
Nincs véletlen
hozzáférést egy láncolt lista.

292
00:14:10,460 --> 00:14:15,610
De ha ahelyett, hogy mindegyik kapcsolódik
lista, ahol egy keresési lenne O n,

293
00:14:15,610 --> 00:14:19,590
Most már 10 láncolt listák,
vagy 1000 láncolt listák,

294
00:14:19,590 --> 00:14:24,120
most ez O n osztva 10,
vagy O n osztva 1000.

295
00:14:24,120 --> 00:14:26,940
>> És miközben beszélgettünk
elméletileg mintegy összetettsége

296
00:14:26,940 --> 00:14:30,061
eltekintünk állandók, az igazi
világban ezek a dolgok valóban számít,

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

298
00:14:30,560 --> 00:14:33,080
Igazából észre fogja venni
hogy ez történik

299
00:14:33,080 --> 00:14:36,610
futni 10-szer gyorsabb,
vagy 1000-szer gyorsabb,

300
00:14:36,610 --> 00:14:41,570
mert mi terjesztése egy hosszú
lánc-szerte 1000 kisebb láncok.

301
00:14:41,570 --> 00:14:45,090
És így minden alkalommal meg kell keresni
révén az egyik ilyen láncok tudjuk

302
00:14:45,090 --> 00:14:50,290
figyelmen kívül hagyják a 999 lánc nem érdekel
szól, és csak a keresési hogy az egyik.

303
00:14:50,290 --> 00:14:53,220
>> Ami átlagosan a
legyen 1000-szer rövidebb.

304
00:14:53,220 --> 00:14:56,460
És így még mindig van valami
hajló ez az átlag esetben

305
00:14:56,460 --> 00:15:01,610
lét állandó idő, de
Csak azért, mert Kihasználjuk

306
00:15:01,610 --> 00:15:03,730
elosztjuk néhány hatalmas állandó tényező.

307
00:15:03,730 --> 00:15:05,804
Lássuk, hogyan lehet ezt
valójában meg mégis.

308
00:15:05,804 --> 00:15:08,720
Szóval ez volt a hash tábla volt
mielőtt nyilvánították hash tábla

309
00:15:08,720 --> 00:15:10,270
volt képes tárolni 10 szálakat.

310
00:15:10,270 --> 00:15:11,728
Nem fogunk tenni, hogy többé.

311
00:15:11,728 --> 00:15:13,880
Azt már tudjuk,
korlátait, hogy módszer.

312
00:15:13,880 --> 00:15:20,170
Most a hash tábla lesz
egy sor 10 csomópontok, pointerek

313
00:15:20,170 --> 00:15:22,120
a feje láncolt listák.

314
00:15:22,120 --> 00:15:23,830
>> És most ez null.

315
00:15:23,830 --> 00:15:26,170
Minden egyes ilyen 10 mutató null.

316
00:15:26,170 --> 00:15:29,870
Nincs semmi a mi
hasítótábla most.

317
00:15:29,870 --> 00:15:32,690
>> Most kezdjük, hogy egy kis
dolgok ebbe hash tábla.

318
00:15:32,690 --> 00:15:35,440
És nézzük meg, hogyan ez a módszer
fog részesülni nekünk egy kicsit.

319
00:15:35,440 --> 00:15:36,760
Nézzük most hash Joey.

320
00:15:36,760 --> 00:15:40,210
Majd fog futni a húr Joey keresztül
a hash függvény, és visszatérünk 6.

321
00:15:40,210 --> 00:15:41,200
Nos, mit tegyünk most?

322
00:15:41,200 --> 00:15:44,090
>> Hát most dolgozik láncolt listák,
már nem dolgozunk együtt tömbök.

323
00:15:44,090 --> 00:15:45,881
És amikor dolgozunk
A láncolt listák vagyunk

324
00:15:45,881 --> 00:15:49,790
tudom, el kell kezdenünk dinamikusan
foglalt hely és az építési láncok.

325
00:15:49,790 --> 00:15:54,020
Ez a fajta how-- ezek a mag
elemei épület egy láncolt lista.

326
00:15:54,020 --> 00:15:57,670
Úgyhogy dinamikusan
osztja helyet Joey,

327
00:15:57,670 --> 00:16:00,390
majd tegyük hozzá, hogy a lánc.

328
00:16:00,390 --> 00:16:03,170
>> Szóval most nézd, mit tettünk.

329
00:16:03,170 --> 00:16:06,440
Amikor hash Joey megkaptuk az hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Most a mutató a tömb helyen 6
rámutat, hogy a feje egy láncolt lista,

331
00:16:11,790 --> 00:16:14,900
és most ez az egyetlen
eleme egy láncolt lista.

332
00:16:14,900 --> 00:16:18,350
És a csomópont, hogy
láncolt lista Joey.

333
00:16:18,350 --> 00:16:22,300
>> Tehát, ha szükségünk van, hogy néz ki Joey
Később, mi csak hash Joey újra,

334
00:16:22,300 --> 00:16:26,300
jutunk ismét a 6, mert a
hash függvény determinisztikus.

335
00:16:26,300 --> 00:16:30,400
És akkor kezdjük élén
A láncolt lista rámutatott

336
00:16:30,400 --> 00:16:33,360
hogy a tömb helyét
6, és mehetünk

337
00:16:33,360 --> 00:16:35,650
szerte, hogy megpróbálja megtalálni Joey.

338
00:16:35,650 --> 00:16:37,780
És ha építünk
hash tábla hatékony,

339
00:16:37,780 --> 00:16:41,790
és mi hash hatékonyan működnek
terjeszteni adatok is,

340
00:16:41,790 --> 00:16:45,770
átlagosan minden egyes ilyen kapcsolódik
listák minden tömb helyét

341
00:16:45,770 --> 00:16:50,110
lesz 1/10 a méret, ha
Csak volt, mint egy egyetlen hatalmas

342
00:16:50,110 --> 00:16:51,650
kapcsolt lista minden benne van.

343
00:16:51,650 --> 00:16:55,670
>> Ha terjeszteni, hogy hatalmas összefüggő
lista fölött 10 láncolt listák

344
00:16:55,670 --> 00:16:57,760
Minden lista lesz 1/10 méretét.

345
00:16:57,760 --> 00:17:01,432
És így 10-szer gyorsabb
keresgélni.

346
00:17:01,432 --> 00:17:02,390
Úgyhogy ezt újra.

347
00:17:02,390 --> 00:17:04,290
Nézzük most hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> És mondjuk Ross, amikor ezt tesszük
A hash kódot kapunk vissza 2.

349
00:17:07,540 --> 00:17:10,630
Hát most már dinamikusan hozzárendel egy
Új csomópont tesszük Ross abban csomópont,

350
00:17:10,630 --> 00:17:14,900
és azt mondjuk most tömb helyét
2, ahelyett, rámutatva, hogy null,

351
00:17:14,900 --> 00:17:18,579
rámutat, hogy a feje egy kapcsolt
listán, akiknek egyetlen csomópont Ross.

352
00:17:18,579 --> 00:17:22,660
És ezt meg tudjuk tenni még egyszer, mi
lehet hash Rachel és kap hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc egy új csomópont, tedd Rachel
A csomópont, és mondjuk egy tömb helyét

354
00:17:25,490 --> 00:17:27,839
4. utal most már a fejét
Egy hivatkozott lista, amelynek

355
00:17:27,839 --> 00:17:31,420
egyetlen elem előfordul, hogy Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, de mi történik, ha
van egy ütközés?

357
00:17:33,470 --> 00:17:38,560
Lássuk, hogyan kezeljük ütközések
az önálló láncolás módszer.

358
00:17:38,560 --> 00:17:39,800
Nézzük hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Kapunk a hashcode 6.

360
00:17:41,094 --> 00:17:44,010
Korábbi például voltunk, csak
tárolja a húrok a tömbben.

361
00:17:44,010 --> 00:17:45,980
Ez volt a probléma.

362
00:17:45,980 --> 00:17:48,444
>> Nem akarunk a cucc
Joey, és mi már

363
00:17:48,444 --> 00:17:51,110
Látható, hogy mi tud kap valamiféle csoportosulás
problémákat, ha megpróbálunk lépést

364
00:17:51,110 --> 00:17:52,202
keresztül és a szonda.

365
00:17:52,202 --> 00:17:54,660
De mi van, ha csak ilyen
kezeli ezt ugyanúgy, ugye?

366
00:17:54,660 --> 00:17:57,440
Olyan ez, mint egy elem hozzáadásával
hogy a feje egy láncolt lista.

367
00:17:57,440 --> 00:18:00,220
Nézzük csak malloc helyet Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Majd azt mondjuk, Phoebe következő mutató
a régi vezetője a láncolt lista,

369
00:18:04,764 --> 00:18:07,180
majd 6 csak arra utal, hogy a
új vezetője a láncolt lista.

370
00:18:07,180 --> 00:18:10,150
És most nézd, mi már megváltozott Phoebe in.

371
00:18:10,150 --> 00:18:14,210
Most már tárolni két
elemek hashcode 6,

372
00:18:14,210 --> 00:18:17,170
és nincs semmilyen probléma.

373
00:18:17,170 --> 00:18:20,147
>> Ez elég sok minden
van, hogy láncolás.

374
00:18:20,147 --> 00:18:21,980
És láncolatok határozottan
A módszer ez

375
00:18:21,980 --> 00:18:27,390
lesz a leghatékonyabb az Ön számára, ha
akkor tárolja az adatokat egy hash tábla.

376
00:18:27,390 --> 00:18:30,890
De ez a kombináció
tömbök és láncolt listák

377
00:18:30,890 --> 00:18:36,080
együtt alkotnak egy hash tábla igazán
drámaian javítja a képességét,

378
00:18:36,080 --> 00:18:40,550
tárolni nagy mennyiségű adatot, és
Nagyon gyorsan és hatékonyan keresni

379
00:18:40,550 --> 00:18:41,630
révén, hogy az adatok.

380
00:18:41,630 --> 00:18:44,150
>> Van még egy további
adatstruktúra odakinn

381
00:18:44,150 --> 00:18:48,700
hogy talán még egy kicsit
Jobb a biztosító

382
00:18:48,700 --> 00:18:51,920
hogy a mi inszerció, deléció, és
felnéz alkalommal még gyorsabbak.

383
00:18:51,920 --> 00:18:55,630
És majd meglátjuk, hogy egy videót próbál.

384
00:18:55,630 --> 00:18:58,930
Én Doug Lloyd, ez CS50.

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