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

2
00:00:00,500 --> 00:00:01,900
[Muzika]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG Lloyd: Deri tani ju
dinë shumë rreth vargjeve,

5
00:00:09,150 --> 00:00:11,610
dhe ju e dini shumë për listat e lidhura.

6
00:00:11,610 --> 00:00:13,650
Dhe ne kemi diskutuar
pro dhe kundra, ne kemi

7
00:00:13,650 --> 00:00:16,620
diskutuar se lidhur listat
mund të merrni më të mëdha dhe të vogla,

8
00:00:16,620 --> 00:00:18,630
por ata kërkojnë më shumë madhësinë.

9
00:00:18,630 --> 00:00:22,359
Vargjeve janë shumë më të hapur për të
përdorin, por ata janë të kufizuar në sa më shumë

10
00:00:22,359 --> 00:00:24,900
si ne kemi për të vendosur madhësinë e
array në fillim

11
00:00:24,900 --> 00:00:26,910
dhe pastaj ne jemi të mbërthyer me të.

12
00:00:26,910 --> 00:00:30,470
>> Por kjo është, ne kemi shumë e shumë
shteruar të gjitha temat tona

13
00:00:30,470 --> 00:00:33,040
në lidhje me listat e lidhura dhe vargjeve.

14
00:00:33,040 --> 00:00:34,950
Apo kemi?

15
00:00:34,950 --> 00:00:37,720
Ndoshta ne mund të bëjmë diçka
edhe më shumë krijues.

16
00:00:37,720 --> 00:00:40,950
Dhe kjo lloj i jep hua
ideja e një tabelë hash.

17
00:00:40,950 --> 00:00:46,680
>> Pra, në një tabelë hash ne jemi duke shkuar për të provoni
të kombinuar një grup me një listë të lidhura.

18
00:00:46,680 --> 00:00:49,520
Ne jemi duke shkuar për të marrë avantazhet
e array, si qasje të rastit,

19
00:00:49,520 --> 00:00:53,510
qenë në gjendje të thjesht shkoni në grup
element 4 ose grup element 8

20
00:00:53,510 --> 00:00:55,560
pa pasur nevojë për të iterate nëpër.

21
00:00:55,560 --> 00:00:57,260
Kjo është shumë e shpejtë, e drejtë?

22
00:00:57,260 --> 00:01:00,714
>> Por ne gjithashtu duam të kemi të dhënat tona
Struktura të jetë në gjendje të rritet dhe tkurret.

23
00:01:00,714 --> 00:01:02,630
Ne nuk kemi nevojë, ne nuk e bëjmë
duan të jenë të kufizuara.

24
00:01:02,630 --> 00:01:04,588
Dhe ne duam të jetë në gjendje
të shtoni dhe hiqni gjërat

25
00:01:04,588 --> 00:01:08,430
shumë lehtë, e cila në qoftë se ju kujtohet,
është shumë komplekse me një grup.

26
00:01:08,430 --> 00:01:11,650
Dhe ne mund ta quajmë këtë
gjë e re një tabelë hash.

27
00:01:11,650 --> 00:01:15,190
>> Dhe në qoftë se zbatohet si duhet,
ne jemi lloj i marrjes

28
00:01:15,190 --> 00:01:18,150
avantazhet e të dy të dhënave
Strukturat e keni parë tashmë,

29
00:01:18,150 --> 00:01:19,880
vargjeve dhe listat lidhura.

30
00:01:19,880 --> 00:01:23,070
Futje mund të fillojnë të
priren drejt theta e 1.

31
00:01:23,070 --> 00:01:26,207
Theta ne nuk kemi diskutuar me të vërtetë,
por theta është vetëm rasti mesatare,

32
00:01:26,207 --> 00:01:27,540
çfarë është në të vërtetë do të ndodhë.

33
00:01:27,540 --> 00:01:29,680
Ju nuk jeni gjithmonë do të
kanë skenarin më të keq,

34
00:01:29,680 --> 00:01:32,555
dhe ju nuk jeni gjithmonë do të ketë
skenari më i mirë, kështu që çfarë është

35
00:01:32,555 --> 00:01:33,900
skenari mesatar?

36
00:01:33,900 --> 00:01:36,500
>> E pra një futje mesatare
në një tabelë hash

37
00:01:36,500 --> 00:01:39,370
mund të filloni për të marrë afër në kohë të vazhdueshme.

38
00:01:39,370 --> 00:01:41,570
Dhe fshirje mund të merrni
mbyllur në kohë të vazhdueshme.

39
00:01:41,570 --> 00:01:44,440
Dhe lookup mund të merrni
mbyllur në kohë të vazhdueshme.

40
00:01:44,440 --> 00:01:48,600
That's-- ne nuk kemi një të dhënave
Struktura ende se mund ta bëjë këtë,

41
00:01:48,600 --> 00:01:51,180
dhe kështu që kjo tashmë tingëllon
si një gjë mjaft e madhe.

42
00:01:51,180 --> 00:01:57,010
Ne kemi zbutet vërtetë
disavantazhet e secilit më vete.

43
00:01:57,010 --> 00:01:59,160
>> Për të marrë këtë performancë
përmirësuar edhe pse, ne

44
00:01:59,160 --> 00:02:03,580
duhet të mendonin se si ne shtoni
të dhënat në strukturën.

45
00:02:03,580 --> 00:02:07,380
Në mënyrë të veçantë ne dëshironi
vetë të dhënat për të na tregoni

46
00:02:07,380 --> 00:02:09,725
ku ajo duhet të shkojë në strukturën.

47
00:02:09,725 --> 00:02:12,850
Dhe nëse atëherë ne kemi nevojë për të parë nëse është në
struktura, në qoftë se ne kemi nevojë për të gjetur atë,

48
00:02:12,850 --> 00:02:16,610
ne duam të shikojmë në të dhënat e
përsëri dhe të jenë në gjendje që në mënyrë efektive,

49
00:02:16,610 --> 00:02:18,910
duke përdorur të dhënat, rastësisht të hyrë në të.

