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

2
00:00:00,500 --> 00:00:01,900
[Prehrávanie hudby]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Do teraz ste
vedia veľa o pole,

5
00:00:09,150 --> 00:00:11,610
a viete, že veľa o spojových zoznamov.

6
00:00:11,610 --> 00:00:13,650
A máme diskutovať
klady a zápory, ktoré sme

7
00:00:13,650 --> 00:00:16,620
diskutovali, ktorý spájal zoznamy
Môžete získať väčšie a menšie,

8
00:00:16,620 --> 00:00:18,630
ale zaberajú väčšiu veľkosť.

9
00:00:18,630 --> 00:00:22,359
Polia sú oveľa jednoduchšie na
použitie, ale oni sú reštriktívne v tej miere,

10
00:00:22,359 --> 00:00:24,900
ako musíme nastaviť veľkosť
polia na samom začiatku

11
00:00:24,900 --> 00:00:26,910
a potom sme s tým nenarobia.

12
00:00:26,910 --> 00:00:30,470
>> Ale to je, máme celkom veľa
vyčerpal všetky naše tém

13
00:00:30,470 --> 00:00:33,040
o prepojených zoznamov a polí.

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

15
00:00:34,950 --> 00:00:37,720
Možno, že môžeme niečo urobiť
ešte viac kreatívne.

16
00:00:37,720 --> 00:00:40,950
A to druh, požičiava
myšlienka na hash tabuľky.

17
00:00:40,950 --> 00:00:46,680
>> Takže v tabuľke hash budeme sa snažiť
kombinujú pole so zoznamom Google.

18
00:00:46,680 --> 00:00:49,520
Budeme mať výhody
matice, rovnako ako náhodný prístup,

19
00:00:49,520 --> 00:00:53,510
budú môcť len ísť do poľa
element 4 alebo prvok poľa 8

20
00:00:53,510 --> 00:00:55,560
bez toho aby museli prechádzať cez.

21
00:00:55,560 --> 00:00:57,260
To je dosť rýchlo, nie?

22
00:00:57,260 --> 00:01:00,714
>> Ale tiež chceme mať naše dáta
štruktúra moci rast a zmenšiť.

23
00:01:00,714 --> 00:01:02,630
Nepotrebujeme, my nie
chcú byť obmedzené.

24
00:01:02,630 --> 00:01:04,588
A my chceme byť schopní
pridávať a odoberať veci

25
00:01:04,588 --> 00:01:08,430
veľmi ľahko, ktoré, ak si spomínate,
je veľmi zložitá s radom.

26
00:01:08,430 --> 00:01:11,650
A môžeme volať toto
Novinkou hash tabuľky.

27
00:01:11,650 --> 00:01:15,190
>> A ak by bola vykonaná správne,
my sme nejako prevzatia

28
00:01:15,190 --> 00:01:18,150
výhod oboch údajov
štruktúry, ktoré ste už videli,

29
00:01:18,150 --> 00:01:19,880
poľa a spojové zoznamy.

30
00:01:19,880 --> 00:01:23,070
Vkladanie môže začať
inklinovať k theta z 1.

31
00:01:23,070 --> 00:01:26,207
Theta sme sa naozaj diskutuje,
ale theta je len priemerný prípad,

32
00:01:26,207 --> 00:01:27,540
čo sa vlastne bude diať.

33
00:01:27,540 --> 00:01:29,680
Nie ste vždycky
majú najhorší možný scenár,

34
00:01:29,680 --> 00:01:32,555
a vy nie vždy bude mať
najlepší scenár, takže to, čo je

35
00:01:32,555 --> 00:01:33,900
priemerný scenár?

36
00:01:33,900 --> 00:01:36,500
>> No priemerná vloženie
do hash tabuľky

37
00:01:36,500 --> 00:01:39,370
Môžete začať sa dostať blízko k konštantnom čase.

38
00:01:39,370 --> 00:01:41,570
A mazanie môže dostať
blízko k konštantnom čase.

39
00:01:41,570 --> 00:01:44,440
A vyhľadávanie môže dostať
blízko k konštantnom čase.

40
00:01:44,440 --> 00:01:48,600
That's-- nemáme dáta:
štruktúra napriek tomu, že môže robiť to,

41
00:01:48,600 --> 00:01:51,180
a tak to už znie
ako celkom veľkú vec.

42
00:01:51,180 --> 00:01:57,010
My sme naozaj mierni
nevýhody každého z nich na jeho vlastné.

43
00:01:57,010 --> 00:01:59,160
>> Ak chcete získať toto predstavenie
upgradovať aj keď sme

44
00:01:59,160 --> 00:02:03,580
je potrebné premyslieť, ako pridáme
dát do konštrukcie.

45
00:02:03,580 --> 00:02:07,380
Konkrétne chceme,
Dáta sama o sebe, aby nám povedali

46
00:02:07,380 --> 00:02:09,725
ak by malo ísť v štruktúre.

47
00:02:09,725 --> 00:02:12,850
A keď sme potom je potrebné zistiť, či je to vo
štruktúra, ak budeme potrebovať, aby ju nájsť,

48
00:02:12,850 --> 00:02:16,610
Chceme sa pozrieť na dáta,
Znovu a musí byť schopný efektívne,

49
00:02:16,610 --> 00:02:18,910
použitia dát, náhodne prístup.

