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

2
00:00:00,500 --> 00:00:01,900
[Přehrávání hudby]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Do teď jste
vědí hodně o pole,

5
00:00:09,150 --> 00:00:11,610
a víte, že hodně o spojových seznamů.

6
00:00:11,610 --> 00:00:13,650
A máme diskutovat
klady a zápory, které jsme

7
00:00:13,650 --> 00:00:16,620
diskutovali, který spojoval seznamy
Můžete získat větší a menší,

8
00:00:16,620 --> 00:00:18,630
ale zabírají větší velikost.

9
00:00:18,630 --> 00:00:22,359
Pole jsou mnohem jednodušší na
použití, ale oni jsou restriktivní v té míře,

10
00:00:22,359 --> 00:00:24,900
jak musíme nastavit velikost
pole na samém začátku

11
00:00:24,900 --> 00:00:26,910
a pak jsme s tím nenadělají.

12
00:00:26,910 --> 00:00:30,470
>> Ale to je, máme docela hodně
vyčerpal všechny naše témat

13
00:00:30,470 --> 00:00:33,040
o propojených seznamů a polí.

14
00:00:33,040 --> 00:00:34,950
Nebo máme?

15
00:00:34,950 --> 00:00:37,720
Možná, že můžeme něco udělat
ještě více kreativní.

16
00:00:37,720 --> 00:00:40,950
A to druh, půjčuje
myšlenka na hash tabulky.

17
00:00:40,950 --> 00:00:46,680
>> Takže v tabulce hash budeme se snažit
kombinují pole se seznamem Google.

18
00:00:46,680 --> 00:00:49,520
Budeme mít výhody
matice, stejně jako náhodný přístup,

19
00:00:49,520 --> 00:00:53,510
budou moci jen jít do pole
element 4 nebo prvek pole 8

20
00:00:53,510 --> 00:00:55,560
aniž by museli přecházet přes.

21
00:00:55,560 --> 00:00:57,260
To je dost rychle, ne?

22
00:00:57,260 --> 00:01:00,714
>> Ale také chceme mít naše data
struktura moci růst a zmenšit.

23
00:01:00,714 --> 00:01:02,630
Nepotřebujeme, my ne
chtějí být omezeno.

24
00:01:02,630 --> 00:01:04,588
A my chceme být schopni
přidávat a odebírat věci

25
00:01:04,588 --> 00:01:08,430
velmi snadno, které, pokud si vzpomínáte,
je velmi složitá s řadou.

26
00:01:08,430 --> 00:01:11,650
A můžeme volat toto
Novinkou hash tabulky.

27
00:01:11,650 --> 00:01:15,190
>> A pokud by byla provedena správně,
my jsme nějak převzetí

28
00:01:15,190 --> 00:01:18,150
výhod obou údajů
struktury, které jste již viděli,

29
00:01:18,150 --> 00:01:19,880
pole a spojové seznamy.

30
00:01:19,880 --> 00:01:23,070
Vkládání může začít
inklinovat k theta z 1.

31
00:01:23,070 --> 00:01:26,207
Theta jsme se opravdu diskutováno,
ale theta je jen průměrný případ,

32
00:01:26,207 --> 00:01:27,540
co se vlastně bude dít.

33
00:01:27,540 --> 00:01:29,680
Nejste vždycky
mají nejhorší možný scénář,

34
00:01:29,680 --> 00:01:32,555
a vy ne vždy bude mít
nejlepší scénář, takže to, co je

35
00:01:32,555 --> 00:01:33,900
průměrný scénář?

36
00:01:33,900 --> 00:01:36,500
>> No průměrná vložení
do hash tabulky

37
00:01:36,500 --> 00:01:39,370
Můžete začít se dostat blízko k konstantním čase.

38
00:01:39,370 --> 00:01:41,570
A mazání může dostat
blízko k konstantním čase.

39
00:01:41,570 --> 00:01:44,440
A vyhledávání může dostat
blízko k konstantním čase.

40
00:01:44,440 --> 00:01:48,600
That's-- nemáme data:
struktura přesto, že může dělat to,

41
00:01:48,600 --> 00:01:51,180
a tak to už zní
jako docela velkou věc.

42
00:01:51,180 --> 00:01:57,010
My jsme opravdu mírní
nevýhody každého z nich na jeho vlastní.

43
00:01:57,010 --> 00:01:59,160
>> Chcete-li získat toto představení
upgradovat i když jsme

44
00:01:59,160 --> 00:02:03,580
je třeba promyslet, jak přidáme
dat do konstrukce.

45
00:02:03,580 --> 00:02:07,380
Konkrétně chceme,
Data sama o sobě, aby nám řekli

46
00:02:07,380 --> 00:02:09,725
pokud by mělo jít ve struktuře.

47
00:02:09,725 --> 00:02:12,850
A když jsme pak je třeba zjistit, jestli je to ve
struktura, pokud budeme potřebovat, aby ji najít,

48
00:02:12,850 --> 00:02:16,610
Chceme se podívat na data,
Znovu a musí být schopen efektivně,

49
00:02:16,610 --> 00:02:18,910
použití dat, náhodně přístup.

50
00:02:18,910 --> 00:02:20,700
Jen tím, že při pohledu na
Údaje bychom měli mít

51
00:02:20,700 --> 00:02:25,890
nápad, kde přesně jsme
bude najít v tabulce hash.