50
00:02:18,910 --> 00:02:20,700
Vetëm duke shikuar në
të dhëna ne duhet të kemi

51
00:02:20,700 --> 00:02:25,890
një ide e ku pikërisht ne jemi
do të gjeni atë në tabelë hash.

52
00:02:25,890 --> 00:02:28,770
>> Tani dobësitë e një hash
tabelë është se ata janë me të vërtetë

53
00:02:28,770 --> 00:02:31,770
shumë e keqe në urdhërimin ose klasifikim të dhënave.

54
00:02:31,770 --> 00:02:34,970
Dhe në fakt, nëse ju filloni
të përdorin ato për të porositur ose lloj

55
00:02:34,970 --> 00:02:37,990
të dhëna ju humbni të gjitha të
Përparësitë ju më parë

56
00:02:37,990 --> 00:02:40,710
kishte në aspektin e futje dhe fshirje.

57
00:02:40,710 --> 00:02:44,060
Koha bëhet më afër
theta e n, dhe ne kemi në thelb

58
00:02:44,060 --> 00:02:45,530
ngecur në një listë të lidhura.

59
00:02:45,530 --> 00:02:48,850
Dhe kështu që ne vetëm dëshironi të përdorni hash
tavolina, nëse ne nuk e kujdesit në lidhje me

60
00:02:48,850 --> 00:02:51,490
nëse të dhënat është e renditura.

61
00:02:51,490 --> 00:02:54,290
Për kontekstin në të cilin
ju do të përdorin ato në CS50

62
00:02:54,290 --> 00:02:58,900
ju ndoshta nuk e kujdesit
se të dhënat është e renditura.

63
00:02:58,900 --> 00:03:03,170
>> Pra, një tabelë hash është një kombinim
nga dy pjesë të dallueshme

64
00:03:03,170 --> 00:03:04,980
me të cilat ne jemi të njohur.

65
00:03:04,980 --> 00:03:07,930
I parë është një funksion, e cila
ne zakonisht e quajmë një funksion hash.

66
00:03:07,930 --> 00:03:11,760
Dhe kjo funksion hash do të
kthehen disa numër i plotë jo-negativ, i cili

67
00:03:11,760 --> 00:03:14,870
ne zakonisht e quajmë një hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
Pjesa e dytë është një grup, i cili është
të aftë për magazinimin e të dhënave të tipit ne

69
00:03:20,230 --> 00:03:22,190
doni të vendosni në strukturën e të dhënave.

70
00:03:22,190 --> 00:03:24,310
Ne do të mbajë jashtë në anën
lidhur element listë për tani

71
00:03:24,310 --> 00:03:27,810
dhe të fillojë vetëm me bazat e një
hash tryezë për të marrë kokën tuaj rreth tij,

72
00:03:27,810 --> 00:03:30,210
dhe pastaj ne do të ndoshta goditje
mendjen tuaj pak kur ne

73
00:03:30,210 --> 00:03:32,920
kombinohen vargjeve dhe listat lidhur së bashku.

74
00:03:32,920 --> 00:03:35,590
>> Ideja themelore pse
është që ne të marrë disa të dhëna.

75
00:03:35,590 --> 00:03:37,860
Ne të drejtuar se të dhënat përmes
funksioni hash.

76
00:03:37,860 --> 00:03:41,980
Dhe kështu të dhënat janë përpunuar
dhe ajo pështyn nga një numër, në rregull?

77
00:03:41,980 --> 00:03:44,890
Dhe pastaj me atë numër
ne vetëm të ruajtur të dhënat

78
00:03:44,890 --> 00:03:48,930
ne duam të ruajtur në
array në atë vend.

79
00:03:48,930 --> 00:03:53,990
Kështu për shembull, ne kemi ndoshta
kjo tabelë hash e strings.

80
00:03:53,990 --> 00:03:57,350
Ajo ka 10 elemente në të, kështu që
ne mund të përshtatet 10 vargjet në të.

81
00:03:57,350 --> 00:03:59,320
>> Le të themi se duam të hash Gjoni.

82
00:03:59,320 --> 00:04:02,979
Pra, Gjoni si të dhëna ne duam të futur
në këtë tabelë hash diku.

83
00:04:02,979 --> 00:04:03,770
Ku nuk kemi vënë atë?

84
00:04:03,770 --> 00:04:05,728
E pra në mënyrë tipike me një
array deri tani ne ndoshta

85
00:04:05,728 --> 00:04:07,610
do të vënë atë në vend array 0.

86
00:04:07,610 --> 00:04:09,960
Por tani ne kemi këtë funksion të ri hash.

87
00:04:09,960 --> 00:04:13,180
>> Dhe le të themi se kemi drejtuar Gjoni
përmes këtij funksioni hash

88
00:04:13,180 --> 00:04:15,417
dhe kjo është pështyn nga 4.

89
00:04:15,417 --> 00:04:17,500
E pra kjo është ajo ku ne jemi
do të duan të vënë Gjoni.

90
00:04:17,500 --> 00:04:22,050
Ne duam të vënë Gjonin në vend array
4, sepse në qoftë se ne të hash Gjoni again--

91
00:04:22,050 --> 00:04:23,810
le të themi më vonë ne
doni të kërkoni dhe të shohin

92
00:04:23,810 --> 00:04:26,960
nëse John ekziston në këtë hash
table-- të gjithë ne duhet të bëjmë

93
00:04:26,960 --> 00:04:30,310
është drejtuar atë nëpërmjet të njëjtin hash
funksion, të marrë numrin 4 nga,

94
00:04:30,310 --> 00:04:33,929
dhe të jetë në gjendje për të gjetur Gjoni
menjëherë në strukturën e të dhënave tonë.

95
00:04:33,929 --> 00:04:34,720
Kjo është shumë e mirë.

96
00:04:34,720 --> 00:04:36,928
>> Le të themi se tani bëjmë këtë
përsëri, ne duam të hash Palin.

97
00:04:36,928 --> 00:04:39,446
Ne duam të shtoni Palin
në këtë tabelë hash.

98
00:04:39,446 --> 00:04:42,070
Le të themi se këtë herë kemi drejtuar
Pali përmes funksionit hash,

