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

2
00:00:00,500 --> 00:00:01,900
[Daqq tal-mużika]

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

4
00:00:05,710 --> 00:00:09,150
>> Doug LLOYD: Sa issa inti
jafu ħafna dwar arrays,

5
00:00:09,150 --> 00:00:11,610
u inti taf ħafna dwar listi marbuta.

6
00:00:11,610 --> 00:00:13,650
U aħna ħadthom jiddiskutu l
vantaġġi u liżvantaġġi, konna

7
00:00:13,650 --> 00:00:16,620
diskussi li marbuta listi
jistgħu jiksbu akbar u iżgħar,

8
00:00:16,620 --> 00:00:18,630
iżda dawn jieħdu aktar daqs.

9
00:00:18,630 --> 00:00:22,359
Arrays huma ħafna aktar faċli li
użu, iżda dawn qed restrittiva fil kemm

10
00:00:22,359 --> 00:00:24,900
kif għandna li jistabbilixxi daqs tal
l-array fil-bidu nett

11
00:00:24,900 --> 00:00:26,910
u allura aħna qed mwaħħla miegħu.

12
00:00:26,910 --> 00:00:30,470
>> Imma dak li, konna pretty ħafna
eżawriti kollha ta 'suġġetti tagħna

13
00:00:30,470 --> 00:00:33,040
dwar listi konnessi u arrays.

14
00:00:33,040 --> 00:00:34,950
Jew ikollhom we?

15
00:00:34,950 --> 00:00:37,720
Forsi nistgħu nagħmlu xi ħaġa
saħansitra aktar kreattivi.

16
00:00:37,720 --> 00:00:40,950
U dik it-tip ta 'jsellef
l-idea ta 'tabella hash.

17
00:00:40,950 --> 00:00:46,680
>> Allura f'tabella hash aħna qed tmur biex tipprova
jikkombinaw firxa ma 'lista marbuta.

18
00:00:46,680 --> 00:00:49,520
Aħna qed tmur biex tieħu l-vantaġġi
mill-firxa, bħall-aċċess bl-addoċċ,

19
00:00:49,520 --> 00:00:53,510
li tista 'biss mur firxa
element 4 jew firxa element 8

20
00:00:53,510 --> 00:00:55,560
mingħajr ma jkollhom jtenni madwar.

21
00:00:55,560 --> 00:00:57,260
Li pretty fast, id-dritt?

22
00:00:57,260 --> 00:01:00,714
>> Iżda aħna wkoll tixtieq li jkollok data tagħna
istruttura tkun kapaċi li jikbru u tiċkien.

23
00:01:00,714 --> 00:01:02,630
M'għandniex bżonn, aħna ma
jridu jiġu ristretti.

24
00:01:02,630 --> 00:01:04,588
U irridu nkunu kapaċi
li żżid u neħħi l-affarijiet

25
00:01:04,588 --> 00:01:08,430
faċilment, li jekk inti recall,
hija kumplessa ħafna ma 'firxa.

26
00:01:08,430 --> 00:01:11,650
U nistgħu sejħa dan
ħaġa ġdida tabella hash.

27
00:01:11,650 --> 00:01:15,190
>> U jekk implimentati b'mod korrett,
aħna qed tip ta 'teħid

28
00:01:15,190 --> 00:01:18,150
il-vantaġġi taż-żewġ data
istrutturi inti stajt diġà raw,

29
00:01:18,150 --> 00:01:19,880
arrays u listi marbuta.

30
00:01:19,880 --> 00:01:23,070
Inserzjoni jistgħu jibdew
tendenza lejn theta minn 1.

31
00:01:23,070 --> 00:01:26,207
Theta aħna ma diskussi verament,
iżda theta huwa biss il-każ medja,

32
00:01:26,207 --> 00:01:27,540
dak li attwalment jiġri.

33
00:01:27,540 --> 00:01:29,680
Int mhux dejjem se
għandhom l-agħar każ,

34
00:01:29,680 --> 00:01:32,555
u int mhux dejjem se jkollhom
l aħjar każ, hekk x'hemm

35
00:01:32,555 --> 00:01:33,900
ix-xenarju medju?

36
00:01:33,900 --> 00:01:36,500
>> Well inserzjoni medja
fis-tabella hash

37
00:01:36,500 --> 00:01:39,370
tista 'tibda li jersaq qrib għal żmien kostanti.

38
00:01:39,370 --> 00:01:41,570
U t-tħassir jista 'jikseb
qrib għal żmien kostanti.

39
00:01:41,570 --> 00:01:44,440
U lookup jistgħu jiksbu
qrib għal żmien kostanti.

40
00:01:44,440 --> 00:01:48,600
That's-- aħna ma jkollhomx data
istruttura li għadha tista 'tagħmel dan,

41
00:01:48,600 --> 00:01:51,180
u għalhekk dan diġà ħsejjes
bħal ħaġa pretty kbira.

42
00:01:51,180 --> 00:01:57,010
Imxejna verament mitigati l
żvantaġġi ta 'kull waħdu.

43
00:01:57,010 --> 00:01:59,160
>> Biex tikseb din il-prestazzjoni
upgrade għalkemm, aħna

44
00:01:59,160 --> 00:02:03,580
bżonn naħsbu mill-ġdid kif aħna żid
data fl-istruttura.

45
00:02:03,580 --> 00:02:07,380
Speċifikament irridu li l-
data nnifisha biex tgħidilna

46
00:02:07,380 --> 00:02:09,725
fejn għandhom imorru fl-istruttura.

47
00:02:09,725 --> 00:02:12,850
U jekk aħna mbagħad bżonn biex tara jekk huwa fil
l-istruttura, jekk għandna bżonn issib lilha,

48
00:02:12,850 --> 00:02:16,610
irridu nħarsu lejn il-data
ġdid u tkun tista 'b'mod effettiv,

49
00:02:16,610 --> 00:02:18,910
tintuża d-dejta, każwalment jkollhom aċċess għaliha.

50
00:02:18,910 --> 00:02:20,700
Biss billi tħares lejn l-
data għandu jkollna