50
00:02:18,910 --> 00:02:20,700
Len tým, že pri pohľade na
Údaje by sme mali mať

51
00:02:20,700 --> 00:02:25,890
nápad, kde presne sme
bude nájsť v tabuľke hash.

52
00:02:25,890 --> 00:02:28,770
>> Teraz Nevýhodou hash
Tabuľka je, že sú naozaj

53
00:02:28,770 --> 00:02:31,770
dosť zlé na objednávke alebo pri radení dát.

54
00:02:31,770 --> 00:02:34,970
A v skutočnosti, keď začnete
použiť im nariadiť alebo triedenie

55
00:02:34,970 --> 00:02:37,990
Dáta stratíte všetky
Výhody, ktoré ste predtým

56
00:02:37,990 --> 00:02:40,710
mal, pokiaľ ide o vkladanie a mazanie.

57
00:02:40,710 --> 00:02:44,060
Čas sa stáva bližšie
theta n, a my sme v podstate

58
00:02:44,060 --> 00:02:45,530
ustúpila do prepojeného zoznamu.

59
00:02:45,530 --> 00:02:48,850
A tak sme sa len chcete použiť hash
stoly, keby sme sa nestarajú o

60
00:02:48,850 --> 00:02:51,490
či sa dáta budú zoradené.

61
00:02:51,490 --> 00:02:54,290
Pre kontextu, v ktorom
budete používať ich v CS50

62
00:02:54,290 --> 00:02:58,900
pravdepodobne nezaujíma
že dáta sú radené.

63
00:02:58,900 --> 00:03:03,170
>> Takže hash tabuľka je kombináciou
z dvoch odlišných kusov

64
00:03:03,170 --> 00:03:04,980
s ktorými sme oboznámení.

65
00:03:04,980 --> 00:03:07,930
Prvým z nich je funkcia, ktorá
zvyčajne nazývame hash funkcie.

66
00:03:07,930 --> 00:03:11,760
A to hash funkcie sa chystá
vrátiť nejaké nezáporné celé číslo, ktoré

67
00:03:11,760 --> 00:03:14,870
zvyčajne zavolať hodnotu hash, OK?

68
00:03:14,870 --> 00:03:20,230
Druhá časť je pole, čo je
schopný ukladanie dát typu my

69
00:03:20,230 --> 00:03:22,190
umiestniť do dátovej štruktúry.

70
00:03:22,190 --> 00:03:24,310
Budeme odložiť na
spájať zoznam prvku teraz

71
00:03:24,310 --> 00:03:27,810
a len začať so základmi
hash tabuľky, aby si hlavu okolo neho,

72
00:03:27,810 --> 00:03:30,210
a potom budeme možno fúkať
vaša myseľ trochu, keď sme

73
00:03:30,210 --> 00:03:32,920
kombinujú poľa a prepojenie zoznamov dohromady.

74
00:03:32,920 --> 00:03:35,590
>> Základná myšlienka hoci
je berieme niektoré dáta.

75
00:03:35,590 --> 00:03:37,860
Prevádzkujeme dáta prostredníctvom
funkcie hash.

76
00:03:37,860 --> 00:03:41,980
A tak sa dáta spracované
a to vypľuje číslo, OK?

77
00:03:41,980 --> 00:03:44,890
A potom sa s týmto číslom
my len ukladanie dát

78
00:03:44,890 --> 00:03:48,930
chceme uložiť do
Poľa na tomto mieste.

79
00:03:48,930 --> 00:03:53,990
Tak napríklad máme možná
Tento hash tabuľky reťazcov.

80
00:03:53,990 --> 00:03:57,350
Je tu 10 prvkov v ňom, tak
môžeme vojde 10 reťazca v ňom.

81
00:03:57,350 --> 00:03:59,320
>> Povedzme, že chceme, aby hash Johna.

82
00:03:59,320 --> 00:04:02,979
Tak ako Ján dát chceme vložiť
Do tejto tabuľky hash niekde.

83
00:04:02,979 --> 00:04:03,770
Kam dať?

84
00:04:03,770 --> 00:04:05,728
No typicky S
array zatiaľ sme asi

85
00:04:05,728 --> 00:04:07,610
by sa dať do lokalite poľa 0.

86
00:04:07,610 --> 00:04:09,960
Ale teraz máme túto novú funkciu hash.

87
00:04:09,960 --> 00:04:13,180
>> A povedzme, že bežíme Johna
Pomocou tejto funkcie hash

88
00:04:13,180 --> 00:04:15,417
a to vypľuje 4.

89
00:04:15,417 --> 00:04:17,500
No, to je miesto, kde sme
bude chcieť dať Johna.

90
00:04:17,500 --> 00:04:22,050
Chceme dať Johnovi v mieste poľa
4, pretože ak by sme hash Johna again--

91
00:04:22,050 --> 00:04:23,810
povedzme, že neskôr sme
chcete vyhľadať a zobraziť

92
00:04:23,810 --> 00:04:26,960
ak John existuje v tomto hash
table-- všetko, čo potrebujete urobiť,

93
00:04:26,960 --> 00:04:30,310
je prevádzkovaný cez rovnaké hash
funkcie, dostanete číslo 4 out,

94
00:04:30,310 --> 00:04:33,929
a musí byť schopný nájsť John
ihneď v našej dátovej štruktúre.

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