99
00:04:42,070 --> 00:04:44,600
hashcode që është krijuar është 6.

100
00:04:44,600 --> 00:04:47,340
E pra tani ne mund të vënë Palin
në array vend të 6.

101
00:04:47,340 --> 00:04:50,040
Dhe në qoftë se ne duhet të shohim lart nëse
Pali është në këtë tabelë hash,

102
00:04:50,040 --> 00:04:53,900
të gjithë ne duhet të bëni është të drejtuar Paul
përmes funksionit hash përsëri

103
00:04:53,900 --> 00:04:55,830
dhe ne jemi duke shkuar për të marrë 6 jashtë përsëri.

104
00:04:55,830 --> 00:04:57,590
>> Dhe atëherë ne vetëm shikoni
në array vend të 6.

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

106
00:04:58,910 --> 00:05:00,160
Nëse është kështu, ai është në tabelën hash.

107
00:05:00,160 --> 00:05:01,875
Paul nuk ka?

108
00:05:01,875 --> 00:05:03,000
Ai nuk është në tabelën hash.

109
00:05:03,000 --> 00:05:05,720
Është shumë i thjeshtë.

110
00:05:05,720 --> 00:05:07,770
>> Tani si mund të përcaktojë një funksion hash?

111
00:05:07,770 --> 00:05:11,460
E pra nuk ka të vërtetë nuk ka kufi të
Numri i funksioneve të mundshme hash.

112
00:05:11,460 --> 00:05:14,350
Në fakt ka një numër të vërtetë,
ato me të vërtetë të mira në internet.

113
00:05:14,350 --> 00:05:17,560
Ka një numër të vërtetë,
ato me të vërtetë të këqija në internet.

114
00:05:17,560 --> 00:05:21,080
Është gjithashtu shumë e lehtë
për të shkruar një të keqe.

115
00:05:21,080 --> 00:05:23,760
>> Pra, çfarë e bën një të mirë
funksion hash, e drejtë?

116
00:05:23,760 --> 00:05:27,280
Edhe një funksion të mirë hash duhet
përdorin vetëm të dhënat që janë sheshuar,

117
00:05:27,280 --> 00:05:29,420
dhe të gjitha të dhënave të sheshuar.

118
00:05:29,420 --> 00:05:32,500
Pra, ne nuk duam të përdorni anything--
ne nuk përfshijnë ndonjë gjë

119
00:05:32,500 --> 00:05:35,560
tjetër përveç të dhënave.

120
00:05:35,560 --> 00:05:37,080
Dhe ne duam të përdorim të gjitha të dhënave.

121
00:05:37,080 --> 00:05:39,830
Ne nuk duam që të përdorni vetëm një copë
e saj, ne duam të përdorim të gjithë atë.

122
00:05:39,830 --> 00:05:41,710
Një funksion hash duhet
të jetë gjithashtu determinist.

123
00:05:41,710 --> 00:05:42,550
Cfare do te thote ajo?

124
00:05:42,550 --> 00:05:46,200
E pra kjo do të thotë se çdo herë kemi
kalojë të njëjtën pjesë e saktë e të dhënave

125
00:05:46,200 --> 00:05:50,040
në funksion hash ne gjithmonë
merrni të njëjtën hashcode jashtë.

126
00:05:50,040 --> 00:05:52,870
Nëse unë kaloj Gjonin në të
funksion hash unë dal 4.

127
00:05:52,870 --> 00:05:56,110
Unë duhet të jetë në gjendje të bëjë atë 10,000
herë dhe unë gjithmonë do të merrni 4.

128
00:05:56,110 --> 00:06:00,810
Kështu që nuk ka numra të rastit në mënyrë efektive
mund të përfshihen në hash tonë tables--

129
00:06:00,810 --> 00:06:02,750
në funksionet tona të hash.

130
00:06:02,750 --> 00:06:05,750
>> Një funksion hash duhet gjithashtu
uniforme shpërndarjen e të dhënave.

131
00:06:05,750 --> 00:06:09,700
Në qoftë se çdo herë që të drejtuar të dhënat përmes
funksion hash ju merrni hashcode 0,

132
00:06:09,700 --> 00:06:11,200
kjo ndoshta nuk është aq e madhe, apo jo?

133
00:06:11,200 --> 00:06:14,600
Ju ndoshta dëshironi të mëdha
një varg i kodeve hash.

134
00:06:14,600 --> 00:06:17,190
Edhe gjërat mund të përhapet
nga të gjithë në tryezë.

135
00:06:17,190 --> 00:06:23,210
Dhe gjithashtu kjo do të jetë i madh në qoftë se me të vërtetë
të dhëna të ngjashme, si Gjoni dhe Jonathanin,

136
00:06:23,210 --> 00:06:26,320
ndoshta janë shtrirë për të peshojnë
vende të ndryshme në tabelë hash.

137
00:06:26,320 --> 00:06:28,750
Kjo do të jetë një avantazh i bukur.

138
00:06:28,750 --> 00:06:31,250
>> Ja një shembull i një funksion hash.

139
00:06:31,250 --> 00:06:33,150
Kam shkruar këtë një të tillë më herët.

140
00:06:33,150 --> 00:06:35,047
Kjo nuk është një veçanërisht i
Funksioni i mirë hash

141
00:06:35,047 --> 00:06:37,380
për arsye që nuk të vërtetë
mbajnë shkon në të drejtë tani.

142
00:06:37,380 --> 00:06:41,040
Por ju e shihni se çfarë po ndodh këtu?

143
00:06:41,040 --> 00:06:44,420
Duket sikur ne jemi duke deklaruar një ndryshore
quhet shuma e vendosur atë të barabartë me 0.

144
00:06:44,420 --> 00:06:50,010
Dhe pastaj me sa duket unë jam duke bërë diçka
për aq kohë sa strstr [j] nuk është i barabartë

145
00:06:50,010 --> 00:06:52,490
për backslash 0.

146
00:06:52,490 --> 00:06:54,870
Çfarë po bëj këtu?