52
00:02:25,890 --> 00:02:28,770
>> Nyní Nevýhodou hash
Tabulka je, že jsou opravdu

53
00:02:28,770 --> 00:02:31,770
dost špatné na objednávce nebo při řazení dat.

54
00:02:31,770 --> 00:02:34,970
A ve skutečnosti, když začnete
použít jim nařídit nebo třídění

55
00:02:34,970 --> 00:02:37,990
Data ztratíte všechny
Výhody, které jste předtím

56
00:02:37,990 --> 00:02:40,710
měl, pokud jde o vkládání a mazání.

57
00:02:40,710 --> 00:02:44,060
Čas se stává blíž
theta n, a my jsme v podstatě

58
00:02:44,060 --> 00:02:45,530
ustoupila do propojeného seznamu.

59
00:02:45,530 --> 00:02:48,850
A tak jsme se jen chcete použít hash
stoly, kdybychom se nestarají o

60
00:02:48,850 --> 00:02:51,490
zda se data budou seřazeny.

61
00:02:51,490 --> 00:02:54,290
Pro kontextu, v němž
budete používat je v CS50

62
00:02:54,290 --> 00:02:58,900
pravděpodobně nezajímá
že data jsou řazeny.

63
00:02:58,900 --> 00:03:03,170
>> Takže hash tabulka je kombinací
ze dvou odlišných kusů

64
00:03:03,170 --> 00:03:04,980
s nimiž jsme obeznámeni.

65
00:03:04,980 --> 00:03:07,930
Prvním z nich je funkce, která
obvykle nazýváme hash funkce.

66
00:03:07,930 --> 00:03:11,760
A to hash funkce se chystá
vrátit nějaké nezáporné celé číslo, které

67
00:03:11,760 --> 00:03:14,870
obvykle zavolat hodnotu hash, OK?

68
00:03:14,870 --> 00:03:20,230
Druhá část je pole, což je
schopný ukládání dat typu my

69
00:03:20,230 --> 00:03:22,190
umístit do datové struktury.

70
00:03:22,190 --> 00:03:24,310
Budeme odložit na
spojový seznam prvku teď

71
00:03:24,310 --> 00:03:27,810
a jen začít se základy
hash tabulky, aby si hlavu kolem něj,

72
00:03:27,810 --> 00:03:30,210
a pak budeme možná foukat
vaše mysl trochu, když jsme

73
00:03:30,210 --> 00:03:32,920
kombinují pole a propojení seznamů dohromady.

74
00:03:32,920 --> 00:03:35,590
>> Základní myšlenka ačkoli
je bereme některá data.

75
00:03:35,590 --> 00:03:37,860
Provozujeme data prostřednictvím
funkce hash.

76
00:03:37,860 --> 00:03:41,980
A tak se data zpracována
a to vyplivne číslo, OK?

77
00:03:41,980 --> 00:03:44,890
A pak se s tímto číslem
my jen ukládání dat

78
00:03:44,890 --> 00:03:48,930
chceme uložit do
Pole na tomto místě.

79
00:03:48,930 --> 00:03:53,990
Tak například máme možná
Tento hash tabulky řetězců.

80
00:03:53,990 --> 00:03:57,350
Je tu 10 prvků v něm, tak
můžeme vejde 10 řetězce v něm.

81
00:03:57,350 --> 00:03:59,320
>> Řekněme, že chceme, aby hash Johna.

82
00:03:59,320 --> 00:04:02,979
Tak jako Jan dat chceme vložit
Do této tabulky hash někde.

83
00:04:02,979 --> 00:04:03,770
Kam dát?

84
00:04:03,770 --> 00:04:05,728
No typicky S
array zatím jsme asi

85
00:04:05,728 --> 00:04:07,610
by se dát do lokalitě pole 0.

86
00:04:07,610 --> 00:04:09,960
Ale teď máme tuto novou funkci hash.

87
00:04:09,960 --> 00:04:13,180
>> A řekněme, že běžíme Johna
Pomocí této funkce hash

88
00:04:13,180 --> 00:04:15,417
a to vyplivne 4.

89
00:04:15,417 --> 00:04:17,500
No, to je místo, kde jsme
bude chtít dát Johna.

90
00:04:17,500 --> 00:04:22,050
Chceme dát Johnovi v místě pole
4, protože pokud bychom hash Johna again--

91
00:04:22,050 --> 00:04:23,810
řekněme, že později jsme
chcete vyhledat a zobrazit

92
00:04:23,810 --> 00:04:26,960
pokud John existuje v tomto hash
table-- vše, co potřebujete udělat,

93
00:04:26,960 --> 00:04:30,310
je provozován přes stejné hash
funkce, dostanete číslo 4 out,

94
00:04:30,310 --> 00:04:33,929
a musí být schopen najít John
ihned v naší datové struktuře.

95
00:04:33,929 --> 00:04:34,720
To je docela dobrý.

96
00:04:34,720 --> 00:04:36,928
>> Řekněme, že teď to udělat
Znovu chceme hash Paul.

97
00:04:36,928 --> 00:04:39,446
Chceme přidat Paul
Do této tabulky hash.

98
00:04:39,446 --> 00:04:42,070
Řekněme, že jsme tentokrát spuštění
Paul pomocí funkce hash,

99
00:04:42,070 --> 00:04:44,600
hashCode, který je generován je 6.

100
00:04:44,600 --> 00:04:47,340
No teď můžeme dát Paul
v místě pole 6.