96
00:04:34,720 --> 00:04:36,928
>> Povedzme, že teraz to urobiť
Znovu chceme hash Paul.

97
00:04:36,928 --> 00:04:39,446
Chceme pridať Paul
Do tejto tabuľky hash.

98
00:04:39,446 --> 00:04:42,070
Povedzme, že sme tentoraz spustenie
Paul pomocou funkcie hash,

99
00:04:42,070 --> 00:04:44,600
hashCode, ktorý je generovaný je 6.

100
00:04:44,600 --> 00:04:47,340
No teraz môžeme dať Paul
v mieste poľa 6.

101
00:04:47,340 --> 00:04:50,040
A ak budeme musieť pozrieť do či
Paul je v tejto tabuľke hash,

102
00:04:50,040 --> 00:04:53,900
všetko, čo potrebujeme urobiť, je spustiť Paul
pomocou hash funkcie znova

103
00:04:53,900 --> 00:04:55,830
a budeme sa dostať 6 zase von.

104
00:04:55,830 --> 00:04:57,590
>> A potom sme sa len pozrieť
v mieste poľa 6.

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

106
00:04:58,910 --> 00:05:00,160
Ak áno, je to v tabuľke hash.

107
00:05:00,160 --> 00:05:01,875
Nie je Paul nie?

108
00:05:01,875 --> 00:05:03,000
On nie je v tabuľke hash.

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

110
00:05:05,720 --> 00:05:07,770
>> Teraz, ako si definovať hash funkcie?

111
00:05:07,770 --> 00:05:11,460
No tam je naozaj žiadny limit na
počet možných funkcií hash.

112
00:05:11,460 --> 00:05:14,350
V skutočnosti existuje celý rad naozaj,
Naozaj dobrí na internete.

113
00:05:14,350 --> 00:05:17,560
K dispozícii je celý rad naozaj,
Naozaj zlé tie na internete.

114
00:05:17,560 --> 00:05:21,080
Je to tiež celkom jednoduché
napísať zlý jeden.

115
00:05:21,080 --> 00:05:23,760
>> Takže to, čo tvorí dobrý
hash funkcie, že jo?

116
00:05:23,760 --> 00:05:27,280
No dobrá hashovacie funkcie by
použiť iba sa Hashed dáta,

117
00:05:27,280 --> 00:05:29,420
a všetky dáta sú hash.

118
00:05:29,420 --> 00:05:32,500
Takže nechceme používať anything--
nemáme nič začleniť

119
00:05:32,500 --> 00:05:35,560
iný ako dáta.

120
00:05:35,560 --> 00:05:37,080
A chceme používať všetky dáta.

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

122
00:05:39,830 --> 00:05:41,710
Funkcia hash by mal
byť tiež deterministické.

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

124
00:05:42,550 --> 00:05:46,200
No to znamená, že zakaždým, keď
prejsť presne rovnaký kus dát

125
00:05:46,200 --> 00:05:50,040
do funkcie hash vždy
získať rovnaký hodnotu hash von.

126
00:05:50,040 --> 00:05:52,870
Keby som prejsť Johna do
hash funkcie sa dostanem von 4.

127
00:05:52,870 --> 00:05:56,110
Mal by som byť schopný to urobiť 10.000
časy a ja budem vždy 4.

128
00:05:56,110 --> 00:06:00,810
Takže žiadne náhodné čísla účinne
sa môžu zapojiť do našej hash tables--

129
00:06:00,810 --> 00:06:02,750
v našich hašovacej funkciách.

130
00:06:02,750 --> 00:06:05,750
>> Funkcia hash by tiež
rovnomerne distribúciu dát.

131
00:06:05,750 --> 00:06:09,700
Ak by každý spusteniu údajov prostredníctvom
hash funkcie dostanete hodnotu hash 0,

132
00:06:09,700 --> 00:06:11,200
že to asi nie je tak veľký, že jo?

133
00:06:11,200 --> 00:06:14,600
Pravdepodobne budete chcieť, aby veľký
rad hash kódov.

134
00:06:14,600 --> 00:06:17,190
Tiež veci môžu byť rozložené
v priebehu celého stola.

135
00:06:17,190 --> 00:06:23,210
A tiež, že by bolo skvelé, keby naozaj
podobné údaje, ako sú John a Jonathan,

136
00:06:23,210 --> 00:06:26,320
Možno boli rozprestreté vážiť
rôzne umiestnenia v tabuľke hash.

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

138
00:06:28,750 --> 00:06:31,250
>> Tu je príklad funkcie hash.

139
00:06:31,250 --> 00:06:33,150
Napísal som tento privstať.

140
00:06:33,150 --> 00:06:35,047
Nie je to zvlášť
dobrá funkcia hash

141
00:06:35,047 --> 00:06:37,380
z dôvodov, ktoré nemajú v skutočnosti
medveď ísť do teraz.

142
00:06:37,380 --> 00:06:41,040
Ale vidíte, čo sa tu deje?

143
00:06:41,040 --> 00:06:44,420
Vyzerá to, že sme deklarovaní premennej
volal súčet a nastavenie presne 0.

144
00:06:44,420 --> 00:06:50,010
A potom vraj robím niečo
tak dlho, ako strstr [j] nerovná

145
00:06:50,010 --> 00:06:52,490
na spätné lomítka 0.