51
00:02:20,700 --> 00:02:25,890
idea ta 'fejn eżattament aħna qed
ser isibuha fit-tabella hash.

52
00:02:25,890 --> 00:02:28,770
>> Issa l-tnaqqis ta 'hash
tabella hija li dawn qed verament

53
00:02:28,770 --> 00:02:31,770
pretty bad fuq ordni jew issortjar data.

54
00:02:31,770 --> 00:02:34,970
U fil-fatt, jekk inti tibda
li jużawhom għall-ordni jew it-tip

55
00:02:34,970 --> 00:02:37,990
data inti titlef kollha ta 'l-
vantaġġi inti qabel

56
00:02:37,990 --> 00:02:40,710
kellhom f'termini ta 'inserzjoni u t-tħassir.

57
00:02:40,710 --> 00:02:44,060
Il-ħin isir eqreb lejn
theta ta n, u konna bażikament

58
00:02:44,060 --> 00:02:45,530
naqas f'lista marbuta.

59
00:02:45,530 --> 00:02:48,850
U hekk aħna biss tixtieq li tuża hash
tabelli jekk aħna ma jimpurtahom

60
00:02:48,850 --> 00:02:51,490
jekk id-data huwa magħżul.

61
00:02:51,490 --> 00:02:54,290
Għall-kuntest li fih
inti ser jużawhom fil CS50

62
00:02:54,290 --> 00:02:58,900
inti probabilment ma 'kura
li d-data hija magħżula.

63
00:02:58,900 --> 00:03:03,170
>> Allura tabella hash huwa kombinazzjoni
ta 'żewġ biċċiet distinti

64
00:03:03,170 --> 00:03:04,980
li aħna qed familjari.

65
00:03:04,980 --> 00:03:07,930
L-ewwel hija funzjoni, li
aħna normalment sejħa funzjoni hash.

66
00:03:07,930 --> 00:03:11,760
U dik il-funzjoni hash se
ritorn xi numru sħiħ mhux negattiva, li

67
00:03:11,760 --> 00:03:14,870
aħna normalment sejħa hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
It-tieni biċċa hija firxa, li hija
kapaċi maħżuna d- data tat-tip aħna

69
00:03:20,230 --> 00:03:22,190
jixtiequ li jpoġġu fl-istruttura tad-data.

70
00:03:22,190 --> 00:03:24,310
Aħna ser jżommu off fuq il-
marbuta element lista għal issa

71
00:03:24,310 --> 00:03:27,810
u biss tibda bil-punti bażiċi ta '
hash tabella li tikseb ras tiegħek madwar dan,

72
00:03:27,810 --> 00:03:30,210
u allura aħna ser forsi blow
moħħok ftit meta aħna

73
00:03:30,210 --> 00:03:32,920
jikkombinaw arrays u listi rabta flimkien.

74
00:03:32,920 --> 00:03:35,590
>> L-idea bażika għalkemm
huwa nieħdu xi data.

75
00:03:35,590 --> 00:03:37,860
We run li d-data permezz
il-funzjoni hash.

76
00:03:37,860 --> 00:03:41,980
U għalhekk id-data hija pproċessata
u spits out numru, OK?

77
00:03:41,980 --> 00:03:44,890
U mbagħad b'dak l-għadd
aħna biss jaħżen id-data

78
00:03:44,890 --> 00:03:48,930
irridu li jaħżnu fil-
firxa f'dak il-post.

79
00:03:48,930 --> 00:03:53,990
Għalhekk, per eżempju għandna forsi
din it-tabella hash ta 'spag.

80
00:03:53,990 --> 00:03:57,350
Huwa ltqajna 10 elementi fiha, so
nistgħu joqogħdu 10 kordi fiha.

81
00:03:57,350 --> 00:03:59,320
>> Ejja ngħidu li rridu hash John.

82
00:03:59,320 --> 00:04:02,979
Allura John billi d-data irridu li daħħal
fis din it-tabella hash x'imkien.

83
00:04:02,979 --> 00:04:03,770
Fejn nistgħu poġġih?

84
00:04:03,770 --> 00:04:05,728
Well tipikament ma '
firxa s'issa aħna probabbilment

85
00:04:05,728 --> 00:04:07,610
ipoġġiha fil-lokalità firxa 0.

86
00:04:07,610 --> 00:04:09,960
Imma issa għandna din il-funzjoni hash ġdid.

87
00:04:09,960 --> 00:04:13,180
>> U ejja ngħidu li aħna run John
permezz ta 'din il-funzjoni hash

88
00:04:13,180 --> 00:04:15,417
u huwa spits out 4.

89
00:04:15,417 --> 00:04:17,500
Ukoll li fejn aħna qed
tmur jridu jitqiegħdu John.

90
00:04:17,500 --> 00:04:22,050
Aħna tixtieq li tqiegħed John f'post firxa
4, għaliex jekk aħna hash John again--

91
00:04:22,050 --> 00:04:23,810
ejja ngħidu wara aħna
trid tfittex u tara

92
00:04:23,810 --> 00:04:26,960
jekk John teżisti f'dan hash
table-- kollha għandna bżonn tagħmel

93
00:04:26,960 --> 00:04:30,310
hija mmexxija permezz ta 'l-istess hash
funzjoni, jiksbu l-out numru 4,

94
00:04:30,310 --> 00:04:33,929
u tkun tista 'ssib John
immedjatament fl-istruttura tad-data tagħna.

95
00:04:33,929 --> 00:04:34,720
Li pjuttost tajba.

96
00:04:34,720 --> 00:04:36,928
>> Ejja ngħidu aħna issa nagħmlu dan
għal darb'oħra, irridu li hash Paul.

97
00:04:36,928 --> 00:04:39,446
Aħna tixtieq iżżid Paul
fis din it-tabella hash.

98
00:04:39,446 --> 00:04:42,070
Ejja ngħidu li din id-darba we run
Paul permezz tal-funzjoni hash,

99
00:04:42,070 --> 00:04:44,600
l hashcode li hija ġġenerata hija ta '6.