101
00:04:47,340 --> 00:04:50,040
A pokud budeme muset podívat do zda
Paul je v této tabulce hash,

102
00:04:50,040 --> 00:04:53,900
vše, co potřebujeme udělat, je spustit Paul
pomocí hash funkce znovu

103
00:04:53,900 --> 00:04:55,830
a budeme se dostat 6 zase ven.

104
00:04:55,830 --> 00:04:57,590
>> A pak jsme se jen podívat
v místě pole 6.

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

106
00:04:58,910 --> 00:05:00,160
Pokud ano, je to v tabulce hash.

107
00:05:00,160 --> 00:05:01,875
Není Paul ne?

108
00:05:01,875 --> 00:05:03,000
On není v tabulce hash.

109
00:05:03,000 --> 00:05:05,720
Je to docela jednoduché.

110
00:05:05,720 --> 00:05:07,770
>> Nyní, jak si definovat hash funkce?

111
00:05:07,770 --> 00:05:11,460
No tam je opravdu žádný limit na
počet možných funkcí hash.

112
00:05:11,460 --> 00:05:14,350
Ve skutečnosti existuje celá řada opravdu,
Opravdu dobří na internetu.

113
00:05:14,350 --> 00:05:17,560
K dispozici je celá řada opravdu,
Opravdu špatné ty na internetu.

114
00:05:17,560 --> 00:05:21,080
Je to také docela snadné
napsat špatný jeden.

115
00:05:21,080 --> 00:05:23,760
>> Takže to, co tvoří dobrý
hash funkce, že jo?

116
00:05:23,760 --> 00:05:27,280
No dobrá hashovací funkce by
použít pouze se hashed data,

117
00:05:27,280 --> 00:05:29,420
a všechna data jsou hash.

118
00:05:29,420 --> 00:05:32,500
Takže nechceme používat anything--
nemáme nic začlenit

119
00:05:32,500 --> 00:05:35,560
jiný než data.

120
00:05:35,560 --> 00:05:37,080
A chceme používat všechna data.

121
00:05:37,080 --> 00:05:39,830
Nechceme, aby stačí použít kus
z toho, chceme použít všechno.

122
00:05:39,830 --> 00:05:41,710
Funkce hash by měl
být také deterministické.

123
00:05:41,710 --> 00:05:42,550
Co to znamená?

124
00:05:42,550 --> 00:05:46,200
No to znamená, že pokaždé, když
projít přesně stejný kus dat

125
00:05:46,200 --> 00:05:50,040
do funkce hash vždy
získat stejný hodnotu hash ven.

126
00:05:50,040 --> 00:05:52,870
Kdybych projít Johna do
hash funkce se dostanu ven 4.

127
00:05:52,870 --> 00:05:56,110
Měl bych být schopen to udělat 10.000
časy a já budu vždy 4.

128
00:05:56,110 --> 00:06:00,810
Takže žádné náhodná čísla účinně
se mohou zapojit do naší hash tables--

129
00:06:00,810 --> 00:06:02,750
v našich hašovacích funkcích.

130
00:06:02,750 --> 00:06:05,750
>> Funkce hash by také
rovnoměrně distribuci dat.

131
00:06:05,750 --> 00:06:09,700
Pokud by každý spuštění dat prostřednictvím
hash funkce dostanete hodnotu hash 0,

132
00:06:09,700 --> 00:06:11,200
že to asi není tak velký, že jo?

133
00:06:11,200 --> 00:06:14,600
Pravděpodobně budete chtít, aby velký
řada hash kódů.

134
00:06:14,600 --> 00:06:17,190
Také věci mohou být rozloženy
v průběhu celého stolu.

135
00:06:17,190 --> 00:06:23,210
A také, že by bylo skvělé, kdyby opravdu
podobné údaje, jako jsou John a Jonathan,

136
00:06:23,210 --> 00:06:26,320
Možná byly rozprostřeny vážit
různá umístění v tabulce hash.

137
00:06:26,320 --> 00:06:28,750
To by bylo hezký výhoda.

138
00:06:28,750 --> 00:06:31,250
>> Zde je příklad funkce hash.

139
00:06:31,250 --> 00:06:33,150
Napsal jsem tenhle přivstat.

140
00:06:33,150 --> 00:06:35,047
Není to zvlášť
dobrá funkce hash

141
00:06:35,047 --> 00:06:37,380
z důvodů, které nemají ve skutečnosti
medvěd jít do teď.

142
00:06:37,380 --> 00:06:41,040
Ale vidíte, co se tu děje?

143
00:06:41,040 --> 00:06:44,420
Vypadá to, že jsme deklarování proměnné
volal součet a nastavení rovno 0.

144
00:06:44,420 --> 00:06:50,010
A pak prý dělám něco
tak dlouho, jak strstr [j] není rovno

145
00:06:50,010 --> 00:06:52,490
na zpětná lomítka 0.

146
00:06:52,490 --> 00:06:54,870
Co já jsem tam dělal?

147
00:06:54,870 --> 00:06:57,440
>> To je v podstatě jen další
způsob provádění [? strl?]

148
00:06:57,440 --> 00:06:59,773
a detekci, když jsem
dostal na konec řetězce.

149
00:06:59,773 --> 00:07:02,480
Takže nemám skutečně
vypočítat délku řetězce,