146
00:06:52,490 --> 00:06:54,870
Čo ja som tam robil?

147
00:06:54,870 --> 00:06:57,440
>> To je v podstate len ďalší
spôsob vykonávania [? strl?]

148
00:06:57,440 --> 00:06:59,773
a detekciu, keď som
dostal na koniec reťazca.

149
00:06:59,773 --> 00:07:02,480
Takže nemám skutočne
vypočítať dĺžku reťazca,

150
00:07:02,480 --> 00:07:05,640
Ja som len pomocou, keď som hit
spätné lomítko 0 postava viem

151
00:07:05,640 --> 00:07:07,185
Ja som došiel na koniec reťazca.

152
00:07:07,185 --> 00:07:09,560
A potom budem držať
iterácie tohto reťazca,

153
00:07:09,560 --> 00:07:15,310
pridávanie strstr [j] sčítať, a potom na
konci dňa vracať čiastky mod

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

155
00:07:16,200 --> 00:07:18,700
>> V podstate všetko hash
Funkcia je robí, je sčítanie

156
00:07:18,700 --> 00:07:23,450
všetky hodnoty ASCII
môj reťazec, a potom je to

157
00:07:23,450 --> 00:07:26,390
návratu hodnotu hash
modded by HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Je to asi o veľkosti
moje pole, nie?

159
00:07:29,790 --> 00:07:33,160
Nechcem sa dostať hash
kódy, ak sú moje pole je veľkosti 10,

160
00:07:33,160 --> 00:07:35,712
Nechcem byť získanie
out hash kódy 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, nemôžem dať veci do
Tieto miesta z poľa,

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

163
00:07:39,790 --> 00:07:42,130
Ja by som trpieť chybu segmentácie.

164
00:07:42,130 --> 00:07:45,230
>> Teraz je tu ďalší rýchly stranou.

165
00:07:45,230 --> 00:07:48,470
Všeobecne budete pravdepodobne nebude
Chcete napísať vlastnú hash funkcie.

166
00:07:48,470 --> 00:07:50,997
Je to vlastne trochu
umenia, nie je veda.

167
00:07:50,997 --> 00:07:52,580
A je tu veľa, že ide do nich.

168
00:07:52,580 --> 00:07:55,288
Internet, ako som povedal, je plný
naozaj dobrých hašovacej funkcií,

169
00:07:55,288 --> 00:07:58,470
a vy by ste mali používať internet na
nájsť hash funkcie, pretože je to naozaj

170
00:07:58,470 --> 00:08:03,230
len tak zbytočným
strata času vytvoriť si vlastný.

171
00:08:03,230 --> 00:08:05,490
>> Môžete napísať tie jednoduché
na účely testovania.

172
00:08:05,490 --> 00:08:08,323
Ale keď ste vlastne sa chystáte
spustiť zatrieďovanie dáta a ukladá ich

173
00:08:08,323 --> 00:08:10,780
do hash tabuľky, ktorú ste
pravdepodobne bude chcieť

174
00:08:10,780 --> 00:08:14,580
použiť nejakú funkciu, ktorá bola generovaná
pre teba, ktorý existuje na internete.

175
00:08:14,580 --> 00:08:17,240
Ak si proste byť istí,
citovať svoje zdroje.

176
00:08:17,240 --> 00:08:21,740
Neexistuje žiadny dôvod, aby
napodobniť niečo tu.

177
00:08:21,740 --> 00:08:25,370
>> Počítač vedy komunita je
rozhodne rastie, a naozaj hodnoty

178
00:08:25,370 --> 00:08:28,796
open source, a je to naozaj dôležité,
citovať svoje zdroje tak, aby ľudia

179
00:08:28,796 --> 00:08:30,670
môžu získať autorstvo
dielo, ktoré sú

180
00:08:30,670 --> 00:08:32,312
robí v prospech komunity.

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

182
00:08:34,020 --> 00:08:37,270
funkcie, ale všeobecne, keď vás
použiť kód z vonkajšieho zdroja,

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

184
00:08:38,299 --> 00:08:43,500
Dať úver na osoby, ktorá ju
niektoré práce, takže si nemusíte.

185
00:08:43,500 --> 00:08:46,720
>> OK, takže poďme to znova
hash tabuľky na sekundu.

186
00:08:46,720 --> 00:08:48,780
To je miesto, kde sme opustili
off potom, čo sme vkladajú

187
00:08:48,780 --> 00:08:53,300
John a Paul do tohto hash tabuľky.

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 vidieť dva.

190
00:08:58,410 --> 00:09:02,240
Ale najmä, že nie
pozri tento možný problém?

191
00:09:02,240 --> 00:09:06,770
>> Čo keď hash Ringo, a to
Ukazuje sa, že po spracovaní

192
00:09:06,770 --> 00:09:14,000
že údaje prostredníctvom funkcie hash
Ringo tiež generované na hodnotu hash 6.

193
00:09:14,000 --> 00:09:16,810
Už mám dáta
hashcode-- umiestnenie poľa 6.

194
00:09:16,810 --> 00:09:22,000
Takže to asi bude trochu
problému teraz pre mňa, že jo?

195
00:09:22,000 --> 00:09:23,060
>> Hovoríme tomu kolízie.

196
00:09:23,060 --> 00:09:26,460
A dochádza ku kolízii, keď dvaja
objemy dát, prechádzajú rovnakým dátovým