100
00:04:44,600 --> 00:04:47,340
Ukoll issa nistgħu npoġġu Paul
fil-post array 6.

101
00:04:47,340 --> 00:04:50,040
U jekk għandna bżonn li wieħed ifittex jekk
Paul huwa f'din it-tabella hash,

102
00:04:50,040 --> 00:04:53,900
kollha għandna bżonn tagħmel huwa mmexxi Paul
permezz tal-funzjoni hash mill-ġdid

103
00:04:53,900 --> 00:04:55,830
u aħna qed tmur biex tikseb 6 mill-ġdid.

104
00:04:55,830 --> 00:04:57,590
>> U allura aħna biss ħarsa
fil-post array 6.

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

106
00:04:58,910 --> 00:05:00,160
Jekk iva, hu fit-tabella hash.

107
00:05:00,160 --> 00:05:01,875
Huwa Paul ma hemm?

108
00:05:01,875 --> 00:05:03,000
Huwa ma fit-tabella hash.

109
00:05:03,000 --> 00:05:05,720
Huwa pjuttost sempliċi.

110
00:05:05,720 --> 00:05:07,770
>> Issa kif taħseb li jiddefinixxu funzjoni hash?

111
00:05:07,770 --> 00:05:11,460
Ukoll hemm verament ebda limitu għall-
numru ta 'funzjonijiet possibbli hash.

112
00:05:11,460 --> 00:05:14,350
Fil-fatt hemm numru ta 'tassew,
dawk verament tajba fuq l-internet.

113
00:05:14,350 --> 00:05:17,560
Hemm numru ta 'tassew,
dawk verament ħżiena fuq l-internet.

114
00:05:17,560 --> 00:05:21,080
Huwa wkoll pjuttost faċli
jiktbu waħda ħażina.

115
00:05:21,080 --> 00:05:23,760
>> Allura dak li jagħmel up a tajba
funzjoni hash, id-dritt?

116
00:05:23,760 --> 00:05:27,280
Well funzjoni hash tajba għandhom
jużaw biss l-informazzjoni li qed hashed,

117
00:05:27,280 --> 00:05:29,420
u kollha tad-data li qed hashed.

118
00:05:29,420 --> 00:05:32,500
Allura aħna ma jridu jużaw anything--
aħna ma jinkorporaw xejn

119
00:05:32,500 --> 00:05:35,560
inkella barra mit-tagħrif.

120
00:05:35,560 --> 00:05:37,080
U aħna tixtieq li tuża kollha tad-data.

121
00:05:37,080 --> 00:05:39,830
Aħna ma jridux biss tuża biċċa
ta 'dan, aħna tixtieq li tagħmel użu kollu kemm hu.

122
00:05:39,830 --> 00:05:41,710
Funzjoni hash għandhom
wkoll tkun deterministic.

123
00:05:41,710 --> 00:05:42,550
Xi tfisser?

124
00:05:42,550 --> 00:05:46,200
Ukoll dan ifisser li kull darba li aħna
jgħaddu l-istess biċċa eżatt ta 'data

125
00:05:46,200 --> 00:05:50,040
fil-funzjoni hash aħna dejjem
jiksbu l-istess hashcode out.

126
00:05:50,040 --> 00:05:52,870
Jekk I jgħaddu John fil-
funzjoni hash I toħroġ 4.

127
00:05:52,870 --> 00:05:56,110
I għandhom ikunu jistgħu jagħmlu dan 10,000
ħinijiet u jien ser dejjem nikseb 4.

128
00:05:56,110 --> 00:06:00,810
Allura l-ebda każwali numri effettiv
jistgħu jiġu involuti fl hash tagħna tables--

129
00:06:00,810 --> 00:06:02,750
fil-funzjonijiet hash tagħna.

130
00:06:02,750 --> 00:06:05,750
>> Funzjoni hash għandha wkoll
uniformi tqassam data.

131
00:06:05,750 --> 00:06:09,700
Jekk kull darba li inti tmexxi data permezz tal-
funzjoni hash ikollok l-hashcode 0,

132
00:06:09,700 --> 00:06:11,200
li probabbilment mhux daqshekk kbir, id-dritt?

133
00:06:11,200 --> 00:06:14,600
Inti probabilment jridu big
firxa ta 'kodiċijiet hash.

134
00:06:14,600 --> 00:06:17,190
Ukoll affarijiet jistgħu jinfirxu
kemm matul il-mejda.

135
00:06:17,190 --> 00:06:23,210
U wkoll ikun kbir jekk verament
data simili, bħal John u Jonathan,

136
00:06:23,210 --> 00:06:26,320
forsi kienu mifruxa li jintiżnu
postijiet differenti fit-tabella hash.

137
00:06:26,320 --> 00:06:28,750
Dan ikun ta 'vantaġġ sbieħ.

138
00:06:28,750 --> 00:06:31,250
>> Hawn eżempju ta 'funzjoni hash.

139
00:06:31,250 --> 00:06:33,150
I kiteb dan wieħed up qabel.

140
00:06:33,150 --> 00:06:35,047
Mhuwiex partikolarment
funzjoni hash tajba

141
00:06:35,047 --> 00:06:37,380
għal raġunijiet li ma verament
iġorru nidħlu dritt issa.

142
00:06:37,380 --> 00:06:41,040
Imma inti tara x'inhu għaddej hawn?

143
00:06:41,040 --> 00:06:44,420
Jidher simili aħna qed tiddikjara varjabbli
imsejħa somma u dan ikun iffissat ugwali għal 0.

144
00:06:44,420 --> 00:06:50,010
U allura apparentement qed nagħmel xi ħaġa
sakemm strstr [j] mhijiex ugwali

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

146
00:06:52,490 --> 00:06:54,870
What am I tagħmel hemmhekk?

147
00:06:54,870 --> 00:06:57,440
>> Dan huwa bażikament biss ieħor
Mod ta 'implimentazzjoni [? STRL?]

148
00:06:57,440 --> 00:06:59,773
u skoperta meta inti stajt
laħqu t-tmiem tas-sekwenza.