147
00:06:54,870 --> 00:06:57,440
>> Kjo është në thelb vetëm një tjetër
Mënyra e zbatimit të [? strl?]

148
00:06:57,440 --> 00:06:59,773
dhe zbulimin kur ju keni
arritur në fund të vargut.

149
00:06:59,773 --> 00:07:02,480
Kështu që unë nuk duhet të vërtetë të
të llogaritur gjatësinë e vargut,

150
00:07:02,480 --> 00:07:05,640
Unë jam vetëm duke përdorur, kur unë goditi
backslash 0 karakter di

151
00:07:05,640 --> 00:07:07,185
Unë e kam arritur në fund të vargut.

152
00:07:07,185 --> 00:07:09,560
Dhe atëherë unë jam duke shkuar për të mbajtur
iterating nëpër atë varg,

153
00:07:09,560 --> 00:07:15,310
duke shtuar strstr [J] për të përmbledhur, dhe pastaj në
fundi i ditës do të kthehen shuma mod

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

155
00:07:16,200 --> 00:07:18,700
>> Në thelb të gjithë kësaj hash
Funksioni është duke bërë është duke shtuar deri

156
00:07:18,700 --> 00:07:23,450
të gjithë nga vlerat e ASCII
string im, dhe atëherë është

157
00:07:23,450 --> 00:07:26,390
kthyer disa hashcode
modded nga HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Kjo është ndoshta e madhësisë
e array tim, e drejtë?

159
00:07:29,790 --> 00:07:33,160
Unë nuk dua të jetë marrë hash
Kodet nëse array ime është e madhësisë 10,

160
00:07:33,160 --> 00:07:35,712
Unë nuk dua të jetë marrë
Kodet jashtë hash 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, unë nuk mund të vënë gjërat në
këto vende e vektorit,

162
00:07:38,690 --> 00:07:39,790
që do të jetë i paligjshëm.

163
00:07:39,790 --> 00:07:42,130
Unë do të vuajnë një defekt segmentimit.

164
00:07:42,130 --> 00:07:45,230
>> Tani këtu është një tjetër i shpejtë mënjanë.

165
00:07:45,230 --> 00:07:48,470
Në përgjithësi ju jeni ndoshta nuk do të
dua të shkruaj funksionet e veta hash tuaja.

166
00:07:48,470 --> 00:07:50,997
Kjo është në fakt një grimë
një art, jo një shkencë.

167
00:07:50,997 --> 00:07:52,580
Dhe ka shumë që shkon në to.

168
00:07:52,580 --> 00:07:55,288
Interneti, si i tha, është e plotë
i funksioneve të vërtetë të mirë hash,

169
00:07:55,288 --> 00:07:58,470
dhe ju duhet të përdorni internetin për
gjeni funksionet hash, sepse është e vërtetë

170
00:07:58,470 --> 00:08:03,230
vetëm lloj i një të panevojshme
humbje e kohës për të krijuar tuaj.

171
00:08:03,230 --> 00:08:05,490
>> Ju mund të shkruani ato të thjeshta
për qëllime testimi.

172
00:08:05,490 --> 00:08:08,323
Por kur ju të vërtetë do të
të fillojë hashing të dhënave dhe ruajtjen atë

173
00:08:08,323 --> 00:08:10,780
në një tabelë hash ju jeni
ndoshta do të doni

174
00:08:10,780 --> 00:08:14,580
të përdorin një funksion që është gjeneruar
për ju, që ekziston në internet.

175
00:08:14,580 --> 00:08:17,240
Nëse ju bëni të vetëm të jetë i sigurt
të përmendin burimet tuaja.

176
00:08:17,240 --> 00:08:21,740
Nuk ka asnjë arsye për të
bëj plagjiaturë asgjë këtu.

177
00:08:21,740 --> 00:08:25,370
>> Komuniteti shkenca kompjuterike është
definitivisht në rritje, dhe me të vërtetë vlerat

178
00:08:25,370 --> 00:08:28,796
burim të hapur, dhe kjo është me të vërtetë e rëndësishme
të citojnë burimet tuaja në mënyrë që njerëzit

179
00:08:28,796 --> 00:08:30,670
mund të merrni atribuim për
puna që ata janë

180
00:08:30,670 --> 00:08:32,312
duke bërë për të mirën e komunitetit.

181
00:08:32,312 --> 00:08:34,020
Pra, të jetë gjithmonë sure--
dhe jo vetëm për hash

182
00:08:34,020 --> 00:08:37,270
funksionet, por në përgjithësi, kur ju
përdorni kodin nga një burim i jashtëm,

183
00:08:37,270 --> 00:08:38,299
gjithmonë citojnë burimin tuaj.

184
00:08:38,299 --> 00:08:43,500
Japin kredi për personin i cili bëri
disa të punës kështu që ju nuk keni për të.

185
00:08:43,500 --> 00:08:46,720
>> OK kështu që le të rishqyrtojnë këtë
tabelë hash për një të dytë.

186
00:08:46,720 --> 00:08:48,780
Kjo është ajo ku kemi lënë
off pas ne futur

187
00:08:48,780 --> 00:08:53,300
John dhe Paul në këtë tabelë hash.

188
00:08:53,300 --> 00:08:55,180
A ke parë një problem këtu?

189
00:08:55,180 --> 00:08:58,410
Ju mund të shihni dy.

190
00:08:58,410 --> 00:09:02,240
Por në veçanti, a
shohin këtë problem të mundshëm?

191
00:09:02,240 --> 00:09:06,770
>> Çka nëse unë hash Ringo, dhe ajo
rezulton se pas përpunimit

192
00:09:06,770 --> 00:09:14,000
që të dhënat me anë të funksionit hash
Ringo gjithashtu gjeneruar hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Unë kam marrë tashmë të dhënave në
hashcode-- array vendndodhjen 6.

194
00:09:16,810 --> 00:09:22,000
Pra, kjo ndoshta do të jetë pak
e një problemi për mua tani, apo jo?

195
00:09:22,000 --> 00:09:23,060
>> Ne e quajmë këtë një përplasje.