197
00:09:26,460 --> 00:09:29,200
funkcie dávajú rovnakú hodnotu hash.

198
00:09:29,200 --> 00:09:32,850
Pravdepodobne stále chceme získať oba
kusy dát do tabuľky hash,

199
00:09:32,850 --> 00:09:36,330
inak by sme byť spustený Ringo
ľubovoľne pomocou hash funkcie.

200
00:09:36,330 --> 00:09:40,870
Pravdepodobne Chceme sa dostať
Ringo do tohto poľa.

201
00:09:40,870 --> 00:09:46,070
>> Ako to robíme aj keď, keby sa
a Paul obaja výnos hashCode 6?

202
00:09:46,070 --> 00:09:49,520
Nechceme, aby prepísať Paula,
Chceme Paul, aby sa tam taky.

203
00:09:49,520 --> 00:09:52,790
Preto musíme nájsť spôsob, ako dostať
prvky do tabuľky hash, ktorý

204
00:09:52,790 --> 00:09:56,550
stále zachováva rýchlom
vkladanie a rýchly pohľad hore.

205
00:09:56,550 --> 00:10:01,350
A jeden spôsob, ako sa s tým vysporiadať, je
robiť niečo, čo nazýva lineárny sondovania.

206
00:10:01,350 --> 00:10:04,170
>> Pomocou tejto metódy, ak máme
kolízie, no, čo budeme robiť?

207
00:10:04,170 --> 00:10:08,580
No nemôžeme ho v mieste poľa
6, alebo čokoľvek hashCode bol vytvorený,

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

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

210
00:10:13,670 --> 00:10:17,420
Výhodou tejto bytosti, ak je to
Nie je presne tam, kde si myslíme, že je,

211
00:10:17,420 --> 00:10:20,850
a my musíme začať hľadať,
Možno nemusíme ísť príliš ďaleko.

212
00:10:20,850 --> 00:10:23,900
Možno, že nemáme hľadať
všetky n prvky tabuľky hash.

213
00:10:23,900 --> 00:10:25,790
Možno, že budeme musieť hľadať
niekoľko z nich.

214
00:10:25,790 --> 00:10:30,680
>> A tak sme stále vedú k
že priemerný prípad je blízko k 1 vs

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

216
00:10:34,280 --> 00:10:38,010
Takže poďme sa pozrieť, ako to
by mohlo fungovať v praxi.

217
00:10:38,010 --> 00:10:41,460
A uvidíme, či by sme možno dokáže detekovať
problém, že tu môže dôjsť.

218
00:10:41,460 --> 00:10:42,540
>> Povedzme, že sme Hashovať Barta.

219
00:10:42,540 --> 00:10:45,581
Takže teraz budeme prevádzkovať nový súbor
reťazcov cez hash funkcie,

220
00:10:45,581 --> 00:10:48,460
a my beh Barta cez hash
funkcie, dostaneme hodnotu hash 6.

221
00:10:48,460 --> 00:10:52,100
Sme sa pozrieť, vidíme, 6
prázdne, takže môžeme dať tam Barta.

222
00:10:52,100 --> 00:10:55,410
>> Teraz sme hash Lisu a že
tiež generuje hodnotu hash 6.

223
00:10:55,410 --> 00:10:58,330
Tak teraz, keď sme pomocou tohto
lineárne sondovania metódu 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 dať 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
Poďme až 7.

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

229
00:11:04,610 --> 00:11:06,510
Takže poďme dať Lisa tam.

230
00:11:06,510 --> 00:11:10,200
>> Teraz sme hash Homera a dostaneme 7.

231
00:11:10,200 --> 00:11:13,380
OK dobre vieme, že 7 je plný
Teraz, takže nemôžeme dať tam Homer.

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

233
00:11:14,850 --> 00:11:15,664
Je k dispozícii 8?

234
00:11:15,664 --> 00:11:18,330
Jo, v blízkosti 8 k 7, takže ak
musíme začať hľadať sme

235
00:11:18,330 --> 00:11:20,020
nebude musieť ísť príliš ďaleko.

236
00:11:20,020 --> 00:11:22,860
A tak sa poďme dať Homerovi v 8.

237
00:11:22,860 --> 00:11:25,151
>> Teraz sme hash Maggie a
3 sa vracia, vďaka bohu

238
00:11:25,151 --> 00:11:26,650
sme schopní len dať Maggie tam.

239
00:11:26,650 --> 00:11:29,070
Nemusíme robiť akýkoľvek
druh sondovania za to.

240
00:11:29,070 --> 00:11:32,000
Teraz sme hash Marge, a
Marge tiež vracia 6.

241
00:11:32,000 --> 00:11:39,560
>> No 6 je plná, 7 je plná, 8 je plná,
9, v poriadku vďaka Bohu, 9 je prázdny.

242
00:11:39,560 --> 00:11:41,600
Môžem dať Marge na 9.

243
00:11:41,600 --> 00:11:45,280
Už môžeme vidieť, že my teraz začíname
aby tento problém, kde teraz sme

244
00:11:45,280 --> 00:11:48,780
začína natiahnuť veci druh
ďaleko od svojich hash kódy.

245
00:11:48,780 --> 00:11:52,960
A to theta 1, že priemerný
Prípad je konštantný čas,