149
00:06:59,773 --> 00:07:02,480
So I ma jkollhomx biex effettivament
jikkalkulaw it-tul tas-sekwenza,

150
00:07:02,480 --> 00:07:05,640
Jien biss jużaw meta I hit l-
backslash 0 karattru Naf

151
00:07:05,640 --> 00:07:07,185
Stajt laħqu t-tmiem tas-sekwenza.

152
00:07:07,185 --> 00:07:09,560
U allura jien ser iżommu
mtennija permezz ta 'dak string,

153
00:07:09,560 --> 00:07:15,310
żżid strstr [j] fi ftit kliem, u mbagħad fl-
aħħar tal-ġurnata se jirritorna mod somma

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

155
00:07:16,200 --> 00:07:18,700
>> Bażikament dan kollu hash
funzjoni qed tagħmel qed iżżid up

156
00:07:18,700 --> 00:07:23,450
kollha tal-valuri ASCII ta
string tiegħi, u allura huwa

157
00:07:23,450 --> 00:07:26,390
jirritornaw xi hashcode
Modded mill HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Huwa probabbilment l-daqs
ta array tiegħi, id-dritt?

159
00:07:29,790 --> 00:07:33,160
Ma rridx li jkollna hash
kodiċijiet jekk firxa tiegħi huwa ta 'daqs 10,

160
00:07:33,160 --> 00:07:35,712
Ma rridx li tkun jkollna
kodiċijiet barra hash 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, I ma tista 'tpoġġi l-affarijiet fil
f'dawn il-postijiet ta 'l-array,

162
00:07:38,690 --> 00:07:39,790
li jkun illegali.

163
00:07:39,790 --> 00:07:42,130
I d jsofru tort segmentazzjoni.

164
00:07:42,130 --> 00:07:45,230
>> Issa hawnhekk hija ieħor malajr aside.

165
00:07:45,230 --> 00:07:48,470
Ġeneralment int probabilment mhux se
jridu jiktbu funzjonijiet tiegħek hash stess.

166
00:07:48,470 --> 00:07:50,997
Huwa fil-fatt daqsxejn ta
arti, mhux xjenza.

167
00:07:50,997 --> 00:07:52,580
U hemm ħafna li tmur ġo fihom.

168
00:07:52,580 --> 00:07:55,288
L-internet, bħal I said, huwa sħiħa
tal-funzjonijiet hash verament tajba,

169
00:07:55,288 --> 00:07:58,470
u għandek tuża l-internet biex
Sib l-funzjonijiet hash għaliex dan huwa verament

170
00:07:58,470 --> 00:08:03,230
biss it-tip ta 'bla bżonn
ħela ta 'ħin biex joħolqu tiegħek.

171
00:08:03,230 --> 00:08:05,490
>> Tista 'tikteb dawk sempliċi
għal skopijiet li jittestjaw.

172
00:08:05,490 --> 00:08:08,323
Imma meta inti fil-fatt se
tibda hashing data u maħżuna

173
00:08:08,323 --> 00:08:10,780
fis-tabella hash int
probabbilment tmur jridu

174
00:08:10,780 --> 00:08:14,580
li tuża xi funzjoni li kien iġġenerat
għalik, li teżisti fuq l-internet.

175
00:08:14,580 --> 00:08:17,240
Jekk inti biss tkun ċert
li jiċċitaw sorsi tiegħek.

176
00:08:17,240 --> 00:08:21,740
M'hemm l-ebda raġuni biex
plagiarize xejn hawn.

177
00:08:21,740 --> 00:08:25,370
>> Il-komunità tax-xjenza tal-kompjuter hija
definittivament tikber, u verament valuri

178
00:08:25,370 --> 00:08:28,796
sors miftuħ, u huwa verament importanti
li jiċċitaw sorsi tiegħek sabiex in-nies

179
00:08:28,796 --> 00:08:30,670
jistgħu jiksbu attribuzzjoni għall
ix-xogħol li dawn qed

180
00:08:30,670 --> 00:08:32,312
tagħmel għall-benefiċċju tal-komunità.

181
00:08:32,312 --> 00:08:34,020
Allura dejjem tkun sure--
u mhux biss għall hash

182
00:08:34,020 --> 00:08:37,270
funzjonijiet, iżda ġeneralment meta inti
jużaw kodiċi minn sors barra,

183
00:08:37,270 --> 00:08:38,299
dejjem jiċċitaw sors tiegħek.

184
00:08:38,299 --> 00:08:43,500
Agħti kreditu lill-persuna li għamlet
xi xogħol sabiex inti ma għandekx.

185
00:08:43,500 --> 00:08:46,720
>> OK so ejja rriveduti dan
tabella hash għat-tieni.

186
00:08:46,720 --> 00:08:48,780
Dan huwa fejn aħna jitħalla
off wara we inserit

187
00:08:48,780 --> 00:08:53,300
John u Paul fis din it-tabella hash.

188
00:08:53,300 --> 00:08:55,180
Inti tara problema hawn?

189
00:08:55,180 --> 00:08:58,410
Inti tista 'tara tnejn.

190
00:08:58,410 --> 00:09:02,240
Iżda b'mod partikolari, do you
tara din il-problema?

191
00:09:02,240 --> 00:09:06,770
>> X'jiġri jekk I hash Ringo, u
Jirriżulta li wara l-ipproċessar

192
00:09:06,770 --> 00:09:14,000
li d-data permezz tal-funzjoni hash
Ringo iġġenerat ukoll l hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Stajt diġà kisbu data fil
post array hashcode-- 6.

194
00:09:16,810 --> 00:09:22,000
Allura huwa probabbilment se tkun daqsxejn
ta 'problema għalija issa, id-dritt?

195
00:09:22,000 --> 00:09:23,060
>> Aħna nsejħu dan ħabta.

196
00:09:23,060 --> 00:09:26,460
U l-ħabta ssir meta żewġ
biċċiet ta 'data jgħaddi mill-istess hash

197
00:09:26,460 --> 00:09:29,200
funzjoni jagħtu l-istess hashcode.