196
00:09:23,060 --> 00:09:26,460
Dhe përplasja ndodh kur dy
pjesë e të dhënave të drejtuar nëpër të njëjtën hash

197
00:09:26,460 --> 00:09:29,200
Funksioni i japin të njëjtën hashcode.

198
00:09:29,200 --> 00:09:32,850
Me sa duket ne ende duan të marrin dy
pjesë e të dhënave në tabela hash,

199
00:09:32,850 --> 00:09:36,330
përndryshe ne nuk do të konkurrojnë Ringo
në mënyrë arbitrare përmes funksionit hash.

200
00:09:36,330 --> 00:09:40,870
Ne me sa duket duan të marrin
Ringo në atë grup.

201
00:09:40,870 --> 00:09:46,070
>> Si nuk kemi të bëjmë atë edhe pse, në qoftë se ai
dhe Pali dyja jepnin hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Ne nuk duam të prishësh Palin,
ne duam Pali të jenë atje.

203
00:09:49,520 --> 00:09:52,790
Pra, ne kemi nevojë për të gjetur një mënyrë për të marrë
Elementet në tryezë hash që

204
00:09:52,790 --> 00:09:56,550
ende ruan Quick tonë
futje dhe të shpejtë të kërkoni.

205
00:09:56,550 --> 00:10:01,350
Dhe një mënyrë për t'u marrë me të është që të
të bëjë diçka të quajtur lineare probing.

206
00:10:01,350 --> 00:10:04,170
>> Duke përdorur këtë metodë në qoftë se ne kemi një
përplasje, mirë, çfarë bëjmë ne?

207
00:10:04,170 --> 00:10:08,580
E pra ne nuk mund ta vënë atë në vend array
6, ose çfarëdo hashcode u gjenerua,

208
00:10:08,580 --> 00:10:10,820
le të vënë atë në hashcode plus 1.

209
00:10:10,820 --> 00:10:13,670
Dhe nëse kjo është e plotë let
vënë atë në hashcode plus 2.

210
00:10:13,670 --> 00:10:17,420
Përfitimi i kësaj qenieje, nëse ai është
jo saktësisht ku ne mendojmë se është,

211
00:10:17,420 --> 00:10:20,850
dhe ne kemi për të filluar kërkimin,
Ndoshta ne nuk kemi për të shkuar shumë larg.

212
00:10:20,850 --> 00:10:23,900
Ndoshta ne nuk kemi për të kërkuar
të gjitha elementet n e tabelës hash.

213
00:10:23,900 --> 00:10:25,790
Ndoshta ne duhet të kërkoni
disa prej tyre.

214
00:10:25,790 --> 00:10:30,680
>> Dhe kështu që ne jemi ende duke tentuar drejt
se rasti mesatare duke qenë afër 1 vs

215
00:10:30,680 --> 00:10:34,280
afër n, kështu që ndoshta që do të punojnë.

216
00:10:34,280 --> 00:10:38,010
Pra, le të shohim se si kjo
mund të punojnë jashtë në realitet.

217
00:10:38,010 --> 00:10:41,460
Dhe le të shohim nëse ndoshta ne mund të zbulojë
problemi që mund të ndodhë këtu.

218
00:10:41,460 --> 00:10:42,540
>> Le të themi se të hash Bart.

219
00:10:42,540 --> 00:10:45,581
Pra, tani ne jemi duke shkuar për të drejtuar një seri të re
e tela përmes funksionit hash,

220
00:10:45,581 --> 00:10:48,460
dhe ne të drejtuar Bart me anë të hash
funksion, ne kemi marrë hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Ne kemi marrë një sy, ne shohim 6 është
bosh, kështu që ne mund të vënë Bart atje.

222
00:10:52,100 --> 00:10:55,410
>> Tani ne hash Lisa dhe se
gjithashtu gjeneron hashcode 6.

223
00:10:55,410 --> 00:10:58,330
E pra tani që ne jemi duke përdorur këtë
linear probing metodë ne të fillojë në 6,

224
00:10:58,330 --> 00:10:59,330
ne shohim se 6 është e plotë.

225
00:10:59,330 --> 00:11:00,990
Ne nuk mund të vënë Lisa në 6.

226
00:11:00,990 --> 00:11:02,090
Pra, ku do të shkojmë?

227
00:11:02,090 --> 00:11:03,280
Le të shkojnë në 7.

228
00:11:03,280 --> 00:11:04,610
7 e bosh, kështu që punon.

229
00:11:04,610 --> 00:11:06,510
Pra, le të vënë Lisa atje.

230
00:11:06,510 --> 00:11:10,200
>> Tani ne hash Homerit dhe ne të merrni 7.

231
00:11:10,200 --> 00:11:13,380
OK edhe ne e dimë se 7 e plotë
tani, kështu që ne nuk mund të vënë Homerit atje.

232
00:11:13,380 --> 00:11:14,850
Pra, le të shkojë në 8.

233
00:11:14,850 --> 00:11:15,664
Është 8 në dispozicion?

234
00:11:15,664 --> 00:11:18,330
Po, dhe afër 8-të 7, kështu që nëse
ne kemi për të filluar kërkimin jemi

235
00:11:18,330 --> 00:11:20,020
nuk do të ketë për të shkuar shumë larg.

236
00:11:20,020 --> 00:11:22,860
Dhe kështu le të vënë Homerit në 8.

237
00:11:22,860 --> 00:11:25,151
>> Tani ne hash Maggie dhe
kthehet 3, lavdi zotit

238
00:11:25,151 --> 00:11:26,650
ne jemi në gjendje për të vetëm të vënë Maggie atje.

239
00:11:26,650 --> 00:11:29,070
Ne nuk duhet të bëjmë ndonjë
lloj probing për atë.

240
00:11:29,070 --> 00:11:32,000
Tani ne hash Marge, dhe
Marge gjithashtu kthehet 6.

241
00:11:32,000 --> 00:11:39,560
>> E pra 6 është e plotë, 7 është e plotë, 8 është e plotë,
9, të gjithë të drejtë falënderoj Perëndinë, 9 është bosh.

242
00:11:39,560 --> 00:11:41,600
Unë mund të vënë Marge në 9.