150
00:07:02,480 --> 00:07:05,640
Já jsem jen pomocí, když jsem hit
zpětné lomítko 0 postava vím

151
00:07:05,640 --> 00:07:07,185
Já jsem došel na konec řetězce.

152
00:07:07,185 --> 00:07:09,560
A pak budu držet
iterace tohoto řetězce,

153
00:07:09,560 --> 00:07:15,310
přidávání strstr [j] sečíst, a pak na
konci dne vracet částky mod

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

155
00:07:16,200 --> 00:07:18,700
>> V podstatě vše hash
Funkce je dělá, je sčítání

156
00:07:18,700 --> 00:07:23,450
všechny hodnoty ASCII
můj řetězec, a pak je to

157
00:07:23,450 --> 00:07:26,390
navracení hodnotu hash
modded by HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Je to asi o velikosti
mé pole, ne?

159
00:07:29,790 --> 00:07:33,160
Nechci se dostat hash
kódy, pokud jsou moje pole je velikosti 10,

160
00:07:33,160 --> 00:07:35,712
Nechci být získání
out hash kódy 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, nemohu dát věci do
Tato místa z pole,

162
00:07:38,690 --> 00:07:39,790
že by bylo nezákonné.

163
00:07:39,790 --> 00:07:42,130
Já bych trpět chybu segmentace.

164
00:07:42,130 --> 00:07:45,230
>> Nyní je zde další rychlý stranou.

165
00:07:45,230 --> 00:07:48,470
Obecně budete pravděpodobně nebude
Chcete napsat vlastní hash funkce.

166
00:07:48,470 --> 00:07:50,997
Je to vlastně trochu
umění, není věda.

167
00:07:50,997 --> 00:07:52,580
A je tu hodně, že jde do nich.

168
00:07:52,580 --> 00:07:55,288
Internet, jak jsem řekl, je plný
opravdu dobrých hašovacích funkcí,

169
00:07:55,288 --> 00:07:58,470
a vy byste měli používat internet k
najít hash funkce, protože je to opravdu

170
00:07:58,470 --> 00:08:03,230
jen tak zbytečným
ztráta času vytvořit si vlastní.

171
00:08:03,230 --> 00:08:05,490
>> Můžete napsat ty jednoduché
pro účely testování.

172
00:08:05,490 --> 00:08:08,323
Ale když jste vlastně se chystáte
spustit zatřiďování data a ukládá je

173
00:08:08,323 --> 00:08:10,780
do hash tabulky, kterou jste
pravděpodobně bude chtít

174
00:08:10,780 --> 00:08:14,580
použít nějakou funkci, která byla generována
pro tebe, který existuje na internetu.

175
00:08:14,580 --> 00:08:17,240
Pokud si prostě být jisti,
citovat své zdroje.

176
00:08:17,240 --> 00:08:21,740
Neexistuje žádný důvod, aby
napodobit něco tady.

177
00:08:21,740 --> 00:08:25,370
>> Počítač vědy komunita je
rozhodně roste, a opravdu hodnoty

178
00:08:25,370 --> 00:08:28,796
open source, a je to opravdu důležité,
citovat své zdroje tak, aby lidé

179
00:08:28,796 --> 00:08:30,670
mohou získat autorství
dílo, které jsou

180
00:08:30,670 --> 00:08:32,312
dělá ve prospěch komunity.

181
00:08:32,312 --> 00:08:34,020
Takže vždy sure--
a to nejen pro hash

182
00:08:34,020 --> 00:08:37,270
funkce, ale obecně, když vás
použít kód z vnějšího zdroje,

183
00:08:37,270 --> 00:08:38,299
vždy uveďte svůj zdroj.

184
00:08:38,299 --> 00:08:43,500
Dát úvěr na osoby, která ji
některé práce, takže si nemusíte.

185
00:08:43,500 --> 00:08:46,720
>> OK, takže pojďme to znovu
hash tabulky na vteřinu.

186
00:08:46,720 --> 00:08:48,780
To je místo, kde jsme opustili
off poté, co jsme vkládají

187
00:08:48,780 --> 00:08:53,300
John a Paul do tohoto hash tabulky.

188
00:08:53,300 --> 00:08:55,180
Vidíte tu problém?

189
00:08:55,180 --> 00:08:58,410
Můžete vidět dva.

190
00:08:58,410 --> 00:09:02,240
Ale zejména, že ne
viz tento možný problém?

191
00:09:02,240 --> 00:09:06,770
>> Co když hash Ringo, a to
Ukazuje se, že po zpracování

192
00:09:06,770 --> 00:09:14,000
že údaje prostřednictvím funkce hash
Ringo také generovány na hodnotu hash 6.

193
00:09:14,000 --> 00:09:16,810
Už mám data
hashcode-- umístění pole 6.

194
00:09:16,810 --> 00:09:22,000
Takže to asi bude trochu
problému teď pro mě, že jo?

195
00:09:22,000 --> 00:09:23,060
>> Říkáme tomu kolize.

196
00:09:23,060 --> 00:09:26,460
A dochází ke kolizi, když dva
objemy dat, procházejí stejným datovým

197
00:09:26,460 --> 00:09:29,200
funkce dávají stejnou hodnotu hash.

198
00:09:29,200 --> 00:09:32,850
Pravděpodobně stále chceme získat oba
kusy dat do tabulky hash,

199
00:09:32,850 --> 00:09:36,330
jinak bychom být spuštěn Ringo
libovolně pomocí hash funkce.