198
00:09:29,200 --> 00:09:32,850
Preżumibbilment aħna xorta rridu nġibu kemm
biċċiet ta 'data fit-tabella ta hash,

199
00:09:32,850 --> 00:09:36,330
inkella aħna mhux se tkun qed taħdem Ringo
arbitrarju permezz tal-funzjoni hash.

200
00:09:36,330 --> 00:09:40,870
Aħna preżumibbilment rridu nġibu
Ringo f'dak firxa.

201
00:09:40,870 --> 00:09:46,070
>> Kif nistgħu nagħmlu dan għalkemm, jekk hu
u Paul kemm rendiment hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Aħna ma rridux li jissostitwixxu Paul,
irridu Paul li jkun hemm wisq.

203
00:09:49,520 --> 00:09:52,790
Allura għandna bżonn issib mod biex jiksbu
elementi fit-tabella ta hash li

204
00:09:52,790 --> 00:09:56,550
xorta tippreserva quick tagħna
inserzjoni u malajr ħarsa up.

205
00:09:56,550 --> 00:10:01,350
U mod wieħed biex jittrattaw dan huwa li
jagħmel xi ħaġa imsejħa lineari probing.

206
00:10:01,350 --> 00:10:04,170
>> Meta tuża dan il-metodu jekk ikollna
kolliżjoni, ukoll, dak li nagħmlu?

207
00:10:04,170 --> 00:10:08,580
Well aħna ma tista 'tpoġġi lilu fil-post array
6, jew kwalunkwe hashcode ġie ġġenerat,

208
00:10:08,580 --> 00:10:10,820
ejja tpoġġi lilu fil hashcode flimkien ma '1.

209
00:10:10,820 --> 00:10:13,670
U jekk dan huwa sħiħa ta let
jniżżlu hashcode plus 2.

210
00:10:13,670 --> 00:10:17,420
Il-benefiċċju ta 'dan benessri jekk hu
mhux eżattament fejn naħsbu hu,

211
00:10:17,420 --> 00:10:20,850
u għandna nibdew tiftix,
forsi aħna ma jkollhom imorru wisq 'il bogħod.

212
00:10:20,850 --> 00:10:23,900
Forsi aħna ma jkollhomx biex tfittex
elementi kollha N tar-tabella hash.

213
00:10:23,900 --> 00:10:25,790
Forsi irridu tfittxija
ftit minnhom.

214
00:10:25,790 --> 00:10:30,680
>> U hekk aħna qed għadhom tendenza lejn
F'dak il-każ medja li huma qrib 1 vs

215
00:10:30,680 --> 00:10:34,280
qrib n, hekk forsi li ser jaħdmu.

216
00:10:34,280 --> 00:10:38,010
Mela ejja ara kif dan
jista 'jaħdem barra fir-realtà.

217
00:10:38,010 --> 00:10:41,460
U ejja ara jekk forsi nistgħu jikxfu
l-problema li tista 'sseħħ hawn.

218
00:10:41,460 --> 00:10:42,540
>> Ejja ngħidu aħna hash Bart.

219
00:10:42,540 --> 00:10:45,581
Allura issa aħna qed tmur biex imexxu sett ġdid
ta 'spag permezz tal-funzjoni hash,

220
00:10:45,581 --> 00:10:48,460
u aħna run Bart permezz tal-hash
funzjoni, irridu jiksbu hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Aħna tagħti ħarsa, naraw 6 huwa
vojta, hekk aħna tista 'tpoġġi Bart hemmhekk.

222
00:10:52,100 --> 00:10:55,410
>> Issa aħna hash Lisa u li
jiġġenera wkoll hashcode 6.

223
00:10:55,410 --> 00:10:58,330
Ukoll issa li aħna qed jużaw dan
lineari probing metodu nibdew fuq 6,

224
00:10:58,330 --> 00:10:59,330
naraw li 6 hija sħiħa.

225
00:10:59,330 --> 00:11:00,990
Aħna ma tista 'tpoġġi Lisa f'6.

226
00:11:00,990 --> 00:11:02,090
Għalhekk, fejn do we go?

227
00:11:02,090 --> 00:11:03,280
Ejja ħa mmorru sa 7.

228
00:11:03,280 --> 00:11:04,610
7 ta vojta, b'tali mod li jaħdem.

229
00:11:04,610 --> 00:11:06,510
Mela ejja tpoġġi Lisa hemmhekk.

230
00:11:06,510 --> 00:11:10,200
>> Issa aħna hash Homer u nikbru 7.

231
00:11:10,200 --> 00:11:13,380
OK ukoll nafu li 7 ta sħiħa
issa, hekk aħna ma tista 'tpoġġi Homer hemmhekk.

232
00:11:13,380 --> 00:11:14,850
Mela ejja mur 8.

233
00:11:14,850 --> 00:11:15,664
Huwa 8 disponibbli?

234
00:11:15,664 --> 00:11:18,330
Yeah, u qrib 8 għal 7, hekk jekk
għandna nibdew tiftix aħna qed

235
00:11:18,330 --> 00:11:20,020
mhux se jkollhom imorru wisq 'il bogħod.

236
00:11:20,020 --> 00:11:22,860
U hekk ejja tpoġġi Homer fi 8.

237
00:11:22,860 --> 00:11:25,151
>> Issa aħna hash Maggie u
prospetti 3, nirringrazzja goodness

238
00:11:25,151 --> 00:11:26,650
aħna kapaċi biss jitqiegħed Maggie hemmhekk.

239
00:11:26,650 --> 00:11:29,070
Aħna ma jkollhom jagħmlu xi
tip ta 'probing għal dan.

240
00:11:29,070 --> 00:11:32,000
Issa aħna hash Marge, u
Marge prospetti wkoll 6.

241
00:11:32,000 --> 00:11:39,560
>> Ukoll 6 hija sħiħa, 7 hija sħiħa, 8 hija sħiħa,
9, id-dritt nirringrazzjaw 'l Alla, 9 ikun vojt.

