[Muzika]
>> DOUG Lloyd: Deri tani ju dinë shumë rreth vargjeve,
dhe ju e dini shumë për listat e lidhura.
Dhe ne kemi diskutuar pro dhe kundra, ne kemi
diskutuar se lidhur listat mund të merrni më të mëdha dhe të vogla,
por ata kërkojnë më shumë madhësinë.
Vargjeve janë shumë më të hapur për të përdorin, por ata janë të kufizuar në sa më shumë
si ne kemi për të vendosur madhësinë e array në fillim
dhe pastaj ne jemi të mbërthyer me të.
>> Por kjo është, ne kemi shumë e shumë shteruar të gjitha temat tona
në lidhje me listat e lidhura dhe vargjeve.
Apo kemi?
Ndoshta ne mund të bëjmë diçka edhe më shumë krijues.
Dhe kjo lloj i jep hua ideja e një tabelë hash.
>> Pra, në një tabelë hash ne jemi duke shkuar për të provoni të kombinuar një grup me një listë të lidhura.
Ne jemi duke shkuar për të marrë avantazhet e array, si qasje të rastit,
qenë në gjendje të thjesht shkoni në grup element 4 ose grup element 8
pa pasur nevojë për të iterate nëpër.
Kjo është shumë e shpejtë, e drejtë?
>> Por ne gjithashtu duam të kemi të dhënat tona Struktura të jetë në gjendje të rritet dhe tkurret.
Ne nuk kemi nevojë, ne nuk e bëjmë duan të jenë të kufizuara.
Dhe ne duam të jetë në gjendje të shtoni dhe hiqni gjërat
shumë lehtë, e cila në qoftë se ju kujtohet, është shumë komplekse me një grup.
Dhe ne mund ta quajmë këtë gjë e re një tabelë hash.
>> Dhe në qoftë se zbatohet si duhet, ne jemi lloj i marrjes
avantazhet e të dy të dhënave Strukturat e keni parë tashmë,
vargjeve dhe listat lidhura.
Futje mund të fillojnë të priren drejt theta e 1.
Theta ne nuk kemi diskutuar me të vërtetë, por theta është vetëm rasti mesatare,
çfarë është në të vërtetë do të ndodhë.
Ju nuk jeni gjithmonë do të kanë skenarin më të keq,
dhe ju nuk jeni gjithmonë do të ketë skenari më i mirë, kështu që çfarë është
skenari mesatar?
>> E pra një futje mesatare në një tabelë hash
mund të filloni për të marrë afër në kohë të vazhdueshme.
Dhe fshirje mund të merrni mbyllur në kohë të vazhdueshme.
Dhe lookup mund të merrni mbyllur në kohë të vazhdueshme.
That's-- ne nuk kemi një të dhënave Struktura ende se mund ta bëjë këtë,
dhe kështu që kjo tashmë tingëllon si një gjë mjaft e madhe.
Ne kemi zbutet vërtetë disavantazhet e secilit më vete.
>> Për të marrë këtë performancë përmirësuar edhe pse, ne
duhet të mendonin se si ne shtoni të dhënat në strukturën.
Në mënyrë të veçantë ne dëshironi vetë të dhënat për të na tregoni
ku ajo duhet të shkojë në strukturën.
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ë,
ne duam të shikojmë në të dhënat e përsëri dhe të jenë në gjendje që në mënyrë efektive,
duke përdorur të dhënat, rastësisht të hyrë në të.
Vetëm duke shikuar në të dhëna ne duhet të kemi
një ide e ku pikërisht ne jemi do të gjeni atë në tabelë hash.
>> Tani dobësitë e një hash tabelë është se ata janë me të vërtetë
shumë e keqe në urdhërimin ose klasifikim të dhënave.
Dhe në fakt, nëse ju filloni të përdorin ato për të porositur ose lloj
të dhëna ju humbni të gjitha të Përparësitë ju më parë
kishte në aspektin e futje dhe fshirje.
Koha bëhet më afër theta e n, dhe ne kemi në thelb
ngecur në një listë të lidhura.
Dhe kështu që ne vetëm dëshironi të përdorni hash tavolina, nëse ne nuk e kujdesit në lidhje me
nëse të dhënat është e renditura.
Për kontekstin në të cilin ju do të përdorin ato në CS50
ju ndoshta nuk e kujdesit se të dhënat është e renditura.
>> Pra, një tabelë hash është një kombinim nga dy pjesë të dallueshme
me të cilat ne jemi të njohur.
I parë është një funksion, e cila ne zakonisht e quajmë një funksion hash.
Dhe kjo funksion hash do të kthehen disa numër i plotë jo-negativ, i cili
ne zakonisht e quajmë një hashcode, OK?
Pjesa e dytë është një grup, i cili është të aftë për magazinimin e të dhënave të tipit ne
doni të vendosni në strukturën e të dhënave.
Ne do të mbajë jashtë në anën lidhur element listë për tani
dhe të fillojë vetëm me bazat e një hash tryezë për të marrë kokën tuaj rreth tij,
dhe pastaj ne do të ndoshta goditje mendjen tuaj pak kur ne
kombinohen vargjeve dhe listat lidhur së bashku.
>> Ideja themelore pse është që ne të marrë disa të dhëna.
Ne të drejtuar se të dhënat përmes funksioni hash.
Dhe kështu të dhënat janë përpunuar dhe ajo pështyn nga një numër, në rregull?
Dhe pastaj me atë numër ne vetëm të ruajtur të dhënat
ne duam të ruajtur në array në atë vend.
Kështu për shembull, ne kemi ndoshta kjo tabelë hash e strings.
Ajo ka 10 elemente në të, kështu që ne mund të përshtatet 10 vargjet në të.
>> Le të themi se duam të hash Gjoni.
Pra, Gjoni si të dhëna ne duam të futur në këtë tabelë hash diku.
Ku nuk kemi vënë atë?
E pra në mënyrë tipike me një array deri tani ne ndoshta
do të vënë atë në vend array 0.
Por tani ne kemi këtë funksion të ri hash.
>> Dhe le të themi se kemi drejtuar Gjoni përmes këtij funksioni hash
dhe kjo është pështyn nga 4.
E pra kjo është ajo ku ne jemi do të duan të vënë Gjoni.
Ne duam të vënë Gjonin në vend array 4, sepse në qoftë se ne të hash Gjoni again--
le të themi më vonë ne doni të kërkoni dhe të shohin
nëse John ekziston në këtë hash table-- të gjithë ne duhet të bëjmë
është drejtuar atë nëpërmjet të njëjtin hash funksion, të marrë numrin 4 nga,
dhe të jetë në gjendje për të gjetur Gjoni menjëherë në strukturën e të dhënave tonë.
Kjo është shumë e mirë.
>> Le të themi se tani bëjmë këtë përsëri, ne duam të hash Palin.
Ne duam të shtoni Palin në këtë tabelë hash.
Le të themi se këtë herë kemi drejtuar Pali përmes funksionit hash,
hashcode që është krijuar është 6.
E pra tani ne mund të vënë Palin në array vend të 6.
Dhe në qoftë se ne duhet të shohim lart nëse Pali është në këtë tabelë hash,
të gjithë ne duhet të bëni është të drejtuar Paul përmes funksionit hash përsëri
dhe ne jemi duke shkuar për të marrë 6 jashtë përsëri.
>> Dhe atëherë ne vetëm shikoni në array vend të 6.
Paul atje?
Nëse është kështu, ai është në tabelën hash.
Paul nuk ka?
Ai nuk është në tabelën hash.
Është shumë i thjeshtë.
>> Tani si mund të përcaktojë një funksion hash?
E pra nuk ka të vërtetë nuk ka kufi të Numri i funksioneve të mundshme hash.
Në fakt ka një numër të vërtetë, ato me të vërtetë të mira në internet.
Ka një numër të vërtetë, ato me të vërtetë të këqija në internet.
Është gjithashtu shumë e lehtë për të shkruar një të keqe.
>> Pra, çfarë e bën një të mirë funksion hash, e drejtë?
Edhe një funksion të mirë hash duhet përdorin vetëm të dhënat që janë sheshuar,
dhe të gjitha të dhënave të sheshuar.
Pra, ne nuk duam të përdorni anything-- ne nuk përfshijnë ndonjë gjë
tjetër përveç të dhënave.
Dhe ne duam të përdorim të gjitha të dhënave.
Ne nuk duam që të përdorni vetëm një copë e saj, ne duam të përdorim të gjithë atë.
Një funksion hash duhet të jetë gjithashtu determinist.
Cfare do te thote ajo?
E pra kjo do të thotë se çdo herë kemi kalojë të njëjtën pjesë e saktë e të dhënave
në funksion hash ne gjithmonë merrni të njëjtën hashcode jashtë.
Nëse unë kaloj Gjonin në të funksion hash unë dal 4.
Unë duhet të jetë në gjendje të bëjë atë 10,000 herë dhe unë gjithmonë do të merrni 4.
Kështu që nuk ka numra të rastit në mënyrë efektive mund të përfshihen në hash tonë tables--
në funksionet tona të hash.
>> Një funksion hash duhet gjithashtu uniforme shpërndarjen e të dhënave.
Në qoftë se çdo herë që të drejtuar të dhënat përmes funksion hash ju merrni hashcode 0,
kjo ndoshta nuk është aq e madhe, apo jo?
Ju ndoshta dëshironi të mëdha një varg i kodeve hash.
Edhe gjërat mund të përhapet nga të gjithë në tryezë.
Dhe gjithashtu kjo do të jetë i madh në qoftë se me të vërtetë të dhëna të ngjashme, si Gjoni dhe Jonathanin,
ndoshta janë shtrirë për të peshojnë vende të ndryshme në tabelë hash.
Kjo do të jetë një avantazh i bukur.
>> Ja një shembull i një funksion hash.
Kam shkruar këtë një të tillë më herët.
Kjo nuk është një veçanërisht i Funksioni i mirë hash
për arsye që nuk të vërtetë mbajnë shkon në të drejtë tani.
Por ju e shihni se çfarë po ndodh këtu?
Duket sikur ne jemi duke deklaruar një ndryshore quhet shuma e vendosur atë të barabartë me 0.
Dhe pastaj me sa duket unë jam duke bërë diçka për aq kohë sa strstr [j] nuk është i barabartë
për backslash 0.
Çfarë po bëj këtu?
>> Kjo është në thelb vetëm një tjetër Mënyra e zbatimit të [? strl?]
dhe zbulimin kur ju keni arritur në fund të vargut.
Kështu që unë nuk duhet të vërtetë të të llogaritur gjatësinë e vargut,
Unë jam vetëm duke përdorur, kur unë goditi backslash 0 karakter di
Unë e kam arritur në fund të vargut.
Dhe atëherë unë jam duke shkuar për të mbajtur iterating nëpër atë varg,
duke shtuar strstr [J] për të përmbledhur, dhe pastaj në fundi i ditës do të kthehen shuma mod
HASH_MAX.
>> Në thelb të gjithë kësaj hash Funksioni është duke bërë është duke shtuar deri
të gjithë nga vlerat e ASCII string im, dhe atëherë është
kthyer disa hashcode modded nga HASH_MAX.
Kjo është ndoshta e madhësisë e array tim, e drejtë?
Unë nuk dua të jetë marrë hash Kodet nëse array ime është e madhësisë 10,
Unë nuk dua të jetë marrë Kodet jashtë hash 11, 12,
13, unë nuk mund të vënë gjërat në këto vende e vektorit,
që do të jetë i paligjshëm.
Unë do të vuajnë një defekt segmentimit.
>> Tani këtu është një tjetër i shpejtë mënjanë.
Në përgjithësi ju jeni ndoshta nuk do të dua të shkruaj funksionet e veta hash tuaja.
Kjo është në fakt një grimë një art, jo një shkencë.
Dhe ka shumë që shkon në to.
Interneti, si i tha, është e plotë i funksioneve të vërtetë të mirë hash,
dhe ju duhet të përdorni internetin për gjeni funksionet hash, sepse është e vërtetë
vetëm lloj i një të panevojshme humbje e kohës për të krijuar tuaj.
>> Ju mund të shkruani ato të thjeshta për qëllime testimi.
Por kur ju të vërtetë do të të fillojë hashing të dhënave dhe ruajtjen atë
në një tabelë hash ju jeni ndoshta do të doni
të përdorin një funksion që është gjeneruar për ju, që ekziston në internet.
Nëse ju bëni të vetëm të jetë i sigurt të përmendin burimet tuaja.
Nuk ka asnjë arsye për të bëj plagjiaturë asgjë këtu.
>> Komuniteti shkenca kompjuterike është definitivisht në rritje, dhe me të vërtetë vlerat
burim të hapur, dhe kjo është me të vërtetë e rëndësishme të citojnë burimet tuaja në mënyrë që njerëzit
mund të merrni atribuim për puna që ata janë
duke bërë për të mirën e komunitetit.
Pra, të jetë gjithmonë sure-- dhe jo vetëm për hash
funksionet, por në përgjithësi, kur ju përdorni kodin nga një burim i jashtëm,
gjithmonë citojnë burimin tuaj.
Japin kredi për personin i cili bëri disa të punës kështu që ju nuk keni për të.
>> OK kështu që le të rishqyrtojnë këtë tabelë hash për një të dytë.
Kjo është ajo ku kemi lënë off pas ne futur
John dhe Paul në këtë tabelë hash.
A ke parë një problem këtu?
Ju mund të shihni dy.
Por në veçanti, a shohin këtë problem të mundshëm?
>> Çka nëse unë hash Ringo, dhe ajo rezulton se pas përpunimit
që të dhënat me anë të funksionit hash Ringo gjithashtu gjeneruar hashcode 6.
Unë kam marrë tashmë të dhënave në hashcode-- array vendndodhjen 6.
Pra, kjo ndoshta do të jetë pak e një problemi për mua tani, apo jo?
>> Ne e quajmë këtë një përplasje.
Dhe përplasja ndodh kur dy pjesë e të dhënave të drejtuar nëpër të njëjtën hash
Funksioni i japin të njëjtën hashcode.
Me sa duket ne ende duan të marrin dy pjesë e të dhënave në tabela hash,
përndryshe ne nuk do të konkurrojnë Ringo në mënyrë arbitrare përmes funksionit hash.
Ne me sa duket duan të marrin Ringo në atë grup.
>> Si nuk kemi të bëjmë atë edhe pse, në qoftë se ai dhe Pali dyja jepnin hashcode 6?
Ne nuk duam të prishësh Palin, ne duam Pali të jenë atje.
Pra, ne kemi nevojë për të gjetur një mënyrë për të marrë Elementet në tryezë hash që
ende ruan Quick tonë futje dhe të shpejtë të kërkoni.
Dhe një mënyrë për t'u marrë me të është që të të bëjë diçka të quajtur lineare probing.
>> Duke përdorur këtë metodë në qoftë se ne kemi një përplasje, mirë, çfarë bëjmë ne?
E pra ne nuk mund ta vënë atë në vend array 6, ose çfarëdo hashcode u gjenerua,
le të vënë atë në hashcode plus 1.
Dhe nëse kjo është e plotë let vënë atë në hashcode plus 2.
Përfitimi i kësaj qenieje, nëse ai është jo saktësisht ku ne mendojmë se është,
dhe ne kemi për të filluar kërkimin, Ndoshta ne nuk kemi për të shkuar shumë larg.
Ndoshta ne nuk kemi për të kërkuar të gjitha elementet n e tabelës hash.
Ndoshta ne duhet të kërkoni disa prej tyre.
>> Dhe kështu që ne jemi ende duke tentuar drejt se rasti mesatare duke qenë afër 1 vs
afër n, kështu që ndoshta që do të punojnë.
Pra, le të shohim se si kjo mund të punojnë jashtë në realitet.
Dhe le të shohim nëse ndoshta ne mund të zbulojë problemi që mund të ndodhë këtu.
>> Le të themi se të hash Bart.
Pra, tani ne jemi duke shkuar për të drejtuar një seri të re e tela përmes funksionit hash,
dhe ne të drejtuar Bart me anë të hash funksion, ne kemi marrë hashcode 6.
Ne kemi marrë një sy, ne shohim 6 është bosh, kështu që ne mund të vënë Bart atje.
>> Tani ne hash Lisa dhe se gjithashtu gjeneron hashcode 6.
E pra tani që ne jemi duke përdorur këtë linear probing metodë ne të fillojë në 6,
ne shohim se 6 është e plotë.
Ne nuk mund të vënë Lisa në 6.
Pra, ku do të shkojmë?
Le të shkojnë në 7.
7 e bosh, kështu që punon.
Pra, le të vënë Lisa atje.
>> Tani ne hash Homerit dhe ne të merrni 7.
OK edhe ne e dimë se 7 e plotë tani, kështu që ne nuk mund të vënë Homerit atje.
Pra, le të shkojë në 8.
Është 8 në dispozicion?
Po, dhe afër 8-të 7, kështu që nëse ne kemi për të filluar kërkimin jemi
nuk do të ketë për të shkuar shumë larg.
Dhe kështu le të vënë Homerit në 8.
>> Tani ne hash Maggie dhe kthehet 3, lavdi zotit
ne jemi në gjendje për të vetëm të vënë Maggie atje.
Ne nuk duhet të bëjmë ndonjë lloj probing për atë.
Tani ne hash Marge, dhe Marge gjithashtu kthehet 6.
>> 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.
Unë mund të vënë Marge në 9.
Tashmë ne mund të shohim se ne jemi duke filluar që të ketë këtë problem, ku tani ne jemi
filluar të shtrihet gjërat lloj e larg nga kodet e tyre hash.
Dhe që theta nga 1, që mesatarja rast për të qenë kohë konstante,
ka filluar të marrë një more-- vogël duke filluar për të tentojnë pak më shumë
drejt theta të n.
Ne jemi duke filluar për të humbur atë Përparësia e tabelave hash.
>> Ky problem që ne vetëm e pa është diçka e quajtur clustering.
Dhe çfarë është me të vërtetë keq për clustering është se sapo ju tani
kanë dy elemente që janë krah për anën kjo e bën atë edhe më shumë të ngjarë,
ju keni të dyfishtë mundësi, se ju do të jeni
të ketë një tjetër përplasje me këtë grup,
dhe grup do të rritet nga një.
Dhe ju do të vazhdojë të rritet dhe të rritet mundësia juaj për të pasur një përplasje.
Dhe në fund ajo është po aq e keqe si mos zgjidhja e të dhënave në të gjitha.
>> Problemi tjetër edhe pse është ne ende, dhe deri më tani deri në këtë pikë,
ne kemi qenë vetëm lloj i kuptuar se çfarë një tabelë hash është,
ne ende vetëm kanë vend për 10 strings.
Në qoftë se ne duam të vazhdojmë të hash qytetarët e Springfield,
ne mund të merrni vetëm 10 prej tyre në atje.
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.
Ne vetëm mund të jetë tjerrje rreth në qarqet duke u përpjekur për të gjetur një vend bosh,
dhe ne ndoshta merrni mbërthyer në një lak të pafund.
>> Pra, ky lloj i jep hua për idesë e diçka të quajtur chaining.
Dhe kjo është ajo ku ne jemi duke shkuar për të sjellë Listat e lidhura prapa në foto.
Çfarë nëse në vend të ruajtjen vetëm të dhënat vetë në grup,
çdo element i vektorit mund të të mbajë pjesë të shumta e të dhënave?
E pra kjo nuk ka kuptim, apo jo?
Ne e dimë se një grup mund të vetëm hold-- çdo element të një sërë
mund të mbajë vetëm një pjesë e të dhënave të atij lloji të dhënave.
>> Por çfarë nëse kjo lloj e të dhënave është një listë e lidhur, e drejtë?
Pra, çfarë nëse çdo element i vektorit ishte
një tregues në krye të listës të lidhura?
Dhe pastaj ne mund të ndërtojmë këto listat lidhura
dhe rriten ata në mënyrë arbitrare, sepse listat lidhura lejojë
ne të rritet dhe tkurret shumë më tepër fleksibilitet se një grup bën.
Pra, çfarë nëse ne tani përdorin, ne levave kjo, apo jo?
Ne fillojmë të rriten këto zinxhirët nga këto vende array.
>> Tani ne mund të përshtatet një infinit Shuma e të dhënave, apo jo pafund,
një sasi arbitrare të të dhënave, në tryezën tonë hash
pa ndonjëherë drejtimin në problemi i përplasjes.
Ne kemi eliminuar edhe clustering duke bërë këtë.
Dhe ne e dimë mirë se kur ne të futur në një listë të lidhura, në qoftë se ju kujtohet
nga video tonë në listat e lidhura, veçmas Listat e lidhura dhe listat lidhura dyfish,
kjo është një operacion i vazhdueshëm kohë.
Ne jemi vetëm duke shtuar në pjesën e përparme.
>> Dhe për look up, edhe ne e dimë që shikoni në një listë të lidhura
mund të jetë një problem, e drejtë?
Ne duhet të kërkoni përmes ajo nga fillimi në fund.
Nuk ka asnjë mënyrë të rastësishme qasje në një listë të lidhura.
Por në qoftë se në vend të paturit e një të tillë lidhur Lista ku një lookup do të jetë o të n,
ne tani kemi 10 listave të lidhura, ose 1.000 listat lidhura,
tani është o n i ndarë nga 10, ose o të n ndarë nga 1,000.
>> Dhe, ndërsa ne ishim duke folur teorikisht në lidhje me kompleksitetin
ne mosrespektimi konstante, në reale Bota këto gjëra në fakt rëndësi,
e drejtë?
Ne fakt do të vini re se kjo ndodh
për të kandiduar 10 herë më të shpejtë, ose 1000 herë më shpejt,
sepse ne jemi shpërndarjen e gjatë zinxhir nëpër 1000 zinxhirët më të vogla.
Dhe kështu çdo herë që ne kemi për të kërkuar përmes një prej këtyre zinxhirëve ne mund të
injorojnë 999 zinxhirët ne nuk e kujdesit në lidhje me, dhe kërko vetëm se një.
>> E cila është mesatarisht për të jetë 1,000 herë më të shkurtër.
Dhe kështu që ne ende jemi të lloj duke tentuar drejt këtë rast mesatare
për të qenë kohë të vazhdueshme, por vetëm për shkak se ne jemi leveraging
duke e ndarë nga një faktor i madh konstante.
Le të shohim se si kjo mund të në fakt duken pse.
Pra, ky ishte tabelë hash kemi pasur para se të deklaruar një tabelë hash që
ishte i aftë për ruajtjen 10 strings.
Ne nuk jemi duke shkuar për të bërë atë më.
Ne tashmë e dimë Kufizimet e kësaj metode.
Tani tabelën tonë hash do të jetë një grup prej 10 nyjet, pointers
të krerëve të listave të lidhura.
>> Dhe tani kjo është null.
Secili prej këtyre 10 pointers është i pavlefshëm.
Nuk ka asgjë në tonë hash tryezë tani.
>> Tani le të fillojë për të vënë disa gjërat në këtë tabelë hash.
Dhe le të shohim se si kjo metodë është do të na përfituar pak.
Le tani të hash Joey.
Ne do të do të kandidojë string Joey përmes një funksion hash dhe do të kthehemi 6.
E pra çfarë bëjmë ne tani?
>> E pra tani duke punuar me listat e lidhura, ne nuk jemi duke punuar me vargjeve.
Dhe kur ne jemi duke punuar me listat e lidhura ne
e di se ne kemi nevojë për të filluar dinamike caktimin hapësirë ​​dhe ndërtimit zinxhirët.
Kjo është lloj i how-- ato janë thelbi Elementet e ndërtimit të një listë e lidhur.
Pra, le të dinamike ndajë hapësirë ​​për Joey,
dhe pastaj le të shtoni atë në zinxhirin.
>> Pra, tani të shohim se çfarë kemi bërë.
Kur ne hash Joey kemi marrë hashcode 6.
Tani akrep në array vend të 6 vë në krye të një listë të lidhura,
dhe tani kjo është e vetmja element i një liste të lidhura.
Dhe nyja në atë listë e lidhur është Joey.
>> Pra, nëse ne duhet të shohim deri Joey më vonë, ne vetëm të hash Joey përsëri,
ne kemi marrë 6 përsëri sepse tonë funksion hash është determinist.
Dhe pastaj ne të fillojë në krye e listës lidhur theksuar
për nga lokacioni array 6, dhe ne mund iterate
të gjithë se duke u përpjekur për të gjetur Joey.
Dhe në qoftë se ne ndërtojmë tonë hash tryezë në mënyrë efektive,
dhe funksioni ynë hash në mënyrë efektive për të shpërndarë të dhënat e mirë,
mesatarisht secili prej atyre të lidhura Listat në çdo vend array
do të jetë 1/10 madhësia e nëse ne kishte vetëm atë si një e vetme e madhe
listë e lidhur me çdo gjë në të.
>> Nëse ne shpërndajë se i madh i lidhur Lista e të gjithë 10 listat e lidhura
çdo listë do të jetë 1/10 madhësia.
Dhe kështu 10 herë më të shpejtë për të kërkuar përmes.
Pra, le ta bëjmë këtë përsëri.
Le tani të hash Ross.
>> Dhe le të themi Ross, kur ne bëjmë atë kodi hash marrim përsëri është 2.
E pra tani ne dinamike ndajë një nyje e re, ne kemi vënë Ross në atë nyje,
dhe ne themi tani vendndodhja grup 2, në vend të duke treguar null,
vë në kokën e një i lidhur Lista nyje vetëm i të cilit është Ross.
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.
malloc një nyje të re, e vënë Rachel në nyjen, dhe thonë se një vend array
4 tani vë në kokë nga një listë e lidhur e të cilit
vetëm element ndodh të jetë Rachel.
>> OK por çfarë ndodh nëse ne kemi një përplasje?
Le të shohim se si kemi trajtuar goditjet duke përdorur metodën e veçantë chaining.
Le të hash Phoebe.
Ne kemi marrë hashcode 6.
Në shembullin tonë të mëparshme ishim vetëm ruajtjen strings në rrjet.
Ky ishte një problem.
>> Ne nuk duam të plaçkë Joey, dhe ne kemi tashmë
shihet që ne mund të merrni disa clustering Problemet në qoftë se ne të përpiqemi dhe hap
përmes dhe hetim.
Por, çfarë nëse ne vetëm lloj i trajtuar këtë në të njëjtën mënyrë, apo jo?
Është vetëm si duke shtuar një element të në krye të një listë të lidhura.
Le hapësirë ​​vetëm malloc për Phoebe.
>> Ne do të themi pikët e radhës Phoebe pointer të kreut të vjetër të listës lidhur,
dhe pastaj 6 vetëm pikë për Kreu i ri i listës së lidhur.
Dhe tani shikoni, ne kemi ndryshuar Phoebe në.
Ne tani mund të ruajë dy Elementet me hashcode 6,
dhe ne nuk kemi ndonjë problem.
>> Kjo është shumë e shumë të gjithë ka te chaining.
Dhe chaining është padyshim metodë që është
do të jetë më efektive për ju, nëse ju jeni ruajtjen e të dhënave në një tabelë hash.
Por ky kombinim i vargjeve dhe listat lidhura
së bashku për të formuar një tabelë hash të vërtetë në mënyrë dramatike përmirëson aftësinë tuaj
për të ruajtur sasi të mëdha të të dhënave, dhe shumë shpejt dhe me efikasitet të kërkoni
nëpër këto të dhëna.
>> Ka ende një më shumë Struktura e të dhënave atje
që mund edhe të jetë pak më të mirë në aspektin e garantimit
se futje tonë, fshirje, dhe Look up kohët janë edhe më të shpejtë.
Dhe ne do të shohim se në një video në përpiqet.
Unë jam Doug Lloyd, kjo është CS50.