200
00:09:36,330 --> 00:09:40,870
Pravděpodobně Chceme se dostat
Ringo do tohoto pole.

201
00:09:40,870 --> 00:09:46,070
>> Jak to děláme i když, kdyby se
a Paul oba výnos hashCode 6?

202
00:09:46,070 --> 00:09:49,520
Nechceme, aby přepsat Paula,
Chceme Paul, aby se tam taky.

203
00:09:49,520 --> 00:09:52,790
Proto musíme najít způsob, jak dostat
prvky do tabulky hash, který

204
00:09:52,790 --> 00:09:56,550
stále zachovává rychlém
vkládání a rychlý pohled vzhůru.

205
00:09:56,550 --> 00:10:01,350
A jeden způsob, jak se s tím vypořádat, je
dělat něco, co nazývá lineární sondování.

206
00:10:01,350 --> 00:10:04,170
>> Pomocí této metody, pokud máme
kolize, no, co budeme dělat?

207
00:10:04,170 --> 00:10:08,580
No nemůžeme ho v místě pole
6, nebo cokoliv hashCode byl vytvořen,

208
00:10:08,580 --> 00:10:10,820
pojďme ho na hashCode plus 1.

209
00:10:10,820 --> 00:10:13,670
A pokud to plná pojďme
dal ho do hashCode plus 2.

210
00:10:13,670 --> 00:10:17,420
Výhodou této bytosti, pokud je to
Není přesně tam, kde si myslíme, že je,

211
00:10:17,420 --> 00:10:20,850
a my musíme začít hledat,
Možná nemusíme jít příliš daleko.

212
00:10:20,850 --> 00:10:23,900
Možná, že nemáme hledat
všechny n prvky tabulky hash.

213
00:10:23,900 --> 00:10:25,790
Možná, že budeme muset hledat
několik z nich.

214
00:10:25,790 --> 00:10:30,680
>> A tak jsme stále vedou k
že průměrný případ je blízko k 1 vs

215
00:10:30,680 --> 00:10:34,280
v blízkosti n, takže možná to bude fungovat.

216
00:10:34,280 --> 00:10:38,010
Takže pojďme se podívat, jak to
by mohlo fungovat v praxi.

217
00:10:38,010 --> 00:10:41,460
A uvidíme, jestli bychom možná dokáže detekovat
problém, že zde může dojít.

218
00:10:41,460 --> 00:10:42,540
>> Řekněme, že jsme hashovat Barta.

219
00:10:42,540 --> 00:10:45,581
Takže teď budeme provozovat nový soubor
řetězců přes hash funkce,

220
00:10:45,581 --> 00:10:48,460
a my běh Barta přes hash
funkce, dostaneme hodnotu hash 6.

221
00:10:48,460 --> 00:10:52,100
Jsme se podívat, vidíme, 6
prázdné, takže můžeme dát tam Barta.

222
00:10:52,100 --> 00:10:55,410
>> Nyní jsme hash Lisu a že
také generuje hodnotu hash 6.

223
00:10:55,410 --> 00:10:58,330
Tak teď, když jsme pomocí tohoto
lineární sondování metodu začneme 6,

224
00:10:58,330 --> 00:10:59,330
vidíme, že 6 je plná.

225
00:10:59,330 --> 00:11:00,990
Nemůžeme dát Lisu v 6.

226
00:11:00,990 --> 00:11:02,090
Tak kam půjdeme?

227
00:11:02,090 --> 00:11:03,280
Pojďme až 7.

228
00:11:03,280 --> 00:11:04,610
7 je prázdná, tak to funguje.

229
00:11:04,610 --> 00:11:06,510
Takže pojďme dát Lisa tam.

230
00:11:06,510 --> 00:11:10,200
>> Nyní jsme hash Homera a dostaneme 7.

231
00:11:10,200 --> 00:11:13,380
OK dobře víme, že 7 je plný
Nyní, takže nemůžeme dát tam Homer.

232
00:11:13,380 --> 00:11:14,850
Tak pojďme na 8.

233
00:11:14,850 --> 00:11:15,664
Je k dispozici 8?

234
00:11:15,664 --> 00:11:18,330
Jo, v blízkosti 8 k 7, takže pokud
musíme začít hledat jsme

235
00:11:18,330 --> 00:11:20,020
nebude muset jít příliš daleko.

236
00:11:20,020 --> 00:11:22,860
A tak se pojďme dát Homerovi v 8.

237
00:11:22,860 --> 00:11:25,151
>> Nyní jsme hash Maggie a
3 se vrací, díky bohu

238
00:11:25,151 --> 00:11:26,650
jsme schopni jen dát Maggie tam.

239
00:11:26,650 --> 00:11:29,070
Nemusíme dělat jakýkoli
druh sondování za to.

240
00:11:29,070 --> 00:11:32,000
Teď jsme hash Marge, a
Marge také vrací 6.

241
00:11:32,000 --> 00:11:39,560
>> No 6 je plná, 7 je plná, 8 je plná,
9, v pořádku díky Bohu, 9 je prázdný.

242
00:11:39,560 --> 00:11:41,600
Můžu dát Marge na 9.

243
00:11:41,600 --> 00:11:45,280
Už můžeme vidět, že my teď začínáme
aby tento problém, kde teď jsme

244
00:11:45,280 --> 00:11:48,780
začíná natáhnout věci druh
daleko od svých hash kódy.

