[MUSIC PLAYING]
>> DOUG LLOYD: 陌ndi siz Diziler haqq谋nda 莽ox bilm蓹k,
v蓹 ba臒l谋 siyah谋lar谋 haqq谋nda bir 莽ox bilirik.
V蓹 biz m眉zakir蓹 etdik lehte ve eksiklikleri, biz
siyah谋lar谋 ba臒l谋 ki, m眉zakir蓹 b枚y眉k v蓹 ki莽ik 蓹ld蓹 ed蓹 bil蓹rsiniz,
lakin onlar daha 枚l莽眉s眉 almaq.
Diziler daha sad蓹 var istifad蓹, lakin onlar q蓹d蓹r m蓹hdudla艧d谋r谋c谋 ist蓹yirik
biz 枚l莽眉s眉n眉 t蓹yin etm蓹k kimi 莽ox ba艧谋nda array
sonra biz il蓹 vurulmu艧 edirik.
>> Amma ki, biz olduqca 莽ox var var, Bizim m枚vzular b眉t眉n can谋
ba臒l谋 siyah谋lar谋 v蓹 Diziler haqq谋nda.
Yoxsa biz var?
B蓹lk蓹 biz bir 艧ey ed蓹 bil蓹rsiniz daha yarad谋c谋.
V蓹 verir ki, sort bir hash masa ideyas谋.
>> Bel蓹 ki, bir hash masa biz c蓹hd olacaq bir ba臒l谋 siyah谋 il蓹 bir s谋ra birl蓹艧dirir.
Biz 眉st眉nl眉kl蓹ri olacaq serial谋n, t蓹sad眉fi giri艧 kimi,
yaln谋z array getm蓹k 眉莽眉n qadir olan element 4 v蓹 ya array element 8
眉zr蓹 t蓹krarlamaq olmadan.
Bu do臒ru, olduqca s眉r蓹tli var?
>> Amma biz d蓹 m蓹lumatlar var ist蓹yir蓹m strukturu inki艧af v蓹 shrink ed蓹 bil蓹rsiniz.
Biz deyil, ehtiyac yoxdur m蓹hdudla艧d谋r谋lacaq ist蓹yirik.
V蓹 biz etm蓹k ist蓹yir蓹m 蓹lav蓹 v蓹 h蓹r 艧eyi aradan qald谋r谋lmas谋 眉莽眉n
莽ox asanl谋qla, siz geri 蓹g蓹r, bir s谋ra il蓹 莽ox m眉r蓹kk蓹bdir.
V蓹 biz bu z蓹ng ed蓹 bil蓹rsiniz yeni bir 艧ey bir hash masa.
>> 茝g蓹r d眉zg眉n t蓹tbiq biz n枚v alaraq edirik
h蓹m d蓹 m蓹lumatlar谋n 眉st眉nl眉kl蓹ri 茝g蓹r siz art谋q g枚rd眉m strukturlar谋,
Diziler v蓹 ba臒l谋 siyah谋lar谋.
Taxmaq ba艧laya bil蓹rsiniz 1 teta do臒ru edirl蓹r.
Theta biz, h蓹qiq蓹t蓹n, m眉zakir蓹 deyil, lakin teta yaln谋z orta oldu臒u,
n蓹 h蓹qiq蓹t蓹n ba艧 ver蓹c蓹k.
Siz h蓹mi艧蓹 fikrind蓹 deyilik 蓹n pis halda ssenari var,
v蓹 h蓹mi艧蓹 fikrind蓹 deyilik 茝n yax艧谋 ssenari, bel蓹 ki, n蓹 var
orta ssenari?
>> Yax艧谋 bir orta durub bir hash masa
yax谋n daimi vaxt almaq 眉莽眉n ba艧laya bil蓹rsiniz.
V蓹 silinm蓹si 蓹ld蓹 ed蓹 bil蓹rsiniz daimi zaman ba臒lay谋n.
V蓹 Sistemi 蓹ld蓹 ed蓹 bil蓹rsiniz daimi zaman ba臒lay谋n.
That bir m蓹lumat yoxdur strukturu h蓹l蓹 ki, bunu ed蓹 bil蓹rsiniz,
v蓹 bu, art谋q s蓹sl蓹r olduqca b枚y眉k 艧ey kimi.
Biz, h蓹qiq蓹t蓹n, yum艧ald谋lmas谋na etdik 枚z h蓹r m蓹nfi c蓹h蓹tl蓹ri.
>> Bu performans谋 almaq 眉莽眉n , baxmayaraq ki biz t蓹kmill蓹艧dirm蓹k
biz 蓹lav蓹 n蓹 yenid蓹n etm蓹k laz谋md谋r strukturu data.
X眉susil蓹 biz ist蓹yirik data 枚z眉 biz蓹
harada strukturunda getm蓹lidir.
V蓹 biz o var g枚rmek 眉莽眉n laz谋md谋r, 蓹g蓹r strukturu, biz tapmaq laz谋md谋r,
biz m蓹lumatlar谋n baxmaq ist蓹yir蓹m yenid蓹n v蓹 s蓹m蓹r蓹li ed蓹 bil蓹r,
veri istifad蓹 ed蓹r蓹k, t蓹sad眉fi daxil.
Just baxaraq data biz olmal谋d谋r
m蓹hz biz oldu臒unuz bir fikir hash masa tapmaq 眉莽眉n gedir.
>> Bir hash 陌ndi 陌艧in m蓹nfi t蓹r蓹fi odur masa h蓹qiq蓹t蓹n ist蓹yirik ki,
sifari艧 v蓹 ya data 莽e艧idl蓹nm蓹si olduqca pis.
V蓹 蓹slind蓹, siz ba艧lamaq 蓹g蓹r sifari艧 v蓹 ya sort 眉莽眉n onlara istifad蓹 etm蓹k
data b眉t眉n itirm蓹k 眉st眉nl眉kl蓹ri 蓹vv蓹ll蓹r
durub v蓹 silinm蓹si bax谋m谋ndan idi.
vaxt yax谋n olur n teta, v蓹 biz 蓹sas蓹n var
bir ba臒l谋 siyah谋s谋na daxil geril蓹di.
V蓹 bel蓹 ki, biz yaln谋z hash istifad蓹 etm蓹k ist蓹diyiniz masalar biz qay臒谋 yoxdur, 蓹g蓹r
data 莽e艧idl蓹nir olub.
Kontekstind蓹 olan CS50 onlar谋 istifad蓹 ed蓹c蓹yik
Siz y蓹qin ki, qay臒谋 yoxdur data 莽e艧idl蓹nir ki.
>> Bel蓹 ki, bir hash table bir birl蓹艧m蓹sidir iki f蓹rqli 蓹d蓹d
olan biz tan谋艧 edirik.
ilk funksiyas谋 olan biz ad蓹t蓹n bir hash funksiyas谋 z蓹ng.
V蓹 hash funksiyas谋 gedir , b蓹zi qeyri-m蓹nfi tam qay谋tmaq hans谋
biz ad蓹t蓹n OK, bir hashcode z蓹ng?
ikinci par莽a bir s谋ra edir tipli biz saxlan谋lmas谋 m蓹lumatlar谋n bil蓹n
data strukturu yerl蓹艧dirm蓹k ist蓹yir蓹m.
Biz off ke莽irm蓹k laz谋md谋r 陌ndi siyah谋s谋 element ba臒l谋d谋r
v蓹 yaln谋z bir 蓹saslar谋 il蓹 ba艧lamaq onun 蓹traf谋nda ba艧 almaq 眉莽眉n masa hash,
sonra biz b蓹lk蓹 z蓹rb蓹 olacaq fikrinizi bir az zaman
birlikd蓹 Diziler v蓹 link siyah谋lar谋 birl蓹艧dirir.
>> 蓹sas fikir olsa b蓹zi m蓹lumatlar谋 almaq deyil.
Biz data vasit蓹sil蓹 run hash funksiyas谋.
V蓹 bel蓹 data emal v蓹 OK, bir s谋ra spits?
V蓹 sonra say谋 biz yaln谋z veri
biz saxlamaq ist蓹yir蓹m ki, yeri array.
Bel蓹 ki, m蓹s蓹l蓹n, biz b蓹lk蓹 var strings bu hash masa.
Bu, bel蓹 ki, bu 10 elementl蓹r var biz onu 10 strings uy臒un bil蓹r.
>> Biz John hash ist蓹yir蓹m deyirl蓹r.
John Bel蓹 ki, data kimi biz 蓹lav蓹 etm蓹k ist蓹yir蓹m haradasa bu hash masa.
Harada biz qoymaq bil蓹r蓹m?
Yax艧谋 ad蓹t蓹n il蓹 array g眉n蓹 q蓹d蓹r biz y蓹qin ki,
array yeri 0 onu qoymaq olard谋.
Amma indi biz bu yeni hash funksiyas谋 var.
>> V蓹 biz John run ki, bildirin Bu hash funksiyas谋 vasit蓹sil蓹
v蓹 4 spits oldu.
Biz oldu臒unuz yax艧谋 ki var John qoymaq ist蓹yir蓹m olacaq.
Biz array yeri Y蓹hya qoymaq ist蓹yir蓹m 4, biz again-- John hash, 莽眉nki
nin sonra biz dey蓹k axtar谋艧 v蓹 g枚rm蓹k ist蓹yirik
John bu hash varsa biz n蓹 etm蓹k laz谋md谋r b眉t眉n Masa
Eyni hash vasit蓹sil蓹 idar蓹 olunur funksiyas谋, say谋 4 莽谋xmaq
v蓹 John tapa bil蓹c蓹kl蓹r d蓹rhal data strukturu.
Bu olduqca yax艧谋.
>> Biz indi bunu deyirl蓹r yen蓹 biz Paulun hash ist蓹yirik.
Biz Paul 蓹lav蓹 etm蓹k ist蓹diyiniz Bu hash masa.
Bu d蓹f蓹 biz run deyirl蓹r Hash funksiyas谋 vasit蓹sil蓹 Paul,
yarad谋lan hashcode 6.
Yax艧谋 indi biz Paul qoya bil蓹r array yeri 6.
V蓹 biz olmad谋臒谋n谋 baxmaq laz谋md谋r Paul bu hash masa var,
biz n蓹 etm蓹k laz谋md谋r b眉t眉n Paul run hash funksiyas谋 vasit蓹sil蓹 yenid蓹n
v蓹 biz yen蓹 6 almaq olacaq.
>> V蓹 sonra biz yaln谋z baxmaq array yeri 6.
Paul varm谋?
茝g蓹r bel蓹dirs蓹, o, hash masa var.
Paul yoxdur?
O, hash c蓹dv蓹ld蓹 deyil.
Bu olduqca sad蓹.
>> 陌ndi nec蓹 bir hash funksiyas谋 m眉蓹yy蓹n edirsiniz?
Yax艧谋 h蓹qiq蓹t蓹n he莽 bir limit var m眉mk眉n hash funksiyalar谋n谋n say谋.
茝slind蓹 bir s谋ra h蓹qiq蓹t蓹n var internet, h蓹qiq蓹t蓹n, yax艧谋 olanlar谋.
Bir s谋ra h蓹qiq蓹t蓹n var internet, h蓹qiq蓹t蓹n, pis olanlar谋.
O, h蓹m莽inin olduqca asand谋r pis bir yazmaq.
>> Bel蓹 ki, n蓹 bir yax艧谋 t蓹艧kil edir hash funksiyas谋, sa臒?
Yax艧谋 yax艧谋 hash funksiyas谋 olmal谋d谋r yaln谋z data hashed olunur istifad蓹,
v蓹 m蓹lumatlar谋n b眉t眉n hashed olunur.
Bel蓹likl蓹, biz anything-- istifad蓹 etm蓹k ist蓹mir蓹m biz bir 艧ey daxil deyil
data ba艧qa ba艧qa.
Biz data b眉t眉n istifad蓹 etm蓹k ist蓹yirik.
Biz yaln谋z bir par莽a istifad蓹 etm蓹k ist蓹mir蓹m bu, biz bunu b眉t眉n istifad蓹 etm蓹k ist蓹yirik.
A hash funksiyas谋 olmal谋d谋r d蓹 deterministic olun.
Bunun m蓹nas谋 n蓹dir?
Yax艧谋 o dem蓹kdir ki, h蓹r d蓹f蓹 biz m蓹lumatlar谋n eyni par莽a ke莽m蓹k
hash funksiyas谋 daxil biz h蓹mi艧蓹 Eyni hashcode 莽谋xmaq.
M蓹n daxil John ke莽m蓹k 蓹g蓹r hash funksiyas谋 M蓹n 4 莽谋xmaq.
M蓹n bunu etm蓹k laz谋md谋r 10,000 d蓹f蓹 v蓹 m蓹n h蓹mi艧蓹 4 almaq laz谋md谋r.
Bel蓹 ki, he莽 t蓹sad眉fi n枚mr蓹l蓹ri s蓹m蓹r蓹li Bizim hash c蓹lb edil蓹 bil蓹r tables--
Bizim hash funksiyalar谋.
>> A hash funksiyas谋 da olmal谋d谋r uniformly m蓹lumat yaymaq.
H蓹r zaman vasit蓹sil蓹 m蓹lumat 莽al谋艧t谋r谋yorsan谋z hash funksiyas谋, hashcode 0 almaq
do臒ru, y蓹qin ki, o q蓹d蓹r d蓹 b枚y眉k deyil?
Siz y蓹qin ki, b枚y眉k ist蓹yir蓹m hash kodlar谋 bir s谋ra.
H蓹m莽inin 艧eyi yay谋lm谋艧d谋r bil蓹r masa 蓹rzind蓹 h蓹yata.
V蓹 h蓹m莽inin, 蓹g蓹r h蓹qiq蓹t蓹n b枚y眉k olacaq John v蓹 Yonatan kimi ox艧ar m蓹lumatlar,
b蓹lk蓹 莽蓹kin yay谋lm谋艧d谋r edildi hash c蓹dv蓹ld蓹 m眉xt蓹lif yerl蓹rd蓹.
Ki, bir g枚z蓹l 眉st眉nl眉y眉 olacaq.
>> Burada hash funksiyas谋 bir misal var.
M蓹n 蓹vv蓹ll蓹r bu bir q蓹d蓹r yazd谋.
Bu x眉susil蓹 deyil yax艧谋 hash funksiyas谋
h蓹qiq蓹t蓹n, yoxdur s蓹b蓹bl蓹r蓹 g枚r蓹 陌ndi ged蓹n da艧谋y谋rlar.
Amma burada n蓹 olub g枚r眉rs眉n眉z?
Biz bir d蓹yi艧蓹n elan edirik kimi g枚r眉n眉r m蓹bl蓹臒i v蓹 0-a b蓹rab蓹r q蓹bulu 莽a臒谋r谋b.
V蓹 sonra y蓹qin m蓹n bir 艧ey edir蓹m bel蓹 uzun strstr [j] b蓹rab蓹r deyil
0 backslash 眉莽眉n.
M蓹n orada n蓹 edir蓹m?
>> Bu 蓹sas蓹n yaln谋z ba艧qa [h蓹yata ke莽irilm蓹si yolu? Strl?]
Siz var zaman a艧kar simli sona g蓹lindi.
Bel蓹 ki, M蓹n, h蓹qiq蓹t蓹n, yoxdur simli uzunlu臒u hesablamaq,
M蓹n hit zaman m蓹n yaln谋z istifad蓹 edir蓹m backslash 0 xarakter bilir蓹m
M蓹n simli sonunda 蓹ld蓹 etdiyiniz.
V蓹 sonra m蓹n saxlamaq 眉莽眉n gedir蓹m ki, simli vasit蓹sil蓹 iterating,
strstr [j] 蓹lav蓹 sonra yekunla艧d谋rmaq, v蓹 G眉n眉n sonunda m蓹bl蓹臒i mod geri olacaq
HASH_MAX.
>> 茝sas蓹n b眉t眉n bu hash funksiyas谋 蓹lav蓹 olunur edir
ASCII d蓹y蓹rl蓹ri b眉t眉n M蓹nim string, sonra var
b蓹zi hashcode qaytar谋lmas谋 HASH_MAX t蓹r蓹find蓹n modded.
Bu y蓹qin ki, 枚l莽眉s眉 var M蓹nim serial谋n, sa臒?
M蓹n hash 蓹ld蓹 etm蓹k ist蓹mir蓹m kodlar谋 m蓹nim array 枚l莽眉s眉 10 olduqda,
M蓹n 蓹ld蓹 olmaq ist蓹mir蓹m h蓹yata hash kodlar谋 11, 12,
13, m蓹n daxil 艧eyi qoymaq bilm蓹z serial谋n o locations,
ki, qeyri-qanuni ola bil蓹r.
M蓹n bir seqmentasiya g眉nah 蓹ziyy蓹t ediyorum.
>> 陌ndi burada bir s眉r蓹tli k蓹nara edir.
脺mumiyy蓹tl蓹 siz y蓹qin ki, fikrind蓹 deyilik 枚z hash funksiyalar谋 yazmaq ist蓹yir蓹m.
Bu, h蓹qiq蓹t蓹n bir az bir s蓹n蓹t, bir elm.
Onlar谋n gider bir 莽ox var.
Dediyim kimi internet, tam h蓹qiq蓹t蓹n yax艧谋 hash funksiyalar谋,
v蓹 internet istifad蓹 etm蓹lidir Bu, h蓹qiq蓹t蓹n, 莽眉nki hash funksiyalar谋 tapmaq
yaln谋z c眉r g蓹r蓹ksiz vaxt itkisi 枚z yaratmaq.
>> Siz sad蓹 olanlar谋 yaza bil蓹rsiniz m蓹qs蓹dl蓹ri test 眉莽眉n.
Amma 蓹slind蓹 ged蓹n zaman m蓹lumat hashing v蓹 saxlan谋lmas谋 ba艧lamaq
Siz bu hash masa y蓹qin ki, ist蓹yir蓹m olacaq
istehsal edilmi艧dir b蓹zi funksiyadan istifad蓹 etm蓹k Sizin 眉莽眉n ki, internet m枚vcuddur.
Yaln谋z 蓹min olun deyils蓹 Sizin m蓹nb蓹l蓹ri istinad.
He莽 bir s蓹b蓹b 眉莽眉n var burada bir 艧ey plagiarize.
>> informatika icma edir m眉tl蓹q d蓹y蓹rl蓹r artan v蓹 h蓹qiq蓹t蓹n
a莽谋q m蓹nb蓹 v蓹 bu, h蓹qiq蓹t蓹n vacibdir Sizin m蓹nb蓹l蓹ri istinad ki, insanlar
眉莽眉n attribution 蓹ld蓹 ed蓹 bil蓹rsiniz onlar i艧
c蓹miyy蓹tin xeyrin蓹 edirik.
Bel蓹 ki, h蓹mi艧蓹 sure-- ola v蓹 yaln谋z hash 眉莽眉n
funksiyalar谋, lakin 眉mumiyy蓹tl蓹 zaman bir k蓹narda m蓹nb蓹d蓹n kodu istifad蓹,
h蓹mi艧蓹 m蓹nb蓹 istinad.
Etdi 艧蓹xs蓹 kredit verm蓹k i艧 b蓹zi bel蓹 yoxdur.
>> OK, bel蓹 ki, bu yenid蓹n ed蓹k ikinci hash masa.
Biz sol yerdir biz daxil sonra
Bu hash masa John v蓹 Paul.
Burada bir problem g枚r眉rs眉n眉zm眉?
Siz iki g枚r蓹 bil蓹rsiniz.
Amma x眉susil蓹, siz Bu m眉mk眉n problem g枚rm蓹k?
>> M蓹n Ringo hash v蓹 蓹g蓹r sonra emal 莽谋x谋r ki,
hash funksiyas谋 vasit蓹sil蓹 data Ringo d蓹 hashcode 6 yarad谋lan.
M蓹n art谋q data var hashcode-- array yeri 6.
Bel蓹 ki, y蓹qin ki, bir az olacaq 陌ndi m蓹nim 眉莽眉n bir problem, sa臒?
>> Biz toqqu艧ma 莽a臒谋r谋r谋q.
V蓹 toqqu艧ma iki ba艧 verir m蓹lumatlar谋n 蓹d蓹d eyni hash vasit蓹sil蓹 run
funksiyas谋 eyni hashcode verir.
Ehtimal biz h蓹l蓹 d蓹 almaq ist蓹yir蓹m hash masa m蓹lumatlar谋n 蓹d蓹d,
蓹ks halda biz Ringo 莽al谋艧an olmaz 枚zba艧谋na hash funksiyas谋 vasit蓹sil蓹.
Biz ehtimalla almaq ist蓹yir蓹m Ki array daxil Ringo.
>> Biz baxmayaraq bunu nec蓹, o, 蓹g蓹r v蓹 Paul, h蓹m d蓹 g蓹lir hashcode 6?
Biz Paul yazmaq ist蓹mir蓹m, biz Paul orada olmaq ist蓹yir蓹m.
Bel蓹likl蓹, biz almaq 眉莽眉n bir yol tapmaq laz谋md谋r hash masa elementl蓹ri ki
h蓹l蓹 bizim s眉r蓹tli qoruyur durub v蓹 g枚z at谋n谋z up.
V蓹 onunla m蓹艧臒ul bir yol var probing x蓹tti deyil蓹n bir 艧ey yoxdur.
>> Bir varsa, bu metodu istifad蓹 ed蓹r蓹k toqqu艧ma, yax艧谋, biz n蓹 etm蓹liy蓹m?
Yax艧谋 array yeri onu qoymaq bilm蓹z 6, v蓹 ya h蓹r hans谋 hashcode istehsal edilmi艧dir,
nin hashcode plus 1 onu qoymaq bildirin.
V蓹 tam ed蓹k, 蓹g蓹r hashcode plus 2 onu qoydu.
Bu varl谋臒谋n fayda o 蓹g蓹r tam biz o hesab edir蓹m oldu臒u,
v蓹 biz axtar谋艧 ba艧lamaq 眉莽眉n, b蓹lk蓹 biz 莽ox uzaq getm蓹k yoxdur.
B蓹lk蓹 biz axtar谋艧 yoxdur hash masa b眉t眉n n elementl蓹ri.
B蓹lk蓹 biz axtar谋艧 Onlar谋n bir ne莽蓹.
>> V蓹 bel蓹 ki, biz h蓹l蓹 do臒ru meyl edirik orta i艧i 1 yax谋n vs gedir
n yax谋n, bel蓹 ki, b蓹lk蓹 ki, i艧l蓹m蓹k laz谋md谋r.
Bel蓹 ki, nec蓹 bu g枚r蓹k 蓹slind蓹 i艧 bil蓹r.
V蓹 b蓹lk蓹 biz a艧kar ed蓹 bil蓹rsiniz 蓹g蓹r in g枚r蓹k Burada ba艧 ver蓹 bil蓹r problem.
>> Biz Bart hash deyirl蓹r.
Bel蓹 ki, indi biz yeni bir s谋ra 莽al谋艧t谋rmak olacaq hash funksiyas谋 vasit蓹sil蓹 strings,
v蓹 biz hash vasit蓹sil蓹 Bart谋n run funksiyas谋, biz hashcode 6 almaq.
Biz bir n蓹z蓹r, biz 6 g枚rm蓹k bo艧, bel蓹 ki, biz orada Bart bil蓹r.
>> 陌ndi biz Lisa v蓹 hash d蓹 hashcode 6 yarad谋r.
Yax艧谋 indi biz bu istifad蓹 etdiyiniz ki, x蓹tti, biz 6-da ba艧layacaq metodu yoxlama臒a
biz 6 dolu oldu臒unu g枚r眉r眉k.
Biz 6 Lisa qoymaq bilm蓹z.
Bel蓹likl蓹, biz getm蓹k yoxdur?
7 ged蓹k.
7-nin bo艧, bel蓹 i艧l蓹yir.
Bel蓹 ki, orada Lisa qoymaq bildirin.
>> 陌ndi biz Homer hash v蓹 7 almaq.
OK, biz bilirik 7-nin tam ki, 陌ndi, bel蓹 ki, biz orada Homer qoymaq bilm蓹z.
Bel蓹 ki, 8 ged蓹k.
8 bil蓹r?
B蓹li, v蓹 7 8 yax谋n, bel蓹 ki, 蓹g蓹r Biz ist蓹yirik axtar谋艧 ba艧lamaq 眉莽眉n
莽ox uzaq getm蓹k 眉莽眉n var niyy蓹tind蓹 deyil.
V蓹 bel蓹 ki, 8 Homer qoymaq bildirin.
>> 陌ndi biz hash Maggie v蓹 3 qaytar谋r 艧眉k眉r
biz yaln谋z orada Maggie qoymaq ist蓹yirik.
Biz he莽 n蓹 yoxdur sort ki yoxlama臒a.
陌ndi biz Marge hash v蓹 Marge d蓹 6 qaytar谋r.
>> Yax艧谋 6, 8 dolu, 7 tam, tam 9, b眉t眉n sa臒 9 bo艧, Allaha 艧眉k眉r.
M蓹n 9 Marge bil蓹r.
Onsuz da biz ba艧lan臒谋c etdiyiniz g枚r蓹 bil蓹rsiniz biz ist蓹yirik indi bu problem
c眉r 艧eyi uzan谋r ba艧lay谋r uzaq onlar谋n hash kodlar谋.
V蓹 1 ki teta ki, orta daimi vaxt olan halda,
bir az more-- almaq 眉莽眉n ba艧lay谋r bir az daha meyli ba艧layaraq
n teta do臒ru.
Biz ki, itirm蓹k 眉莽眉n ba艧lan臒谋c edirik hash masalar 眉st眉nl眉y眉.
>> Biz yaln谋z g枚rd眉m bu problem klasterl蓹艧m蓹 deyil蓹n bir 艧ey var.
V蓹 h蓹qiq蓹t蓹n pis n蓹 var klasterl蓹艧m蓹 ki, sizin bir d蓹f蓹 indi
yan iki elementl蓹ri il蓹 var bu, daha 莽ox edir yan,
Siz ikiqat 艧ans, siz olacaq
ba艧qa toqqu艧ma var ki 莽oxluq il蓹,
v蓹 cluster biri artacaq.
V蓹 artan v蓹 artan saxlamaq laz谋md谋r bir toqqu艧ma olan sizin ehtimal谋.
V蓹 n蓹tic蓹d蓹 bu kimi pis kimi b眉t眉n m蓹lumatlar谋n 莽e艧idl蓹nm蓹si deyil.
>> dig蓹r problem olsa biz h蓹l蓹 v蓹 bu g眉n蓹 q蓹d蓹r bu n枚qt蓹y蓹 q蓹d蓹r,
biz yaln谋z n枚v oldum bir hash table n蓹 anlama,
biz h蓹l蓹 yaln谋z 10 strings 眉莽眉n otaq var.
Biz hash davam etm蓹k ist蓹yirsinizs蓹, Springfield v蓹t蓹nda艧lar谋,
biz yaln谋z orada onlardan 10 蓹ld蓹 ed蓹 bil蓹rsiniz.
V蓹 biz c蓹hd v蓹 bir 11-ci v蓹 ya 12 蓹lav蓹 biz onlar谋 qoymaq 眉莽眉n bir yer yoxdur.
Biz yaln谋z 蓹traf谋nda iplik bil蓹r dair蓹l蓹r, bo艧 spot tapmaq 眉莽眉n 莽al谋艧谋r谋q
v蓹 biz b蓹lk蓹 tak谋l谋yorum sonsuz loop.
>> Bel蓹 ki, fikir verir bu c眉r bir 艧ey chaining 莽a臒谋r谋b.
V蓹 bu g蓹tirm蓹k olacaq harada geri 艧蓹kil ba臒l谋 siyah谋lar谋.
N蓹 蓹v蓹zin蓹 yaln谋z saxlan谋lmas谋 array data 枚z眉,
serial谋n h蓹r element bil蓹r 莽ox 蓹d蓹d m蓹lumatlar谋n ke莽ir蓹c蓹k?
Yax艧谋 ki, sa臒 m蓹nada etmir?
Biz ki, bir s谋ra yaln谋z bilirik bir s谋ra h蓹r bir element hold--
yaln谋z bir par莽a a莽a bil蓹r ki, data n枚v眉 m蓹lumatlar谋n.
>> Amma n蓹 蓹g蓹r data type bir ba臒l谋 siyah谋 sa臒, var?
Bel蓹 ki, n蓹 蓹g蓹r h蓹r serial谋n element idi
bir ba臒l谋 siyah谋 r蓹hb蓹ri bir g枚st蓹rici?
V蓹 sonra biz qurmaq bil蓹r bu ba臒l谋 siyah谋lar谋
v蓹 枚zba艧谋na onlar谋n inki艧af ba臒l谋 siyah谋lar谋 imkan verir, 莽眉nki
Biz蓹 inki艧af v蓹 daha 莽ox shrink bir s谋ra edir 莽evik 莽ox.
Bel蓹 ki, n蓹 biz indi istifad蓹 蓹g蓹r, biz do臒ru, bu leverage?
Biz bu z蓹ncirl蓹r inki艧af ba艧lamaq bu array yerl蓹rd蓹 h蓹yata.
>> 陌ndi biz sonsuz uy臒un data m蓹bl蓹臒i, v蓹 ya sonsuz deyil,
bir ixtiyari m蓹bl蓹臒i data, bizim hash masa
He莽 daxil 莽al谋艧an olmadan Toqqu艧man谋n problem.
Biz d蓹 aradan sonra bu etm蓹kl蓹 klasterl蓹艧m蓹.
V蓹 biz biz daxil zaman bilirik ki, bir ba臒l谋 siyah谋s谋na daxil, siz geri 蓹g蓹r
story ba臒l谋 siyah谋lar谋 bizim video ba臒l谋 siyah谋lar谋 v蓹 ikiqat ba臒l谋 siyah谋lar谋,
bu, daimi vaxt 蓹m蓹liyyat var.
Biz yaln谋z 枚n 蓹lav蓹 edirik.
>> V蓹 baxmaq q蓹d蓹r, biz bilirik ki, bir ba臒l谋 siyah谋s谋nda baxmaq
sa臒, bir problem ola bil蓹r?
Biz vasit蓹sil蓹 axtar谋艧 蓹vv蓹ld蓹n sona.
He莽 bir t蓹sad眉fi var bir ba臒l谋 siyah谋 giri艧.
Amma 蓹g蓹r 蓹v蓹zin蓹 bir olan ba臒l谋 bir axtar谋艧 n Ey olard谋 siyah谋s谋
biz indi 10 ba臒l谋 siyah谋lar谋 var, v蓹 ya 1000 ba臒l谋 siyah谋lar谋,
indi 10 b枚l眉n眉r n O var, v蓹 ya n O 1000 b枚l眉n眉r.
>> V蓹 biz s枚hb蓹t is蓹 n蓹z蓹ri m眉r蓹kk蓹bliyi haqq谋nda
biz real, sabitl蓹ri ard谋 bunlar h蓹qiq蓹t蓹n m蓹s蓹l蓹 d眉nya,
sa臒?
Biz, h蓹qiq蓹t蓹n, g枚r蓹c蓹ksiniz bu olur ki,
daha s眉r蓹tli 10 d蓹f蓹 莽al谋艧t谋rmak 眉莽眉n, v蓹 ya 1000 d蓹f蓹 daha s眉r蓹tli,
biz uzun bir paylayaraq, 莽眉nki 1000 ki莽ik z蓹ncirl蓹r aras谋nda z蓹ncir.
V蓹 bel蓹 ki, biz h蓹r zaman axtarmaq 眉莽眉n biz o z蓹ncirl蓹r biri il蓹
biz qay臒谋 yoxdur 999 z蓹ncirl蓹r ignore haqq谋nda, v蓹 yaln谋z bir axtar谋艧.
>> Hans谋 orta edir 1000 d蓹f蓹 q谋sa ola bil蓹r.
V蓹 bel蓹 ki, biz h蓹l蓹 sort var Bu orta halda do臒ru baxma
daimi vaxt olan, lakin yaln谋z biz yararlanarak, 莽眉nki
b蓹zi b枚y眉k daimi amil b枚l眉nm蓹si.
Bu nec蓹 ola bil蓹r Baxaq h蓹qiq蓹t蓹n baxmayaraq baxmaq.
Bel蓹 ki, bu biz idi hash table idi bir hash masa elan 蓹vv蓹l
10 strings saxlan谋lmas谋 qadir idi.
Biz art谋q bunu etm蓹k fikrind蓹 deyilik.
Biz art谋q bilirik ki, metodu m蓹hdudiyy蓹tl蓹r.
陌ndi bizim hash table olacaq 10 qov艧aqlar谋n谋n, g枚st蓹ricil蓹r bir s谋ra
ba臒l谋 siyah谋lar谋 r蓹hb蓹rl蓹rin蓹.
>> V蓹 indi bu null.
Bu 10 g枚st蓹ricil蓹r h蓹r bir null edir.
He莽 bir 艧ey bizim var var 陌ndi masa hash.
>> 陌ndi b蓹zi qoymaq ba艧lamaq ed蓹k Bu hash masa 艧eyl蓹r.
V蓹 bu 眉sul nec蓹 ed蓹k Biz蓹 bir az fayda gedir.
陌ndi Joey hash ed蓹k.
Biz simli Joey vasit蓹sil蓹 davam ed蓹c蓹k laz谋md谋r bir hash funksiyas谋 v蓹 biz 6 qay谋tmaq.
Yax艧谋 indi n蓹 etm蓹liy蓹m?
>> Yax艧谋 indi ba臒l谋 siyah谋lar谋 il蓹 i艧, biz seriallar谋n il蓹 i艧 deyilik.
V蓹 biz 莽al谋艧谋r谋q zaman ba臒l谋 siyah谋lar谋 il蓹 biz
biz dinamik ba艧lamaq laz谋md谋r bilirik space v蓹 tikinti z蓹ncirl蓹r b枚l眉艧d眉r眉lm蓹si.
Ki, sort o 蓹sas var how-- var bir ba臒l谋 siyah谋 bina elementl蓹ri.
Bel蓹 ki, dinamik ed蓹k Joey 眉莽眉n yerin ayr谋lmas谋,
V蓹 sonra z蓹ncir ona 蓹lav蓹 ed蓹k.
>> Bel蓹 ki, indi biz etdik n蓹 baxmaq.
Biz Joey hash zaman hashcode 6 var.
Array yeri 6 陌ndi pointer bir ba臒l谋 siyah谋 ba艧谋 g枚st蓹rir,
v蓹 indi yaln谋z var bir ba臒l谋 siyah谋 element.
V蓹 ki, node ba臒l谋 siyah谋 Joey edir.
>> Biz Joey baxmaq laz谋md谋r, bel蓹 ki, sonra, biz yaln谋z yenid蓹n Joey hash,
biz bizimdir bizim 莽眉nki yenid蓹n 6 almaq hash funksiyas谋 deterministic edir.
V蓹 sonra biz ba艧-da ba艧layacaq ba臒l谋 siyah谋 i艧ar蓹
array yeri il蓹 6 v蓹 biz t蓹krarlamaq bil蓹r
Joey tapmaq 眉莽眉n 莽al谋艧谋r谋q ki, rast.
V蓹 biz qurmaq bizim s蓹m蓹r蓹li masa hash,
v蓹 hash funksiyas谋 s蓹m蓹r蓹li yax艧谋 m蓹lumat yaymaq,
orta hesabla o h蓹r ba臒l谋 h蓹r array yerd蓹 siyah谋lar谋
蓹g蓹r 枚l莽眉s眉 1/10 olacaq biz yaln谋z bir b枚y眉k kimi idi
bu h蓹r 艧eyi il蓹 ba臒l谋 siyah谋s谋.
>> Biz b枚y眉k ba臒l谋 oldu臒unu yaymaq 10 ba臒l谋 siyah谋lar谋 aras谋nda siyah谋s谋
H蓹r bir siyah谋 1/10 枚l莽眉s眉 olacaq.
V蓹 bel蓹likl蓹 10 d蓹f蓹 daha s眉r蓹tli vasit蓹sil蓹 axtar谋艧.
Bel蓹 ki, bir daha bunu ed蓹k.
陌ndi Ross hash ed蓹k.
>> V蓹 biz bunu zaman Ross, dey蓹k biz geri almaq hash kodu 2.
Yax艧谋 indi biz dinamik bir ayr谋lmas谋 yeni node, biz ki, node Ross qoymaq
v蓹 biz array yer indi dem蓹k 2 null i艧ar蓹 蓹v蓹zin蓹,
bir ba臒l谋 r蓹hb蓹ri g枚st蓹rir yegan蓹 node siyah谋s谋 Ross edir.
V蓹 biz, biz bu d蓹f蓹 daha ed蓹 bil蓹rsiniz Rachel hash v蓹 hashcode 4 蓹ld蓹 ed蓹 bil蓹rsiniz.
Rachel qoymaq, yeni node malloc node v蓹 array yeri dem蓹k
4 indi ba艧 i艧ar蓹 Onun bir ba臒l谋 siyah谋
yaln谋z element Rachel olmaq olur.
>> OK lakin n蓹 olur biz bir toqqu艧ma var?
Biz toqqu艧ma idar蓹 nec蓹 g枚rm蓹k ed蓹k ayr谋-ayr谋 chaining metodundan istifad蓹.
Nin Phoebe hash ed蓹k.
Biz hashcode 6 almaq.
茝vv蓹lki n眉mun蓹d蓹 biz yaln谋z idi serialda strings saxlan谋lmas谋.
Bu bir problem idi.
>> Biz d枚ym蓹k ist蓹mir蓹m Joey, v蓹 biz art谋q var
b蓹zi klasterl蓹艧m蓹 蓹ld蓹 ed蓹 bil蓹rsiniz ki, g枚rd眉k probleml蓹rini c蓹hd v蓹 add谋m
vasit蓹sil蓹 v蓹 sonda.
Amma n蓹 蓹g蓹r biz yaln谋z n枚v bu h眉quqa eyni 艧蓹kild蓹 m眉alic蓹?
Bu, sad蓹c蓹 bir element 蓹lav蓹 kimi bir ba臒l谋 siyah谋 r蓹hb蓹ri.
Phoebe 眉莽眉n yaln谋z malloc yer ed蓹k.
>> Biz Phoebe n枚vb蓹ti pointer xal dem蓹k laz谋md谋r ba臒l谋 siyah谋 k枚hn蓹 r蓹hb蓹ri,
v蓹 sonra 6 yaln谋z i艧ar蓹 ba臒l谋 siyah谋 yeni r蓹hb蓹ri.
陌ndi biz Phoebe d蓹yi艧dirdik, baxmaq.
Biz indi iki bil蓹rsiniz hashcode 6 elementl蓹ri,
v蓹 h蓹r hans谋 bir problem yoxdur.
>> Olduqca 莽ox b眉t眉n var z蓹ncirl蓹m蓹 var.
V蓹 chaining m眉tl蓹q deyil metodu
蓹g蓹r 眉莽眉n 蓹n effektiv olacaq Bir hash masa m蓹lumatlar谋n saxlan谋lmas谋 olunur.
Amma bu birl蓹艧m蓹si Diziler v蓹 ba臒l谋 siyah谋lar谋
birlikd蓹 h蓹qiq蓹t蓹n bir hash masa yaratmaq 眉莽眉n dramatik sizin qabiliyy蓹tini art谋r谋r
m蓹lumatlar谋n b枚y眉k h蓹cmd蓹 saxlamaq, v蓹 莽ox tez v蓹 s蓹m蓹r蓹li axtar谋艧
ki, data vasit蓹sil蓹.
>> Bir daha h蓹l蓹 var Orada data structure
ki, h蓹tta bir az ola bil蓹r, t蓹min bax谋m谋ndan daha yax艧谋
ki, bizim durub, silinm蓹si, v蓹 yuxar谋 baxmaq d蓹f蓹 daha s眉r蓹tli edir.
V蓹 biz 莽al谋艧谋r bir video g枚r蓹c蓹ksiniz.
M蓹n Doug Lloyd deyil蓹m, bu CS50 edir.