246
00:11:52,960 --> 00:11:56,560
začína byť trochu more--
začína o niečo väčšiu tendenciu

247
00:11:56,560 --> 00:11:58,050
smerom k theta n.

248
00:11:58,050 --> 00:12:01,270
Začíname strácať, že
Výhodou stoly mriežky.

249
00:12:01,270 --> 00:12:03,902
>> Tento problém, ktorý sme práve videli
je niečo, čo nazýva zhlukovaniu.

250
00:12:03,902 --> 00:12:06,360
A čo je naozaj zlé na tom,
clustering je, že akonáhle vás teraz

251
00:12:06,360 --> 00:12:09,606
majú dva prvky, ktoré sú vedľa
stranu to robí to ešte pravdepodobnejšie,

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

253
00:12:11,480 --> 00:12:13,516
mať ďalšie kolízie
klastra s tým,

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

255
00:12:14,890 --> 00:12:19,640
A budete neustále rastú a rastie
Váš pravdepodobnosť mať kolízii.

256
00:12:19,640 --> 00:12:24,470
A nakoniec je to rovnako zlé
tak, že triedenie dát vôbec.

257
00:12:24,470 --> 00:12:27,590
>> Ďalším problémom však je, že sme
stále, a tak ďaleko, až do tohto bodu,

258
00:12:27,590 --> 00:12:30,336
práve sme boli tak nejako
pochopenie toho, čo hash tabuľka je,

259
00:12:30,336 --> 00:12:31,960
máme stále len priestor pre 10 reťazcov.

260
00:12:31,960 --> 00:12:37,030
Ak chceme, aby aj naďalej hash
občania Springfieldu,

261
00:12:37,030 --> 00:12:38,790
môžeme len získať 10 z nich tam.

262
00:12:38,790 --> 00:12:42,619
A keď sa budeme snažiť a pridajte 11. alebo 12.,
nemáme miesto, aby ich dal.

263
00:12:42,619 --> 00:12:45,660
Mohli by sme sa točí okolo
kruhy sa snažia nájsť prázdne miesto,

264
00:12:45,660 --> 00:12:49,000
a my sme možno uviaznu
v nekonečnej slučke.

265
00:12:49,000 --> 00:12:51,810
>> Takže tento druh požičiava myšlienku
niečo volal reťazenie.

266
00:12:51,810 --> 00:12:55,790
A to je miesto, kde budeme prinášať
spojové zoznamy späť do obrazu.

267
00:12:55,790 --> 00:13:01,300
Čo keď miesto uloženia práve
samotné dáta v poli,

268
00:13:01,300 --> 00:13:04,471
každý prvok matice mohla
držať viac častí dát?

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

270
00:13:05,970 --> 00:13:09,280
Vieme len to, že pole môže
hold-- každého prvku poľa

271
00:13:09,280 --> 00:13:12,930
môže mať iba jeden kus
údajov tohto typu dát.

272
00:13:12,930 --> 00:13:16,750
>> Ale čo keď ten typ dát
je prepojený zoznam, nie?

273
00:13:16,750 --> 00:13:19,830
Takže čo keby každý
prvok poľa bola

274
00:13:19,830 --> 00:13:22,790
ukazovateľ na hlave prepojeného zozname?

275
00:13:22,790 --> 00:13:24,680
A potom by sme mohli stavať
tie spojové zoznamy

276
00:13:24,680 --> 00:13:27,120
a rast je ľubovoľne,
preto, že spojové zoznamy umožňujú

277
00:13:27,120 --> 00:13:32,090
náš rast a zmenšiť oveľa viac
pružnejšie než pole robí.

278
00:13:32,090 --> 00:13:34,210
A čo keď budeme teraz používať,
sme využiť to, že jo?

279
00:13:34,210 --> 00:13:37,760
Máme začať pestovať tieto reťaze
z týchto miest poľa.

280
00:13:37,760 --> 00:13:40,740
>> Teraz sme sa zmestí nekonečným
množstvo dát, alebo nie je nekonečná,

281
00:13:40,740 --> 00:13:44,170
ľubovoľná čiastka
Údaje, do nášho hash tabuľky

282
00:13:44,170 --> 00:13:47,760
bez toho aby sa beh do
problém kolízie.

283
00:13:47,760 --> 00:13:50,740
Tiež sme eliminovať
zhlukovaniu tým, že robí to.

284
00:13:50,740 --> 00:13:54,380
A dobre vieme, že keď sme sa vložiť
do prepojeného zoznamu, ak si spomínate

285
00:13:54,380 --> 00:13:57,779
z nášho videa na previazané zoznamy, jednotlivo
prepojené zoznamy a dvojnásobne spojové zoznamy,

286
00:13:57,779 --> 00:13:59,070
je to neustály doba prevádzky.

287
00:13:59,070 --> 00:14:00,710
Sme len pridať na front.

288
00:14:00,710 --> 00:14:04,400
>> A Look Up, dobre vieme,
ktoré vyzerajú v prepojenom zozname

289
00:14:04,400 --> 00:14:05,785
môže byť problém, že jo?

290
00:14:05,785 --> 00:14:07,910
Musíme prehľadávať
je od začiatku až do konca.

291
00:14:07,910 --> 00:14:10,460
Nie je náhodné
pripojenie k internetu v Google zoznamu.