245
00:11:48,780 --> 00:11:52,960
A to theta 1, že průměrný
Případ je konstantní čas,

246
00:11:52,960 --> 00:11:56,560
začíná být trochu more--
začíná o něco větší tendenci

247
00:11:56,560 --> 00:11:58,050
směrem k theta n.

248
00:11:58,050 --> 00:12:01,270
Začínáme ztrácet, že
Výhodou stoly mřížky.

249
00:12:01,270 --> 00:12:03,902
>> Tento problém, který jsme právě viděli
je něco, co nazývá shlukování.

250
00:12:03,902 --> 00:12:06,360
A co je opravdu špatného na tom,
clustering je, že jakmile vás teď

251
00:12:06,360 --> 00:12:09,606
mají dva prvky, které jsou vedle
stranu to dělá to ještě pravděpodobnější,

252
00:12:09,606 --> 00:12:11,480
Máte dvojnásobek
šance, že budete

253
00:12:11,480 --> 00:12:13,516
mít další kolize
clusteru s tím,

254
00:12:13,516 --> 00:12:14,890
a cluster poroste o jedno.

255
00:12:14,890 --> 00:12:19,640
A budete neustále rostou a roste
Váš pravděpodobnost mít kolizi.

256
00:12:19,640 --> 00:12:24,470
A nakonec je to stejně špatné
tak, že třídění dat vůbec.

257
00:12:24,470 --> 00:12:27,590
>> Dalším problémem však je, že jsme
stále, a tak daleko, až do tohoto bodu,

258
00:12:27,590 --> 00:12:30,336
právě jsme byli tak nějak
pochopení toho, co hash tabulka je,

259
00:12:30,336 --> 00:12:31,960
máme stále jen prostor pro 10 řetězců.

260
00:12:31,960 --> 00:12:37,030
Pokud chceme, aby i nadále hash
občané Springfieldu,

261
00:12:37,030 --> 00:12:38,790
můžeme jen získat 10 z nich tam.

262
00:12:38,790 --> 00:12:42,619
A když se budeme snažit a přidejte 11. nebo 12.,
nemáme místo, aby je dal.

263
00:12:42,619 --> 00:12:45,660
Mohli bychom se točí kolem
kruhy se snaží najít prázdné místo,

264
00:12:45,660 --> 00:12:49,000
a my jsme možná uvíznou
v nekonečné smyčce.

265
00:12:49,000 --> 00:12:51,810
>> Takže tento druh půjčuje myšlenku
něco volal řetězení.

266
00:12:51,810 --> 00:12:55,790
A to je místo, kde budeme přinášet
spojové seznamy zpět do obrazu.

267
00:12:55,790 --> 00:13:01,300
Co když místo uložení právě
samotná data v poli,

268
00:13:01,300 --> 00:13:04,471
každý prvek matice mohla
držet více částí dat?

269
00:13:04,471 --> 00:13:05,970
No, to nedává smysl, že jo?

270
00:13:05,970 --> 00:13:09,280
Víme jen to, že pole může
hold-- každého prvku pole

271
00:13:09,280 --> 00:13:12,930
může mít pouze jeden kus
údajů tohoto typu dat.

272
00:13:12,930 --> 00:13:16,750
>> Ale co když ten typ dat
je propojený seznam, ne?

273
00:13:16,750 --> 00:13:19,830
Takže co kdyby každý
prvek pole byla

274
00:13:19,830 --> 00:13:22,790
ukazatel na hlavě propojeného seznamu?

275
00:13:22,790 --> 00:13:24,680
A pak bychom mohli stavět
ty spojové seznamy

276
00:13:24,680 --> 00:13:27,120
a růst je libovolně,
proto, že spojové seznamy umožňují

277
00:13:27,120 --> 00:13:32,090
náš růst a zmenšit mnohem více
pružněji než pole dělá.

278
00:13:32,090 --> 00:13:34,210
A co když budeme nyní používat,
jsme využít to, že jo?

279
00:13:34,210 --> 00:13:37,760
Máme začít pěstovat tyto řetězy
z těchto míst pole.

280
00:13:37,760 --> 00:13:40,740
>> Nyní jsme se vejde nekonečným
množství dat, nebo není nekonečná,

281
00:13:40,740 --> 00:13:44,170
libovolná částka
Údaje, do našeho hash tabulky

282
00:13:44,170 --> 00:13:47,760
aniž by se běh do
problém kolize.

283
00:13:47,760 --> 00:13:50,740
Také jsme eliminovat
shlukování tím, že dělá to.

284
00:13:50,740 --> 00:13:54,380
A dobře víme, že když jsme se vložit
do propojeného seznamu, pokud si vzpomínáte

285
00:13:54,380 --> 00:13:57,779
z našeho videa na provázané seznamy, jednotlivě
propojené seznamy a dvojnásobně spojové seznamy,

286
00:13:57,779 --> 00:13:59,070
je to neustálý doba provozu.

287
00:13:59,070 --> 00:14:00,710
Jsme jen přidat na frontu.

288
00:14:00,710 --> 00:14:04,400
>> A Look Up, dobře víme,
které vypadají v propojeném seznamu

289
00:14:04,400 --> 00:14:05,785
může být problém, že jo?

290
00:14:05,785 --> 00:14:07,910
Musíme prohledávat
je od začátku až do konce.