243
00:11:41,600 --> 00:11:45,280
Tashmë ne mund të shohim se ne jemi duke filluar
që të ketë këtë problem, ku tani ne jemi

244
00:11:45,280 --> 00:11:48,780
filluar të shtrihet gjërat lloj
e larg nga kodet e tyre hash.

245
00:11:48,780 --> 00:11:52,960
Dhe që theta nga 1, që mesatarja
rast për të qenë kohë konstante,

246
00:11:52,960 --> 00:11:56,560
ka filluar të marrë një more-- vogël
duke filluar për të tentojnë pak më shumë

247
00:11:56,560 --> 00:11:58,050
drejt theta të n.

248
00:11:58,050 --> 00:12:01,270
Ne jemi duke filluar për të humbur atë
Përparësia e tabelave hash.

249
00:12:01,270 --> 00:12:03,902
>> Ky problem që ne vetëm e pa
është diçka e quajtur clustering.

250
00:12:03,902 --> 00:12:06,360
Dhe çfarë është me të vërtetë keq për
clustering është se sapo ju tani

251
00:12:06,360 --> 00:12:09,606
kanë dy elemente që janë krah për
anën kjo e bën atë edhe më shumë të ngjarë,

252
00:12:09,606 --> 00:12:11,480
ju keni të dyfishtë
mundësi, se ju do të jeni

253
00:12:11,480 --> 00:12:13,516
të ketë një tjetër përplasje
me këtë grup,

254
00:12:13,516 --> 00:12:14,890
dhe grup do të rritet nga një.

255
00:12:14,890 --> 00:12:19,640
Dhe ju do të vazhdojë të rritet dhe të rritet
mundësia juaj për të pasur një përplasje.

256
00:12:19,640 --> 00:12:24,470
Dhe në fund ajo është po aq e keqe
si mos zgjidhja e të dhënave në të gjitha.

257
00:12:24,470 --> 00:12:27,590
>> Problemi tjetër edhe pse është ne
ende, dhe deri më tani deri në këtë pikë,

258
00:12:27,590 --> 00:12:30,336
ne kemi qenë vetëm lloj i
kuptuar se çfarë një tabelë hash është,

259
00:12:30,336 --> 00:12:31,960
ne ende vetëm kanë vend për 10 strings.

260
00:12:31,960 --> 00:12:37,030
Në qoftë se ne duam të vazhdojmë të hash
qytetarët e Springfield,

261
00:12:37,030 --> 00:12:38,790
ne mund të merrni vetëm 10 prej tyre në atje.

262
00:12:38,790 --> 00:12:42,619
Dhe në qoftë se ne të përpiqemi dhe të shtoni një 11 ose 12,
ne nuk kemi një vend për të vënë ato.

263
00:12:42,619 --> 00:12:45,660
Ne vetëm mund të jetë tjerrje rreth në
qarqet duke u përpjekur për të gjetur një vend bosh,

264
00:12:45,660 --> 00:12:49,000
dhe ne ndoshta merrni mbërthyer
në një lak të pafund.

265
00:12:49,000 --> 00:12:51,810
>> Pra, ky lloj i jep hua për idesë
e diçka të quajtur chaining.

266
00:12:51,810 --> 00:12:55,790
Dhe kjo është ajo ku ne jemi duke shkuar për të sjellë
Listat e lidhura prapa në foto.

267
00:12:55,790 --> 00:13:01,300
Çfarë nëse në vend të ruajtjen vetëm
të dhënat vetë në grup,

268
00:13:01,300 --> 00:13:04,471
çdo element i vektorit mund të
të mbajë pjesë të shumta e të dhënave?

269
00:13:04,471 --> 00:13:05,970
E pra kjo nuk ka kuptim, apo jo?

270
00:13:05,970 --> 00:13:09,280
Ne e dimë se një grup mund të vetëm
hold-- çdo element të një sërë

271
00:13:09,280 --> 00:13:12,930
mund të mbajë vetëm një pjesë
e të dhënave të atij lloji të dhënave.

272
00:13:12,930 --> 00:13:16,750
>> Por çfarë nëse kjo lloj e të dhënave
është një listë e lidhur, e drejtë?

273
00:13:16,750 --> 00:13:19,830
Pra, çfarë nëse çdo
element i vektorit ishte

274
00:13:19,830 --> 00:13:22,790
një tregues në krye të listës të lidhura?

275
00:13:22,790 --> 00:13:24,680
Dhe pastaj ne mund të ndërtojmë
këto listat lidhura

276
00:13:24,680 --> 00:13:27,120
dhe rriten ata në mënyrë arbitrare,
sepse listat lidhura lejojë

277
00:13:27,120 --> 00:13:32,090
ne të rritet dhe tkurret shumë më tepër
fleksibilitet se një grup bën.

278
00:13:32,090 --> 00:13:34,210
Pra, çfarë nëse ne tani përdorin,
ne levave kjo, apo jo?

279
00:13:34,210 --> 00:13:37,760
Ne fillojmë të rriten këto zinxhirët
nga këto vende array.

280
00:13:37,760 --> 00:13:40,740
>> Tani ne mund të përshtatet një infinit
Shuma e të dhënave, apo jo pafund,

281
00:13:40,740 --> 00:13:44,170
një sasi arbitrare të
të dhënave, në tryezën tonë hash

282
00:13:44,170 --> 00:13:47,760
pa ndonjëherë drejtimin në
problemi i përplasjes.

283
00:13:47,760 --> 00:13:50,740
Ne kemi eliminuar edhe
clustering duke bërë këtë.

284
00:13:50,740 --> 00:13:54,380
Dhe ne e dimë mirë se kur ne të futur
në një listë të lidhura, në qoftë se ju kujtohet

285
00:13:54,380 --> 00:13:57,779
nga video tonë në listat e lidhura, veçmas
Listat e lidhura dhe listat lidhura dyfish,

286
00:13:57,779 --> 00:13:59,070
kjo është një operacion i vazhdueshëm kohë.

287
00:13:59,070 --> 00:14:00,710
Ne jemi vetëm duke shtuar në pjesën e përparme.