292
00:14:10,460 --> 00:14:15,610
Avšak v prípade, namiesto toho, aby sa jeden z prepojených
Zoznam kde by vyhľadávania byť O n,

293
00:14:15,610 --> 00:14:19,590
teraz máme 10 previazané zoznamy,
alebo 1000 prepojené zoznamy,

294
00:14:19,590 --> 00:14:24,120
teraz je to ó n delené 10,
alebo O n delené 1,000.

295
00:14:24,120 --> 00:14:26,940
>> A keď sme hovorili
teoreticky o zložitosti

296
00:14:26,940 --> 00:14:30,061
Opomenieme konštanty, v skutočný
svet tieto veci skutočne záleží,

297
00:14:30,061 --> 00:14:30,560
v poriadku?

298
00:14:30,560 --> 00:14:33,080
Vlastne sme si všimnete
, Že sa to stane

299
00:14:33,080 --> 00:14:36,610
bežať 10 krát rýchlejšie,
alebo 1000 krát rýchlejší,

300
00:14:36,610 --> 00:14:41,570
preto, že sme rozdelenie jednej dlhej
reťaz cez 1000 menších reťazcoch.

301
00:14:41,570 --> 00:14:45,090
A tak zakaždým, keď sa musíme hľadať
prostredníctvom jedného z týchto reťazcov je v našich silách

302
00:14:45,090 --> 00:14:50,290
ignorovať 999 reťazcov nás nezaujíma
o, a len hľadať, že jeden.

303
00:14:50,290 --> 00:14:53,220
>> Čo je v priemere
byť 1000x kratšie.

304
00:14:53,220 --> 00:14:56,460
A tak sme stále sú tak nejako
smerujúce k tomuto priemerný prípad

305
00:14:56,460 --> 00:15:01,610
z toho, že konštantnom čase, ale
len preto, že sme sa pákového efektu

306
00:15:01,610 --> 00:15:03,730
delenie nejakým veľkým konštantným faktorom.

307
00:15:03,730 --> 00:15:05,804
Pozrime sa, ako by to mohlo
v skutočnosti vyzerajú hoci.

308
00:15:05,804 --> 00:15:08,720
Tak toto bola tabuľka hash sme mali
Ako sme deklarovali hash tabuľku, ktorá

309
00:15:08,720 --> 00:15:10,270
bol schopný ukladať 10 reťazcov.

310
00:15:10,270 --> 00:15:11,728
Nebudeme robiť, že už nie.

311
00:15:11,728 --> 00:15:13,880
My už vieme, že
Obmedzenie tejto metódy.

312
00:15:13,880 --> 00:15:20,170
Teraz náš hash tabuľky to bude
rad 10 uzlov, ukazovatele

313
00:15:20,170 --> 00:15:22,120
vedúcim spojových zoznamov.

314
00:15:22,120 --> 00:15:23,830
>> A práve teraz je to null.

315
00:15:23,830 --> 00:15:26,170
Každý z tých 10 ukazovateľov je null.

316
00:15:26,170 --> 00:15:29,870
Na tom nie je nič v Our
hash tabuľky práve teraz.

317
00:15:29,870 --> 00:15:32,690
>> Teraz poďme začať, aby niektoré
veci do tohto hash tabuľky.

318
00:15:32,690 --> 00:15:35,440
A pozrime sa, ako je táto metóda
bude nám prospech trochu.

319
00:15:35,440 --> 00:15:36,760
Poďme sa teraz Hashovať Joey.

320
00:15:36,760 --> 00:15:40,210
Budeme sa spustí reťazec Joey prostredníctvom
funkcie hash a vraciame sa 6.

321
00:15:40,210 --> 00:15:41,200
Tak čo budeme robiť teraz?

322
00:15:41,200 --> 00:15:44,090
>> Tak teraz pracuje s prepojenými zoznamy,
nie sme prácu s poľami.

323
00:15:44,090 --> 00:15:45,881
A keď pracujeme
s prepojenými zoznamy my

324
00:15:45,881 --> 00:15:49,790
viete, musíme začať dynamicky
prideľovanie priestoru a stavebné reťaze.

325
00:15:49,790 --> 00:15:54,020
To je druh how-- tie sú jadrom
prvky budovania prepojeného zoznamu.

326
00:15:54,020 --> 00:15:57,670
Takže poďme dynamicky
prideliť priestor pre Joey,

327
00:15:57,670 --> 00:16:00,390
a potom dodajme ho reťaze.

328
00:16:00,390 --> 00:16:03,170
>> Takže teraz sa pozrite, čo sme urobili.

329
00:16:03,170 --> 00:16:06,440
Keď sme hash Joey sme dostali hodnotu hash 6.

330
00:16:06,440 --> 00:16:11,790
Teraz je ukazovateľ v mieste poľa 6
poukazuje na čele zoznamu Google,

331
00:16:11,790 --> 00:16:14,900
a teraz je to jediná
prvok prepojeného zoznamu.

332
00:16:14,900 --> 00:16:18,350
A uzol sa tým, že
spájať zoznam je Joey.

333
00:16:18,350 --> 00:16:22,300
>> Takže ak budeme musieť pozrieť do Joey
neskôr, práve sme hash Joey znova,

334
00:16:22,300 --> 00:16:26,300
dostaneme 6 znova, pretože naša
hash funkcia je deterministický.