242
00:11:39,560 --> 00:11:41,600
I tista 'tpoġġi Marge fid-9.

243
00:11:41,600 --> 00:11:45,280
Diġà nistgħu naraw li aħna qed jibdew
li jkollhom din il-problema fejn issa aħna qed

244
00:11:45,280 --> 00:11:48,780
jibdew biex tistira affarijiet tip
tal bogħod minn kodiċi hash tagħhom.

245
00:11:48,780 --> 00:11:52,960
U li theta ta '1, dik il-medja
każ li jkun żmien kostanti,

246
00:11:52,960 --> 00:11:56,560
qed tibda tikseb more-- ftit
jibdew tendenza ftit aktar

247
00:11:56,560 --> 00:11:58,050
lejn theta ta n.

248
00:11:58,050 --> 00:12:01,270
Aħna qed jibdew jitilfu dak
vantaġġ ta 'tabelli hash.

249
00:12:01,270 --> 00:12:03,902
>> Din il-problema li aħna biss raw
hija xi ħaġa imsejħa clustering.

250
00:12:03,902 --> 00:12:06,360
U x'hemm tassew ħżiena dwar
clustering hija li ladarba inti issa

251
00:12:06,360 --> 00:12:09,606
żewġ elementi li qegħdin ħdejn
sekondarji jagħmilha saħansitra aktar probabbli,

252
00:12:09,606 --> 00:12:11,480
inti għandek doppju tal-
ċans, li int ser

253
00:12:11,480 --> 00:12:13,516
li jkollhom ħabta ieħor
ma 'dak cluster,

254
00:12:13,516 --> 00:12:14,890
u l cluster se tikber minn wieħed.

255
00:12:14,890 --> 00:12:19,640
U tkun taf jibqgħu jikbru u li qed jikber
probabbiltà tiegħek li jkollhom ħabta.

256
00:12:19,640 --> 00:12:24,470
U eventwalment huwa biss bħala ħżiena
ma issortjar id-dejta fil-livelli kollha.

257
00:12:24,470 --> 00:12:27,590
>> Il-problema l-oħra għalkemm hija aħna
xorta, u s'issa sa dan il-punt,

258
00:12:27,590 --> 00:12:30,336
aħna ħadthom biss ġew tip ta '
fehim dak tabella hash hija,

259
00:12:30,336 --> 00:12:31,960
aħna xorta jkollhom biss kamra għal 10 kordi.

260
00:12:31,960 --> 00:12:37,030
Jekk irridu li jkomplu hash
iċ-ċittadini ta Springfield,

261
00:12:37,030 --> 00:12:38,790
nistgħu biss jiksbu 10 minnhom fil hemmhekk.

262
00:12:38,790 --> 00:12:42,619
U jekk nippruvaw u żid 11 jew 12,
aħna ma jkollhomx post li jpoġġuhom.

263
00:12:42,619 --> 00:12:45,660
Nistgħu biss għażil madwar
ċrieki jippruvaw isibu post vojt,

264
00:12:45,660 --> 00:12:49,000
u aħna forsi jeħlu
fi loop infinita.

265
00:12:49,000 --> 00:12:51,810
>> Allura dan it-tip ta 'jsellef lill-idea
ta 'xi ħaġa imsejħa ikkatenar.

266
00:12:51,810 --> 00:12:55,790
U dan huwa fejn aħna qed tmur biex iġibu
listi marbuta lura fil-istampa.

267
00:12:55,790 --> 00:13:01,300
X'jiġri jekk minflok ħażna biss
id-data nnifisha fil-firxa,

268
00:13:01,300 --> 00:13:04,471
kull element tal-firxa tista
istiva biċċiet multipli ta 'data?

269
00:13:04,471 --> 00:13:05,970
Ukoll li ma jagħmilx sens, id-dritt?

270
00:13:05,970 --> 00:13:09,280
Aħna nafu li firxa tista 'biss
hold-- kull element ta 'firxa

271
00:13:09,280 --> 00:13:12,930
tista 'żżomm biss biċċa waħda
ta 'data ta' dak it-tip tad-data.

272
00:13:12,930 --> 00:13:16,750
>> Imma x'jiġri jekk dak it-tip tad-data
hija lista marbut, right?

273
00:13:16,750 --> 00:13:19,830
Allura dak jekk kull
element tad-firxa kienet

274
00:13:19,830 --> 00:13:22,790
a pointer lill-kap ta 'lista marbuta?

275
00:13:22,790 --> 00:13:24,680
U allura nistgħu nibnu
dawk il-listi marbuta

276
00:13:24,680 --> 00:13:27,120
u jikbru minnhom arbitrarju,
minħabba listi marbuta jippermettu

277
00:13:27,120 --> 00:13:32,090
ahna jikbru u tiċkien ħafna aktar
flessibbli minn firxa ma.

278
00:13:32,090 --> 00:13:34,210
Allura dak li jekk aħna issa jużaw,
aħna lieva dan, id-dritt?

279
00:13:34,210 --> 00:13:37,760
Aħna jibdew jikbru dawn il-ktajjen
minn dawn il-lokalitajiet array.

280
00:13:37,760 --> 00:13:40,740
>> Issa nistgħu tajbin infinita
ammont ta 'data, jew le infinita,

281
00:13:40,740 --> 00:13:44,170
ammont arbitrarja ta
data, in-mejda hash tagħna

282
00:13:44,170 --> 00:13:47,760
mingħajr qatt tmexxija fis
il-problema ta 'kolliżjoni.

283
00:13:47,760 --> 00:13:50,740
Imxejna wkoll eliminati
clustering billi tagħmel dan.

284
00:13:50,740 --> 00:13:54,380
U tajjeb nafu li meta aħna daħħal
fi lista marbuta, jekk inti recall

285
00:13:54,380 --> 00:13:57,779
mill-video tagħna fuq il-listi marbuta, weħidhom
listi konnessi u listi marbuta doppjament,

286
00:13:57,779 --> 00:13:59,070
huwa operazzjoni żmien kostanti.

287
00:13:59,070 --> 00:14:00,710
Aħna biss li jżid mal-front.