288
00:14:00,710 --> 00:14:04,400
>> Dhe për look up, edhe ne e dimë
që shikoni në një listë të lidhura

289
00:14:04,400 --> 00:14:05,785
mund të jetë një problem, e drejtë?

290
00:14:05,785 --> 00:14:07,910
Ne duhet të kërkoni përmes
ajo nga fillimi në fund.

291
00:14:07,910 --> 00:14:10,460
Nuk ka asnjë mënyrë të rastësishme
qasje në një listë të lidhura.

292
00:14:10,460 --> 00:14:15,610
Por në qoftë se në vend të paturit e një të tillë lidhur
Lista ku një lookup do të jetë o të n,

293
00:14:15,610 --> 00:14:19,590
ne tani kemi 10 listave të lidhura,
ose 1.000 listat lidhura,

294
00:14:19,590 --> 00:14:24,120
tani është o n i ndarë nga 10,
ose o të n ndarë nga 1,000.

295
00:14:24,120 --> 00:14:26,940
>> Dhe, ndërsa ne ishim duke folur
teorikisht në lidhje me kompleksitetin

296
00:14:26,940 --> 00:14:30,061
ne mosrespektimi konstante, në reale
Bota këto gjëra në fakt rëndësi,

297
00:14:30,061 --> 00:14:30,560
e drejtë?

298
00:14:30,560 --> 00:14:33,080
Ne fakt do të vini re
se kjo ndodh

299
00:14:33,080 --> 00:14:36,610
për të kandiduar 10 herë më të shpejtë,
ose 1000 herë më shpejt,

300
00:14:36,610 --> 00:14:41,570
sepse ne jemi shpërndarjen e gjatë
zinxhir nëpër 1000 zinxhirët më të vogla.

301
00:14:41,570 --> 00:14:45,090
Dhe kështu çdo herë që ne kemi për të kërkuar
përmes një prej këtyre zinxhirëve ne mund të

302
00:14:45,090 --> 00:14:50,290
injorojnë 999 zinxhirët ne nuk e kujdesit
në lidhje me, dhe kërko vetëm se një.

303
00:14:50,290 --> 00:14:53,220
>> E cila është mesatarisht për
të jetë 1,000 herë më të shkurtër.

304
00:14:53,220 --> 00:14:56,460
Dhe kështu që ne ende jemi të lloj
duke tentuar drejt këtë rast mesatare

305
00:14:56,460 --> 00:15:01,610
për të qenë kohë të vazhdueshme, por
vetëm për shkak se ne jemi leveraging

306
00:15:01,610 --> 00:15:03,730
duke e ndarë nga një faktor i madh konstante.

307
00:15:03,730 --> 00:15:05,804
Le të shohim se si kjo mund të
në fakt duken pse.

308
00:15:05,804 --> 00:15:08,720
Pra, ky ishte tabelë hash kemi pasur
para se të deklaruar një tabelë hash që

309
00:15:08,720 --> 00:15:10,270
ishte i aftë për ruajtjen 10 strings.

310
00:15:10,270 --> 00:15:11,728
Ne nuk jemi duke shkuar për të bërë atë më.

311
00:15:11,728 --> 00:15:13,880
Ne tashmë e dimë
Kufizimet e kësaj metode.

312
00:15:13,880 --> 00:15:20,170
Tani tabelën tonë hash do të jetë
një grup prej 10 nyjet, pointers

313
00:15:20,170 --> 00:15:22,120
të krerëve të listave të lidhura.

314
00:15:22,120 --> 00:15:23,830
>> Dhe tani kjo është null.

315
00:15:23,830 --> 00:15:26,170
Secili prej këtyre 10 pointers është i pavlefshëm.

316
00:15:26,170 --> 00:15:29,870
Nuk ka asgjë në tonë
hash tryezë tani.

317
00:15:29,870 --> 00:15:32,690
>> Tani le të fillojë për të vënë disa
gjërat në këtë tabelë hash.

318
00:15:32,690 --> 00:15:35,440
Dhe le të shohim se si kjo metodë është
do të na përfituar pak.

319
00:15:35,440 --> 00:15:36,760
Le tani të hash Joey.

320
00:15:36,760 --> 00:15:40,210
Ne do të do të kandidojë string Joey përmes
një funksion hash dhe do të kthehemi 6.

321
00:15:40,210 --> 00:15:41,200
E pra çfarë bëjmë ne tani?

322
00:15:41,200 --> 00:15:44,090
>> E pra tani duke punuar me listat e lidhura,
ne nuk jemi duke punuar me vargjeve.

323
00:15:44,090 --> 00:15:45,881
Dhe kur ne jemi duke punuar
me listat e lidhura ne

324
00:15:45,881 --> 00:15:49,790
e di se ne kemi nevojë për të filluar dinamike
caktimin hapësirë ​​dhe ndërtimit zinxhirët.

325
00:15:49,790 --> 00:15:54,020
Kjo është lloj i how-- ato janë thelbi
Elementet e ndërtimit të një listë e lidhur.

326
00:15:54,020 --> 00:15:57,670
Pra, le të dinamike
ndajë hapësirë ​​për Joey,

327
00:15:57,670 --> 00:16:00,390
dhe pastaj le të shtoni atë në zinxhirin.

328
00:16:00,390 --> 00:16:03,170
>> Pra, tani të shohim se çfarë kemi bërë.

329
00:16:03,170 --> 00:16:06,440
Kur ne hash Joey kemi marrë hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Tani akrep në array vend të 6
vë në krye të një listë të lidhura,

331
00:16:11,790 --> 00:16:14,900
dhe tani kjo është e vetmja
element i një liste të lidhura.

332
00:16:14,900 --> 00:16:18,350
Dhe nyja në atë
listë e lidhur është Joey.

333
00:16:18,350 --> 00:16:22,300
>> Pra, nëse ne duhet të shohim deri Joey
më vonë, ne vetëm të hash Joey përsëri,

334
00:16:22,300 --> 00:16:26,300
ne kemi marrë 6 përsëri sepse tonë
funksion hash është determinist.