291
00:14:07,910 --> 00:14:10,460
Není náhodné
připojení k internetu v Google seznamu.

292
00:14:10,460 --> 00:14:15,610
Avšak v případě, místo toho, aby se jeden z propojených
Seznam kde by vyhledávání být O n,

293
00:14:15,610 --> 00:14:19,590
nyní máme 10 provázané seznamy,
nebo 1000 propojené seznamy,

294
00:14:19,590 --> 00:14:24,120
teď je to ó n děleno 10,
nebo O n děleno 1,000.

295
00:14:24,120 --> 00:14:26,940
>> A když jsme mluvili
teoreticky o složitosti

296
00:14:26,940 --> 00:14:30,061
Pomineme konstanty, v skutečný
svět tyto věci skutečně záleží,

297
00:14:30,061 --> 00:14:30,560
v pořádku?

298
00:14:30,560 --> 00:14:33,080
Vlastně jsme si všimnete
, že se to stane

299
00:14:33,080 --> 00:14:36,610
běžet 10 krát rychleji,
nebo 1000 krát rychlejší,

300
00:14:36,610 --> 00:14:41,570
proto, že jsme rozdělení jedné dlouhé
řetěz přes 1000 menších řetězcích.

301
00:14:41,570 --> 00:14:45,090
A tak pokaždé, když se musíme hledat
prostřednictvím jednoho z těchto řetězců je v našich silách

302
00:14:45,090 --> 00:14:50,290
ignorovat 999 řetězců nás nezajímá
o, a jen hledat, že jeden.

303
00:14:50,290 --> 00:14:53,220
>> Což je v průměru
být 1000x kratší.

304
00:14:53,220 --> 00:14:56,460
A tak jsme pořád jsou tak nějak
směřující k tomuto průměrný případ

305
00:14:56,460 --> 00:15:01,610
z toho, že konstantním čase, ale
jen proto, že jsme se pákového efektu

306
00:15:01,610 --> 00:15:03,730
dělení nějakým velkým konstantním faktorem.

307
00:15:03,730 --> 00:15:05,804
Podívejme se, jak by to mohlo
ve skutečnosti vypadají ačkoli.

308
00:15:05,804 --> 00:15:08,720
Tak tohle byla tabulka hash jsme měli
Než jsme deklarovali hash tabulku, která

309
00:15:08,720 --> 00:15:10,270
byl schopen ukládat 10 řetězců.

310
00:15:10,270 --> 00:15:11,728
Nebudeme dělat, že už ne.

311
00:15:11,728 --> 00:15:13,880
My už víme, že
Omezení této metody.

312
00:15:13,880 --> 00:15:20,170
Nyní náš hash tabulky to bude
řada 10 uzlů, ukazatele

313
00:15:20,170 --> 00:15:22,120
vedoucím spojových seznamů.

314
00:15:22,120 --> 00:15:23,830
>> A právě teď je to null.

315
00:15:23,830 --> 00:15:26,170
Každý z těch 10 ukazatelů je null.

316
00:15:26,170 --> 00:15:29,870
Na tom není nic v Our
hash tabulky právě teď.

317
00:15:29,870 --> 00:15:32,690
>> Nyní pojďme začít, aby některé
věci do tohoto hash tabulky.

318
00:15:32,690 --> 00:15:35,440
A podívejme se, jak je tato metoda
bude nám prospěch trochu.

319
00:15:35,440 --> 00:15:36,760
Pojďme se teď hashovat Joey.

320
00:15:36,760 --> 00:15:40,210
Budeme se spustí řetězec Joey prostřednictvím
funkce hash a vracíme se 6.

321
00:15:40,210 --> 00:15:41,200
Tak co budeme dělat teď?

322
00:15:41,200 --> 00:15:44,090
>> Tak nyní pracuje s propojenými seznamy,
nejsme práci s poli.

323
00:15:44,090 --> 00:15:45,881
A když pracujeme
s propojenými seznamy my

324
00:15:45,881 --> 00:15:49,790
víte, musíme začít dynamicky
přidělování prostoru a stavební řetězy.

325
00:15:49,790 --> 00:15:54,020
To je druh how-- ty jsou jádrem
prvky budování propojeného seznamu.

326
00:15:54,020 --> 00:15:57,670
Takže pojďme dynamicky
přidělit prostor pro Joey,

327
00:15:57,670 --> 00:16:00,390
a pak dodejme ho řetězu.

328
00:16:00,390 --> 00:16:03,170
>> Takže teď se podívejte, co jsme udělali.

329
00:16:03,170 --> 00:16:06,440
Když jsme hash Joey jsme dostali hodnotu hash 6.

330
00:16:06,440 --> 00:16:11,790
Nyní je ukazatel v místě pole 6
poukazuje na čele seznamu Google,

331
00:16:11,790 --> 00:16:14,900
a teď je to jediná
prvek propojeného seznamu.

332
00:16:14,900 --> 00:16:18,350
A uzel se tím, že
spojový seznam je Joey.

333
00:16:18,350 --> 00:16:22,300
>> Takže pokud budeme muset podívat do Joey
později, právě jsme hash Joey znovu,

334
00:16:22,300 --> 00:16:26,300
dostaneme 6 znovu, protože naše
hash funkce je deterministický.

335
00:16:26,300 --> 00:16:30,400
A pak začneme v čele
propojeného seznamu poukázal

336
00:16:30,400 --> 00:16:33,360
se podle umístění pole
6, a můžeme iteraci