288
00:14:00,710 --> 00:14:04,400
>> U għall-ħarsa up, ukoll aħna nafu
li wieħed ifittex f'lista marbut

289
00:14:04,400 --> 00:14:05,785
tista 'tkun problema, id-dritt?

290
00:14:05,785 --> 00:14:07,910
Irridu tfittxija permezz
mill bidu sat-tmiem.

291
00:14:07,910 --> 00:14:10,460
M'hemm l-ebda każwali
aċċess f'lista marbuta.

292
00:14:10,460 --> 00:14:15,610
Iżda jekk minflok li wieħed marbut
lista fejn lookup tkun O ta 'n-

293
00:14:15,610 --> 00:14:19,590
issa għandna 10-listi marbuta,
jew 1,000 listi marbuta,

294
00:14:19,590 --> 00:14:24,120
issa huwa O ta 'n maqsum f'10,
jew O ta 'n diviż bil 1000.

295
00:14:24,120 --> 00:14:26,940
>> U filwaqt li konna nitkellmu
teoretikament dwar kumplessità

296
00:14:26,940 --> 00:14:30,061
aħna tinjora kostanti, fil-veru
dinja dawn l-affarijiet fil-fatt jimpurtax,

297
00:14:30,061 --> 00:14:30,560
id-dritt?

298
00:14:30,560 --> 00:14:33,080
Aħna fil-fatt se avviż
li dan jiġri

299
00:14:33,080 --> 00:14:36,610
biex imexxu 10 darbiet aktar mgħaġġla,
jew 1,000 darba aktar mgħaġġla,

300
00:14:36,610 --> 00:14:41,570
għaliex aħna qed iqassmu waħda twila
katina madwar 1,000 ktajjen iżgħar.

301
00:14:41,570 --> 00:14:45,090
U hekk kull darba irridu tfittxija
permezz ta 'waħda minn dawk il-ktajjen li nistgħu

302
00:14:45,090 --> 00:14:50,290
jinjora l-ktajjen 999 aħna ma jimpurtahom
dwar, u biss tfittxija li wieħed.

303
00:14:50,290 --> 00:14:53,220
>> Li bħala medja huwa li
jkun 1,000 darba iqsar.

304
00:14:53,220 --> 00:14:56,460
U hekk aħna xorta huma tip ta '
tendenza lejn dan il-każ medja

305
00:14:56,460 --> 00:15:01,610
li jkunu ħin kostanti, iżda
biss għaliex aħna qed jużaw

306
00:15:01,610 --> 00:15:03,730
diviż minn xi fattur kostanti enormi.

307
00:15:03,730 --> 00:15:05,804
Ejja naraw kif dan jista
fil-fatt tfittex għalkemm.

308
00:15:05,804 --> 00:15:08,720
Allura dan kien il-mejda hash kellna
qabel we ddikjarat tabella hash li

309
00:15:08,720 --> 00:15:10,270
kien kapaċi li jaħżen 10 kordi.

310
00:15:10,270 --> 00:15:11,728
Aħna mhux se tagħmel dan aktar.

311
00:15:11,728 --> 00:15:13,880
Aħna diġà jafu l-
limitazzjonijiet ta 'dak il-metodu.

312
00:15:13,880 --> 00:15:20,170
Issa tabella hash tagħna li għaddej biex tkun
firxa ta '10 nodi, pointers

313
00:15:20,170 --> 00:15:22,120
lill-kapijiet ta 'listi marbuta.

314
00:15:22,120 --> 00:15:23,830
>> U d-dritt issa huwa null.

315
00:15:23,830 --> 00:15:26,170
Kull waħda minn dawk il-10 pointers huwa null.

316
00:15:26,170 --> 00:15:29,870
M'hemm xejn fil tagħna
hash tabella dritt issa.

317
00:15:29,870 --> 00:15:32,690
>> Issa ejja nibdew li jqajjem xi
affarijiet fis din it-tabella hash.

318
00:15:32,690 --> 00:15:35,440
U ejja naraw kif dan il-metodu huwa
se jibbenefikaw us ftit.

319
00:15:35,440 --> 00:15:36,760
Ejja issa hash Joey.

320
00:15:36,760 --> 00:15:40,210
Aħna ser se titmexxa l string Joey permezz
funzjoni hash u nerġgħu lura 6.

321
00:15:40,210 --> 00:15:41,200
Well dak li nagħmlu issa?

322
00:15:41,200 --> 00:15:44,090
>> Ukoll issa li jaħdmu b'listi marbuta,
aħna mhux qed jaħdmu ma 'arrays.

323
00:15:44,090 --> 00:15:45,881
U meta aħna qed jaħdmu
ma 'listi marbuta aħna

324
00:15:45,881 --> 00:15:49,790
jafu jeħtieġ li nibdew dinamikament
allokazzjoni ta 'spazju u l-bini ktajjen.

325
00:15:49,790 --> 00:15:54,020
C'est tip ta 'how-- dawk huma l-qalba
elementi ta 'bini ta' lista marbuta.

326
00:15:54,020 --> 00:15:57,670
Mela ejja dinamiku
jalloka spazju għal Joey,

327
00:15:57,670 --> 00:16:00,390
u mbagħad ejja żid lilu għall-katina.

328
00:16:00,390 --> 00:16:03,170
>> Allura issa nħarsu dak li aħna ghamilt.

329
00:16:03,170 --> 00:16:06,440
Meta aħna hash Joey sirna l-hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Issa l-pointer fuq post firxa 6
jindika l-kap ta 'lista marbuta,

331
00:16:11,790 --> 00:16:14,900
u d-dritt issa huwa l-uniku
element ta 'lista marbuta.

332
00:16:14,900 --> 00:16:18,350
U l-node f'dak
Lista marbuta hija Joey.

333
00:16:18,350 --> 00:16:22,300
>> Mela jekk irridu li wieħed ifittex Joey
wara, aħna biss hash Joey mill-ġdid,

334
00:16:22,300 --> 00:16:26,300
nikbru 6 mill-ġdid minħabba tagħna
funzjoni hash hija deterministic.