335
00:16:26,300 --> 00:16:30,400
Dhe pastaj ne të fillojë në krye
e listës lidhur theksuar

336
00:16:30,400 --> 00:16:33,360
për nga lokacioni array
6, dhe ne mund iterate

337
00:16:33,360 --> 00:16:35,650
të gjithë se duke u përpjekur për të gjetur Joey.

338
00:16:35,650 --> 00:16:37,780
Dhe në qoftë se ne ndërtojmë tonë
hash tryezë në mënyrë efektive,

339
00:16:37,780 --> 00:16:41,790
dhe funksioni ynë hash në mënyrë efektive
për të shpërndarë të dhënat e mirë,

340
00:16:41,790 --> 00:16:45,770
mesatarisht secili prej atyre të lidhura
Listat në çdo vend array

341
00:16:45,770 --> 00:16:50,110
do të jetë 1/10 madhësia e nëse ne
kishte vetëm atë si një e vetme e madhe

342
00:16:50,110 --> 00:16:51,650
listë e lidhur me çdo gjë në të.

343
00:16:51,650 --> 00:16:55,670
>> Nëse ne shpërndajë se i madh i lidhur
Lista e të gjithë 10 listat e lidhura

344
00:16:55,670 --> 00:16:57,760
çdo listë do të jetë 1/10 madhësia.

345
00:16:57,760 --> 00:17:01,432
Dhe kështu 10 herë më të shpejtë
për të kërkuar përmes.

346
00:17:01,432 --> 00:17:02,390
Pra, le ta bëjmë këtë përsëri.

347
00:17:02,390 --> 00:17:04,290
Le tani të hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Dhe le të themi Ross, kur ne bëjmë atë
kodi hash marrim përsëri është 2.

349
00:17:07,540 --> 00:17:10,630
E pra tani ne dinamike ndajë një
nyje e re, ne kemi vënë Ross në atë nyje,

350
00:17:10,630 --> 00:17:14,900
dhe ne themi tani vendndodhja grup
2, në vend të duke treguar null,

351
00:17:14,900 --> 00:17:18,579
vë në kokën e një i lidhur
Lista nyje vetëm i të cilit është Ross.

352
00:17:18,579 --> 00:17:22,660
Dhe ne mund të bëjmë këtë edhe një herë më shumë, ne
mund të hash Rakelën dhe për të marrë hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc një nyje të re, e vënë Rachel në
nyjen, dhe thonë se një vend array

354
00:17:25,490 --> 00:17:27,839
4 tani vë në kokë
nga një listë e lidhur e të cilit

355
00:17:27,839 --> 00:17:31,420
vetëm element ndodh të jetë Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK por çfarë ndodh nëse
ne kemi një përplasje?

357
00:17:33,470 --> 00:17:38,560
Le të shohim se si kemi trajtuar goditjet
duke përdorur metodën e veçantë chaining.

358
00:17:38,560 --> 00:17:39,800
Le të hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Ne kemi marrë hashcode 6.

360
00:17:41,094 --> 00:17:44,010
Në shembullin tonë të mëparshme ishim vetëm
ruajtjen strings në rrjet.

361
00:17:44,010 --> 00:17:45,980
Ky ishte një problem.

362
00:17:45,980 --> 00:17:48,444
>> Ne nuk duam të plaçkë
Joey, dhe ne kemi tashmë

363
00:17:48,444 --> 00:17:51,110
shihet që ne mund të merrni disa clustering
Problemet në qoftë se ne të përpiqemi dhe hap

364
00:17:51,110 --> 00:17:52,202
përmes dhe hetim.

365
00:17:52,202 --> 00:17:54,660
Por, çfarë nëse ne vetëm lloj i
trajtuar këtë në të njëjtën mënyrë, apo jo?

366
00:17:54,660 --> 00:17:57,440
Është vetëm si duke shtuar një element të
në krye të një listë të lidhura.

367
00:17:57,440 --> 00:18:00,220
Le hapësirë ​​vetëm malloc për Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Ne do të themi pikët e radhës Phoebe pointer
të kreut të vjetër të listës lidhur,

369
00:18:04,764 --> 00:18:07,180
dhe pastaj 6 vetëm pikë për
Kreu i ri i listës së lidhur.

370
00:18:07,180 --> 00:18:10,150
Dhe tani shikoni, ne kemi ndryshuar Phoebe në.

371
00:18:10,150 --> 00:18:14,210
Ne tani mund të ruajë dy
Elementet me hashcode 6,

372
00:18:14,210 --> 00:18:17,170
dhe ne nuk kemi ndonjë problem.

373
00:18:17,170 --> 00:18:20,147
>> Kjo është shumë e shumë të gjithë
ka te chaining.

374
00:18:20,147 --> 00:18:21,980
Dhe chaining është padyshim
metodë që është

375
00:18:21,980 --> 00:18:27,390
do të jetë më efektive për ju, nëse
ju jeni ruajtjen e të dhënave në një tabelë hash.

376
00:18:27,390 --> 00:18:30,890
Por ky kombinim i
vargjeve dhe listat lidhura

377
00:18:30,890 --> 00:18:36,080
së bashku për të formuar një tabelë hash të vërtetë
në mënyrë dramatike përmirëson aftësinë tuaj

378
00:18:36,080 --> 00:18:40,550
për të ruajtur sasi të mëdha të të dhënave, dhe
shumë shpejt dhe me efikasitet të kërkoni

379
00:18:40,550 --> 00:18:41,630
nëpër këto të dhëna.

380
00:18:41,630 --> 00:18:44,150
>> Ka ende një më shumë
Struktura e të dhënave atje

381
00:18:44,150 --> 00:18:48,700
që mund edhe të jetë pak
më të mirë në aspektin e garantimit

382
00:18:48,700 --> 00:18:51,920
se futje tonë, fshirje, dhe
Look up kohët janë edhe më të shpejtë.

383
00:18:51,920 --> 00:18:55,630
Dhe ne do të shohim se në një video në përpiqet.

384
00:18:55,630 --> 00:18:58,930
Unë jam Doug Lloyd, kjo është CS50.

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