337
00:16:33,360 --> 00:16:35,650
přes který se snaží najít Joey.

338
00:16:35,650 --> 00:16:37,780
A pokud budeme budovat naši
účinně hash tabulky,

339
00:16:37,780 --> 00:16:41,790
a naše hash funkce efektivně
distribuovat dat dobře,

340
00:16:41,790 --> 00:16:45,770
v průměru každá z těch, které souvisejí
seznamy na každém místě pole

341
00:16:45,770 --> 00:16:50,110
bude 1/10 velikost kdybychom
prostě musel to jak jeden obrovský

342
00:16:50,110 --> 00:16:51,650
spojový seznam se vším, co v něm.

343
00:16:51,650 --> 00:16:55,670
>> Pokud budeme distribuovat, že obrovské spojené
Seznam přes 10 spojových seznamů

344
00:16:55,670 --> 00:16:57,760
každý seznam bude desetin velikost.

345
00:16:57,760 --> 00:17:01,432
A tedy 10 krát rychlejší
prohledávat.

346
00:17:01,432 --> 00:17:02,390
Takže pojďme to udělat znovu.

347
00:17:02,390 --> 00:17:04,290
Pojďme se teď hashovat Ross.

348
00:17:04,290 --> 00:17:07,540
>> A řekněme, že Ross, když budeme dělat, že
hash kód se vrátíme je 2.

349
00:17:07,540 --> 00:17:10,630
Tak teď jsme dynamicky přidělit
nový uzel, dáme Ross v tomto uzlu,

350
00:17:10,630 --> 00:17:14,900
a říkáme, nyní umístění array
2, místo toho, směřující na null,

351
00:17:14,900 --> 00:17:18,579
poukazuje na hlavu spojené
Seznam jejichž jediným uzel je Ross.

352
00:17:18,579 --> 00:17:22,660
A můžeme to udělat ještě jeden čas, my
mohou hash Rachel a získat hodnotu hash 4.

353
00:17:22,660 --> 00:17:25,490
malloc nový uzel, dal Rachel v
uzel, a říkají, umístění pole

354
00:17:25,490 --> 00:17:27,839
4 nyní ukazuje na hlavě
propojeného seznamu, jehož

355
00:17:27,839 --> 00:17:31,420
Jediným prvkem se stane být Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, ale co se stane, když
máme kolizi?

357
00:17:33,470 --> 00:17:38,560
Podívejme se, jak nakládáme s kolizí
pomocí samostatného metody zřetězení.

358
00:17:38,560 --> 00:17:39,800
Pojďme hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Dostaneme hodnotu hash 6.

360
00:17:41,094 --> 00:17:44,010
V našem předchozím příkladu jsme byli jen
uložení řetězců v poli.

361
00:17:44,010 --> 00:17:45,980
To byl problém.

362
00:17:45,980 --> 00:17:48,444
>> Nechceme, aby nandat
Joey, a už jsme

363
00:17:48,444 --> 00:17:51,110
vidět, že můžeme získat nějaké clustering
problémy, pokud se snažíme krok

364
00:17:51,110 --> 00:17:52,202
až do konce a sonda.

365
00:17:52,202 --> 00:17:54,660
Ale co když jsme právě druh
zacházet to stejně, ne?

366
00:17:54,660 --> 00:17:57,440
Je to jako přidání prvku
na hlavu propojeného seznamu.

367
00:17:57,440 --> 00:18:00,220
Pojďme se jen malloc prostor pro Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Řekneme další ukazatele bodů Phoebe
na staré hlavě Google seznamu,

369
00:18:04,764 --> 00:18:07,180
a poté na 6 jen poukazuje na
nový šéf Google seznamu.

370
00:18:07,180 --> 00:18:10,150
A teď se podívej, že jsme změnili Phoebe v.

371
00:18:10,150 --> 00:18:14,210
Nyní můžeme uložit dva
prvky s hashCode 6,

372
00:18:14,210 --> 00:18:17,170
a my nemáme žádné problémy.

373
00:18:17,170 --> 00:18:20,147
>> To je skoro všechny
tam je řetězení.

374
00:18:20,147 --> 00:18:21,980
A řetězení je určitě
Metoda, která je

375
00:18:21,980 --> 00:18:27,390
bude nejefektivnější pro vás, pokud
jste ukládání dat do tabulky hash.

376
00:18:27,390 --> 00:18:30,890
Ale tato kombinace
pole a spojové seznamy

377
00:18:30,890 --> 00:18:36,080
spolu tvořit hash tabulku opravdu
výrazně zlepšuje vaši schopnost

378
00:18:36,080 --> 00:18:40,550
pro ukládání velkých objemů dat, a
velmi rychle a efektivně vyhledávat

379
00:18:40,550 --> 00:18:41,630
prostřednictvím tohoto data.

380
00:18:41,630 --> 00:18:44,150
>> Je tu ještě jeden
struktura tam údaje

381
00:18:44,150 --> 00:18:48,700
to by mohlo být i trochu
lepší, pokud jde o zajištění

382
00:18:48,700 --> 00:18:51,920
že naše vkládání, mazání, a
Vyhledá časy jsou ještě rychlejší.

383
00:18:51,920 --> 00:18:55,630
A uvidíme, že ve videu na pokusech.

384
00:18:55,630 --> 00:18:58,930
Jsem Doug Lloyd, je to CS50.

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