335
00:16:26,300 --> 00:16:30,400
A potom začneme v čele
prepojeného zoznamu poukázal

336
00:16:30,400 --> 00:16:33,360
sa podľa umiestnenia poľa
6, a môžeme iterácii

337
00:16:33,360 --> 00:16:35,650
cez ktorý sa snaží nájsť Joey.

338
00:16:35,650 --> 00:16:37,780
A ak budeme budovať našu
účinne hash tabuľky,

339
00:16:37,780 --> 00:16:41,790
a naše hash funkcie efektívne
distribuovať dát dobre,

340
00:16:41,790 --> 00:16:45,770
v priemere každá z tých, ktoré súvisia
zoznamy na každom mieste pole

341
00:16:45,770 --> 00:16:50,110
bude 1/10 veľkosť keby sme
jednoducho musel to ako jeden obrovský

342
00:16:50,110 --> 00:16:51,650
spájať zoznam so všetkým, čo v ňom.

343
00:16:51,650 --> 00:16:55,670
>> Ak budeme distribuovať, že obrovské spojené
Zoznam cez 10 spojových zoznamov

344
00:16:55,670 --> 00:16:57,760
každý zoznam bude desatín veľkosť.

345
00:16:57,760 --> 00:17:01,432
A teda 10 krát rýchlejší
prehľadávať.

346
00:17:01,432 --> 00:17:02,390
Takže poďme to urobiť znova.

347
00:17:02,390 --> 00:17:04,290
Poďme sa teraz Hashovať Ross.

348
00:17:04,290 --> 00:17:07,540
>> A povedzme, že Ross, keď budeme robiť, že
hash kód sa vrátime je 2.

349
00:17:07,540 --> 00:17:10,630
Tak teraz sme dynamicky prideliť
nový uzol, dáme Ross v tomto uzle,

350
00:17:10,630 --> 00:17:14,900
a hovoríme, teraz umiestnenie array
2, namiesto toho, smerujúce na null,

351
00:17:14,900 --> 00:17:18,579
poukazuje na hlavu spojené
Zoznam ktorých jediným uzol je Ross.

352
00:17:18,579 --> 00:17:22,660
A môžeme to urobiť ešte jeden čas, my
môžu hash Rachel a získať hodnotu hash 4.

353
00:17:22,660 --> 00:17:25,490
malloc nový uzol, dal Rachel v
uzol, a hovoria, umiestnenie polia

354
00:17:25,490 --> 00:17:27,839
4 teraz ukazuje na hlave
prepojeného zozname, ktorého

355
00:17:27,839 --> 00:17:31,420
Jediným prvkom sa stane byť Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, ale čo sa stane, keď
máme kolízii?

357
00:17:33,470 --> 00:17:38,560
Pozrime sa, ako nakladáme s kolízií
pomocou samostatného metódy zreťazenie.

358
00:17:38,560 --> 00:17:39,800
Poď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šom predchádzajúcom príklade sme boli len
uloženie reťazcov v poli.

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

362
00:17:45,980 --> 00:17:48,444
>> Nechceme, aby naložiť
Joey, a už sme

363
00:17:48,444 --> 00:17:51,110
vidieť, že môžeme získať nejaké clustering
problémy, ak sa snažíme krok

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

365
00:17:52,202 --> 00:17:54,660
Ale čo keď sme práve druh
zaobchádzať to rovnako, nie?

366
00:17:54,660 --> 00:17:57,440
Je to ako pridanie prvku
na hlavu prepojeného zozname.

367
00:17:57,440 --> 00:18:00,220
Poďme sa len malloc priestor pre Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Povieme ďalšie ukazovatele bodov Phoebe
na staré hlave Google zoznamu,

369
00:18:04,764 --> 00:18:07,180
a potom na 6 len poukazuje na
nový šéf Google zoznamu.

370
00:18:07,180 --> 00:18:10,150
A teraz sa pozri, že sme zmenili Phoebe v.

371
00:18:10,150 --> 00:18:14,210
Teraz môžeme uložiť dva
prvky s hashCode 6,

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

373
00:18:17,170 --> 00:18:20,147
>> To je skoro všetky
tam je reťazenie.

374
00:18:20,147 --> 00:18:21,980
A reťazenie je určite
Metóda, ktorá je

375
00:18:21,980 --> 00:18:27,390
bude najefektívnejší pre vás, ak
ste ukladanie dát do tabuľky hash.

376
00:18:27,390 --> 00:18:30,890
Ale táto kombinácia
poľa a spojové zoznamy

377
00:18:30,890 --> 00:18:36,080
spolu tvoriť hash tabuľku naozaj
výrazne zlepšuje vašu schopnosť

378
00:18:36,080 --> 00:18:40,550
pre ukladanie veľkých objemov dát, a
veľmi rýchlo a efektívne vyhľadávať

379
00:18:40,550 --> 00:18:41,630
prostredníctvom tohto dátumu.

380
00:18:41,630 --> 00:18:44,150
>> Je tu ešte jeden
štruktúra tam údaje

381
00:18:44,150 --> 00:18:48,700
to by mohlo byť aj trochu
lepšie, pokiaľ ide o zabezpečenie

382
00:18:48,700 --> 00:18:51,920
že naše vkladanie, mazanie, a
Vyhľadá časy sú ešte rýchlejšie.

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

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

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