335
00:16:26,300 --> 00:16:30,400
U allura aħna tibda fil-ras
tal-lista marbuta osservat

336
00:16:30,400 --> 00:16:33,360
mill-post array
6, u nistgħu jtenni

337
00:16:33,360 --> 00:16:35,650
madwar li jippruvaw isibu Joey.

338
00:16:35,650 --> 00:16:37,780
U jekk aħna nibnu tagħna
hash tabella effettiv,

339
00:16:37,780 --> 00:16:41,790
u l-funzjoni hash tagħna b'mod effettiv
li jiddistribwixxu data tajjeb,

340
00:16:41,790 --> 00:16:45,770
fuq medja kull wieħed minn dawk marbuta
listi f'kull post array

341
00:16:45,770 --> 00:16:50,110
se jkun 1/10-daqs ta 'jekk irridu
biss kellhom bħala enormi wieħed

342
00:16:50,110 --> 00:16:51,650
lista marbuta ma 'kollox fiha.

343
00:16:51,650 --> 00:16:55,670
>> Jekk aħna jiddistribwixxu li marbuta enormi
Lista madwar 10 listi marbuta

344
00:16:55,670 --> 00:16:57,760
kull lista se jkun 1/10-daqs.

345
00:16:57,760 --> 00:17:01,432
U b'hekk 10 darbiet aktar mgħaġġla
li tfittex.

346
00:17:01,432 --> 00:17:02,390
Mela ejja tagħmel dan mill-ġdid.

347
00:17:02,390 --> 00:17:04,290
Ejja issa hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> U ejja ngħidu Ross, meta nagħmlu dan
il-kodiċi tal-hash nikbru lura huwa ta '2.

349
00:17:07,540 --> 00:17:10,630
Ukoll issa aħna dinamikament jallokaw
node ġdid, npoġġux Ross f'dak node,

350
00:17:10,630 --> 00:17:14,900
u aħna ngħidu issa lokazzjoni firxa
2, minflok tipponta lejn null,

351
00:17:14,900 --> 00:17:18,579
jindika l-kap ta 'marbut
lista li node biss huwa Ross.

352
00:17:18,579 --> 00:17:22,660
U nistgħu nagħmlu dan wieħed aktar ħin, aħna
jistgħu hash Rachel u jiksbu hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc node ġdid, tpoġġi Rachel fil
l node, u jgħidu post array

354
00:17:25,490 --> 00:17:27,839
4 issa juri l-kap
ta 'lista marbuta li

355
00:17:27,839 --> 00:17:31,420
biss element jiġri li jkun Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK imma x'jiġri jekk
għandna ħabta?

357
00:17:33,470 --> 00:17:38,560
Ejja naraw kif aħna nittrattaw ħabtiet
użu tal-metodu chaining separata.

358
00:17:38,560 --> 00:17:39,800
Ejja hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Irridu jiksbu l-hashcode 6.

360
00:17:41,094 --> 00:17:44,010
Fl-eżempju preċedenti tagħna aħna kienu biss
ħażna tal-kordi fl-array.

361
00:17:44,010 --> 00:17:45,980
Din kienet problema.

362
00:17:45,980 --> 00:17:48,444
>> Aħna ma rridux li clobber
Joey, u konna diġà

363
00:17:48,444 --> 00:17:51,110
jidher li nistgħu nikseb xi raggruppament
problemi jekk nippruvaw u pass

364
00:17:51,110 --> 00:17:52,202
permezz ta 'u sonda.

365
00:17:52,202 --> 00:17:54,660
Imma dak jekk aħna biss tip ta '
jittratta dan l-istess mod, id-dritt?

366
00:17:54,660 --> 00:17:57,440
Huwa biss bħal żieda ta 'element
lill-kap ta 'lista marbuta.

367
00:17:57,440 --> 00:18:00,220
Ejja ispazju biss malloc għall Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Aħna ser jgħidu punti Phoebe tal pointer li jmiss
lill-kap antika tal-lista marbuta,

369
00:18:04,764 --> 00:18:07,180
u mbagħad 6 biss juri l-
kap il-ġdid tal-lista marbuta.

370
00:18:07,180 --> 00:18:10,150
U issa nħarsu, konna inbidlet Phoebe in.

371
00:18:10,150 --> 00:18:14,210
Aħna issa jista 'jaħżen tnejn
elementi li hashcode 6,

372
00:18:14,210 --> 00:18:17,170
u aħna ma jkollhom xi problemi.

373
00:18:17,170 --> 00:18:20,147
>> Li pretty ħafna kollha
hemm biex chaining.

374
00:18:20,147 --> 00:18:21,980
U chaining huwa definittivament
il-metodu li l-

375
00:18:21,980 --> 00:18:27,390
ser ikunu aktar effettivi għalik jekk
inti qed jaħżnu data fit-tabella hash.

376
00:18:27,390 --> 00:18:30,890
Iżda din il-kombinazzjoni ta '
arrays u listi marbuta

377
00:18:30,890 --> 00:18:36,080
flimkien biex jiffurmaw tabella hash verament
drammatiku ittejjeb l-abbiltà tiegħek

378
00:18:36,080 --> 00:18:40,550
li jaħżnu ammonti kbar ta 'data, u
malajr ħafna u b'mod effiċjenti tfittxija

379
00:18:40,550 --> 00:18:41,630
permezz ta 'dak id-data.

380
00:18:41,630 --> 00:18:44,150
>> Hemm għadu wieħed aktar
istruttura tad-data hemmhekk

381
00:18:44,150 --> 00:18:48,700
li jista 'anke jkun daqsxejn
aħjar f'termini ta 'garanzija ta

382
00:18:48,700 --> 00:18:51,920
li inserzjoni tagħna, tħassir, u
tfittex up ħinijiet huma aktar malajr.

383
00:18:51,920 --> 00:18:55,630
U aħna ser tara li fil-video fuq jipprova.

384
00:18:55,630 --> 00:18:58,930
Jien Doug Lloyd, dan huwa CS50.

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