[MUSIC nagpe-play] DOUG LLOYD: sa ngayon ikaw alam ng maraming tungkol sa array, at alam mo ng maraming tungkol sa mga listahan ng link. At hindi namin pag-usapan ang mga kalamangan at kahinaan, na namin napag-usapan na ang mga listahan ng link ay maaaring makakuha ng mas malaki at mas maliit, ngunit tumagal ng hanggang sila ay mas laki. Ang mga array ay mas matapat na gamitin, ngunit ang mga ito ay mahigpit sa mas maraming bilang kami upang itakda ang laki ng ang array sa pinakadulo simula at pagkatapos ay natigil kami sa mga ito. 

Ngunit iyon, na namin medyo marami naubos na ang lahat ng aming mga paksa tungkol sa naka-link na mga listahan at mga array. O mayroon kami? Siguro maaari naming gawin ang isang bagay kahit na mas creative. At na uri ng mga nagpapautang ang ideya ng isang hash table. 

Kaya sa isang hash table kami ay pagpunta sa subukan pagsamahin ang isang array na may isang naka-link na listahan. Kami ay pagpunta sa gawin ang mga pakinabang ng array, tulad ng random access, kawalan ng kakayahang pumunta lamang sa array element 4 o array elemento 8 nang hindi na kinakailangang upang umulit sa kabuuan. Iyan ay medyo mabilis, di ba? 

Ngunit din namin na magkaroon ng aming data istraktura ay maaaring sa paglaki at pag-urong. Hindi natin kailangan, ay hindi kami gustong maging limitado. At gusto namin na ma upang idagdag at alisin ang mga bagay-bagay tunay madali, na kung isipin mo, ay napaka-komplikadong sa isang array. At maaari naming tawagan ang bagong bagay ng hash table. 

At kung naipatupad nang tama, uri ng kami ay pagkuha ang mga pakinabang ng parehong data istruktura na nakita mo, array at mga listahan ng link. Insertion ay maaaring magsimula sa malamang papunta theta ng 1. Theta hindi talaga namin napag-usapan, ngunit theta ay lamang ng average na mga kaso, kung ano ang aktwal na pagpunta sa mangyayari. Hindi ka palaging pagpunta sa may pinakamasama kaso sitwasyon, at ikaw ay hindi palaging pagpunta sa may ang pinakamahusay na kaso sitwasyon, kaya kung ano ang ang average na sitwasyon? 

Well isang average insertion sa isang hash table maaari simulan upang makakuha ng malapit sa pare-pareho ang panahon. At pagtanggal ay maaaring makakuha ng isara sa pare-pareho ng panahon. At lookup ay maaaring makakuha ng isara sa pare-pareho ng panahon. That's-- wala tayong isang data structure pa na maaaring gawin iyon, at kaya ito na tunog tulad ng isang medyo magandang bagay. Na talagang mitigated namin ang disadvantages ng bawat-isa. 

Upang makakuha ng pagganap na ito i-upgrade ang bagaman, kami ay kailangan umisip na muli kung paano namin magdagdag ng data sa istraktura. Partikular nais naming ang data ng kanyang sarili upang sabihin sa amin kung saan ito ay dapat pumunta sa istraktura. At kung pagkatapos ay kailangan namin upang makita kung ito ay sa ang istraktura, kung kailangan namin upang mahanap ang mga ito, gusto naming tingnan ang data at ma-muli mabisa, gamit ang data, random access ito. Sa pamamagitan lamang ng pagtingin sa mga data na dapat naming magkaroon isang ideya ng kung saan ang eksaktong hindi namin pagpunta upang mahanap ito sa hash table. 

Ngayon ang downside ng isang hash mesa ay na ang mga ito ay talagang medyo masama sa pag-order o pag-uuri ng data. At sa katunayan, kung sinimulan mo gamitin mag-order o pag-uuri ang mga ito data nawala mo ang lahat ng pakinabang sa iyo dati nagkaroon sa mga tuntunin ng insertion at pagtanggal. Ang oras ay nagiging mas malapit sa theta ng n, at hindi na namin nai talaga regressed sa isang listahan ng mga link. At kaya gusto lamang naming gamitin ang hash tables kung hindi namin pag-aalaga tungkol kung ang data ay pinagsunod-sunod. Para sa konteksto kung saan kakailanganin mong gamitin ang mga ito sa CS50 marahil ay hindi mo pag-aalaga na ang data ay pinagsunod-sunod. 

Kaya ang isang hash table ay isang kumbinasyon ng dalawang natatanging mga piraso na kung saan kami ay pamilyar. Ang una ay isang function, kung saan karaniwang namin tumawag sa isang hash. At na hash ay pagpunta sa ibalik ang ilang mga hindi-negatibong integer, na karaniwang namin tumawag sa isang hashcode, OK? Ang ikalawang piraso ay isang array, na kung saan ay kaya ng pagtatago ng data ng mga uri namin gustong ilagay sa istraktura ng data. Susubukan naming i-hold off sa naka-link na listahan ng elemento para sa ngayon at simulan lamang sa mga pangunahing kaalaman ng isang hash talahanayan upang makakuha ng inyong ulo sa paligid nito, at pagkatapos ay gagamitin namin siguro pumutok ang iyong isip nang kaunti kapag kami pagsamahin ang mga array at mga listahan ng mga link na magkasama. 

Ang pangunahing ideya bagaman ay tumagal kami ng ilang data. Nagpapatakbo kami na data sa pamamagitan ng ang hash. At sa gayon ang data ay na-proseso at ito spits isang numero, OK? At pagkatapos ay may numero na imbak lamang namin ang mga data gusto naming upang i-imbak sa array sa lokasyon na iyon. Kaya halimbawa kami siguro ito hash table ng mga string. Ito ay nakuha ng 10 mga elemento sa loob nito, kaya maaari naming magkasya 10 string sa loob nito. 

Ipagpalagay natin na nais nating hash John. Kaya si Juan ang data na nais namin upang ipasok sa ito hash table sa tabi-tabi. Saan mo ilalagay namin dito? Well karaniwang may isang array sa ngayon kami ay marahil ay ilagay ito sa array lokasyon 0. Ngunit ngayon kami ay ang bagong function hash. 

At sabihin natin na aming pinatatakbo John sa pamamagitan na ito hash at ito ay spits 4. Well na kung saan hindi namin pagpunta sa nais na ilagay John. Gusto naming ilagay Juan sa lokasyon array 4, dahil kung hash namin John again-- sabihin natin mamaya namin nais na paghahanap at makita kung umiiral John sa hash table-- lahat ng kailangan naming gawin ay tatakbo ito sa pamamagitan ng parehong hash function, makuha ang numero 4 out, at ma-makahanap John kaagad sa aming mga istraktura ng data. Iyan ay medyo mabuti. 

Ipagpalagay natin na gawin namin ito ngayon muli, nais naming hash Paul. Gusto naming magdagdag ng Paul sa ito hash table. Sabihin natin na ang oras na ito tumakbo kami Paul sa pamamagitan ng hash function, ang hashcode na nabuo ay 6. Well ngayon ay maaari naming ilagay ang Paul sa array lokasyon 6. At kung kailangan namin upang tumingin up kung Paul ay nasa ito hash table, lahat ng kailangan naming gawin ay tumakbo Paul sa pamamagitan ng hash muli at kami ay pagpunta upang makakuha ng 6 out muli. 

At pagkatapos ay tumingin lang namin sa array lokasyon 6. Mayroon bang Paul? Kung gayon, siya ay sa hash table. Ay Paul hindi doon? Siya ay wala sa hash table. Ito ay medyo tapat. 

Ngayon paano mo tukuyin ang isang hash function? Well may tunay na walang limitasyon sa bilang ng mga posibleng hash function. Sa katunayan mayroong isang bilang ng mga tunay, tunay mabuti iyan sa internet. Mayroong isang bilang ng mga tunay, ganap na hindi maayos na iyan sa internet. Ito ay medyo madali din sumulat ng isang masamang isa. 

Kaya kung ano ang gumagawa ng isang magandang hash, di ba? Well isang magandang function hash dapat gamitin lamang ang mga data na na-hash, at ang lahat ng mga data na na-hash. Kaya hindi namin nais na gumamit ng anything-- hindi namin isama ang anumang bagay pa ang iba sa mga data. At gusto namin na gamitin ang lahat ng mga data. Hindi namin nais na gumamit lamang ng isang piraso ng mga ito, gusto naming gamitin ang lahat ng ito. Isang hash dapat maging deterministic din. Ano ang ibig sabihin nito? Well ito ay nangangahulugan na ang bawat oras na namin ipasa ang parehong piraso ng data sa hash kami ay palaging makakuha ng parehong hashcode out. Kung pumasa I Juan sa hash na nakukuha ko mula 4. Dapat kong magawa na 10,000 beses at lagi makakuha ng 4. Kaya walang mga random na numero epektibong maaaring kasangkot sa aming hash tables-- sa ating mga pag-andar hash. 

Isang hash ay dapat din pantay ipamahagi ang data. Kung sa bawat oras na patakbuhin mo ang data sa pamamagitan ng hash mong makuha ang hashcode 0, na malamang ay hindi kaya mahusay na, i-right? Maaring nais na malaki isang hanay ng mga hash code. Gayundin bagay ay maaaring kumalat out sa buong table. At din ito ay mahusay na kung talagang katulad na data, tulad ni Juan at Jonathan, marahil ay magkahiwalay sa timbangin iba't-ibang lokasyon sa hash table. Iyon ay isang magandang bentahe. 

Narito ang isang halimbawa ng isang hash. Isinulat ko ang isang ito up nang mas maaga. Ito ay hindi isang partikular na magandang function hash para sa mga dahilan na hindi tunay madala ang pagpunta sa ngayon. Ngunit huwag mong makita kung ano ang nangyayari sa dito? Tila tulad ng kami ay deklarasyon ng variable tinatawag sum at ang setting na ito katumbas ng 0. At pagkatapos ay tila ako ng paggawa ng isang bagay kaya hangga't strstr [j] ay hindi katumbas ng sa backslash 0. Ang ginagawa ko doon? 

Ito ay karaniwang lamang ng isa pang paraan ng pagpapatupad [? strl?] at tiktik kapag na sa iyo naabot na ang dulo ng string. Kaya hindi ko kung talagang kalkulahin ang haba ng string, Lamang ako ng gamit kapag ako ay pindutin ang backslash 0 karakter alam ko Naabot ko na ang dulo ng string. At pagkatapos ay ako pagpunta sa panatilihin iterating sa pamamagitan ng na string, pagdagdag ng strstr [j] sa sum, at pagkatapos ay sa pagtatapos ng araw upang bumalik sum mod HASH_MAX. 

Talaga lahat ng hash na ito function na ito ay ginagawa ng pagdaragdag ng hanggang lahat ng mga halaga ASCII ng aking string, at pagkatapos ito ay bumabalik ilang hashcode modded pamamagitan HASH_MAX. Ito ay marahil ang laki ng aking array, di ba? Hindi ko nais na maging sa pagkuha hash Mga code kung ang aking array ng laki 10, Hindi ko nais na maging pagkuha out hash code 11, 12, 13, hindi ko maaaring ilagay ang mga bagay sa mga lokasyon ng mga array, na labag sa batas. Gusto ko magdusa ng segmentation fault. 

Ngayon dito ay isa pang mabilis tabi. Kadalasan ikaw ay marahil hindi pagpunta sa gusto mong isulat ang iyong sariling mga hash function. Ito ay talagang isang piraso ng isang sining, hindi isang science. At mayroong isang pulutong na napupunta sa mga ito. Ang internet, tulad ng sinabi ko, ay puno ng tunay na magandang pag-andar hash, at dapat mong gamitin ang internet upang maghanap ng hash function dahil ito ay talagang lamang ang uri ng isang hindi kailangang aksaya ng panahon upang lumikha ng iyong sarili. 

Maaari mong isulat ang mga musmos para sa mga layunin sa pagsubok. Ngunit kapag ikaw talaga ay pagpunta sa simulan hashing data at pag-imbak nito sa isang hash table ikaw marahil pagpunta sa gusto upang gamitin ang ilang mga function na ay binuo para sa iyo, na umiiral sa internet. Kapag kayo ay siguraduhin lamang na banggitin ang iyong mga pinagkukunan. Walang dahilan upang mamlahiyo anumang bagay dito. 

Ang komunidad na computer science ay tiyak lumalaki, at talagang halaga open source, at ito ay talagang mahalaga na banggitin ang iyong mga pinagkukunan sa gayon na ang mga tao ay maaaring makakuha ng pagpapatungkol para sa ang mga trabaho na ang mga ito ay paggawa sa mga benepisyo ng komunidad. Kaya laging sure-- at hindi lamang para sa hash pag-andar, ngunit sa pangkalahatan ay kapag ikaw gamitin ang code mula sa isang panlabas na pinagmulan, laging banggitin ang iyong source. Bigyan ng credit sa mga tao na ang ilan sa mga trabaho kaya hindi mo na kailangang. 

OK ni muling bisitahin ito upang ipaalam sa hash talahanayan para sa isang segundo. Ito ay kung saan namin kaliwa off pagkatapos naming nakapasok John at Paul sa ito hash table. May nakikita ka bang problema dito? Maaari kang makakita ng dalawang. Ngunit sa partikular, gawin mo makikita ito ng mga posibleng problema? 

Paano kung ako hash Ringo, at ito lumiliko out na matapos ang pagproseso ang data na iyon sa pamamagitan ng hash Ringo nakabuo din ang hashcode 6. Na mayroon akong data sa hashcode-- lokasyon array 6. Kaya ito ay marahil pagpunta sa maging isang bit ng isang problema para sa akin ngayon, tama? 

Tinatawag namin itong isang banggaan. At ang banggaan ay nangyayari kapag ang dalawang mga piraso ng data tumakbo sa pamamagitan ng parehong hash function na ani ng parehong hashcode. Siguro namin gusto pa rin upang makakuha ng parehong mga mga piraso ng data sa hash table, kabilang banda ay hindi maaaring tumakbo kami Ringo nagkataon pamamagitan ng hash. Siguro namin nais na makakuha ng Ringo sa na array. 

Paano namin gawin ito bagaman, kung siya at Paul parehong ani hashcode 6? Hindi namin gusto ang patungan Paul, gusto naming Paul na may masyadong. Kaya kailangan namin upang makahanap ng isang paraan upang makakuha ng elemento sa hash table na pinapanatili pa rin ang aming mabilis na insertion at mabilis na pagtingin up. At isang paraan upang harapin ang mga ito ay upang gawin ang isang bagay na tinatawag na linear probing. 

Gamit ang pamamaraan na kung kami ay may isang banggaan, well, ano ang gagawin namin? Well hindi namin maaaring ilagay sa kanya sa lokasyon array 6, o kahit anong hashcode ay nabuo, Maglagay ng kanya sa hashcode plus 1 ipaalam. At kung na full hahayaan inilagay siya sa hashcode plus 2. Ang mga benepisyo ng mga ito na kung siya ay hindi eksakto kung saan sa tingin namin siya ay, at kami ay may upang simulan ang paghahanap, marahil hindi namin ay may upang pumunta masyadong malayo. Siguro hindi natin kailangang maghanap lahat ng mga elemento n ng hash table. Siguro na namin sa paghahanap isang pares ng mga ito. 

At kaya kami ay nag-aalaga pa rin patungo sa na average case pagiging malapit sa 1 vs malapit sa n, kaya marahil na kakailanganin sa trabaho. Kaya sabihin makita kung paano ito maaaring gumana out sa katotohanan. At makita kung marahil maaari naming makita ipaalam mga problema na maaaring mangyari dito. 

Ipagpalagay natin na hash namin Bart. Kaya ngayon kami ay pagpunta sa magpatakbo ng isang bagong set ng mga string sa pamamagitan ng hash function, at tumakbo kami Bart sa pamamagitan ng hash function, makakakuha tayo ng hashcode 6. Kumuha kami ng isang tumingin, makikita natin na 6 ay walang laman, upang maaari naming ilagay Bart doon. 

Ngayon hash namin Lisa at na Bumubuo din hashcode 6. Well ngayon na aming ginagamit ito linear probing paraan simulan namin sa 6, nakita namin na 6 ay puno na. Hindi namin maaaring ilagay Lisa sa 6. Kaya kung saan tayo pupunta? Sabihin pumunta sa 7. 7 ng walang laman, kaya na gumagana. Kaya sabihin maglagay Lisa doon ipaalam. 

Ngayon hash namin Homer at makuha namin 7. OK na rin alam namin na 7 ng full ngayon, kaya hindi namin maaaring ilagay Homer doon. Kaya sabihin pumunta sa 8. Available ba 8? Oo, at malapit sa 7 8, kaya kung kami ay may upang simulan ang paghahanap hindi namin hindi pagpunta sa may upang pumunta masyadong malayo. At ang ilagay Homer sa 8 kaya hayaan. 

Ngayon hash namin Maggie at nagbabalik 3, salamat sa diyos hindi namin magagawang ilagay lamang Maggie doon. Hindi natin kailangang gawin ang anumang uri ng probing para sa na. Ngayon hash namin Marge, at Nagbabalik din Marge 6. 

Well 6 ay puno na, 7 ay puno na, 8 ay puno na, 9, ang lahat ng karapatan salamat sa Diyos, 9 ay walang laman. Maaari ko bang ilagay Marge sa 9. Ginagamit mo na maaari naming makita na kami ay nagsisimula na magkaroon ng ganitong problema kung saan ngayon hindi namin simula upang mabatak bagay uri ng malayo mula sa kanilang hash code. At na theta ng 1, na average kaso ng pagiging pare-pareho ang oras, ay nagsisimula upang makakuha ng isang maliit more-- nagsisimula na may posibilidad ng kaunti pa patungo theta ng n. Kami ay nagsisimula sa mawala na ang bentahe ng hash talahanayan. 

Ang problemang ito na nakita namin lamang isang bagay na tinatawag clustering. At kung ano ang talagang masama tungkol clustering ay na sa sandaling ikaw ay ngayon may dalawang mga sangkap na bahagi sa pamamagitan ng gilid ito ay gumagawa ito kahit na mas malamang, ikaw ay may double ang pagkakataon, na ikaw ay pagpunta magkaroon ng isa pang banggaan may na kumpol, at ang mga kumpol ay lalaki sa pamamagitan ng isa. At makikita mo panatilihin lumalago at lumalaki ang iyong posibilidad ng pagkakaroon ng isang banggaan. At sa huli ito ay tulad ng masama bilang hindi pag-uuri sa lahat ng mga data. 

Ang iba pang mga problema bagaman ay namin pa rin, at sa ngayon hanggang sa puntong ito, lang nakaya naming uri ng sa pag-unawa kung ano ang isang hash table ay, pa rin namin ang magkaroon lamang ng room para sa 10 mga string. Kung gusto namin upang magpatuloy sa hash ang mga mamamayan ng Springfield, kami ay maaari lamang makakuha ng 10 sa mga ito sa doon. At kung susubukan at magdagdag ng isang ika-11 o ika-12 namin, hindi namin ay may isang lugar upang ilagay ang mga ito. Kami ay maaaring lamang ay umiikot sa paligid sa bilog sinusubukan upang mahanap ang isang walang laman na lugar, at kami ay marahil makakuha ng mapagmataas sa isang walang-katapusang loop. 

Kaya ito uri ng mga nagpapautang sa ideya ng isang bagay na tinatawag pagdudugtong. At ito ay kung saan kami ay pagpunta upang dalhin sa mga listahan ng naka-link pabalik sa ang larawan. Paano kung sa halip ng pag-iimbak lamang ang data mismo sa array, bawat elemento ng array ng dati maghawak ng maramihang mga piraso ng data? Well na ay hindi magkaroon ng kahulugan, tama? Alam namin na ang isang array ay maaari lamang hold-- bawat elemento ng isang array maaari lamang humawak ng isang piraso ng data ng mga uri ng data. 

Ngunit paano kung na uri ng data ay isang listahan ng mga link, di ba? Kaya kung ano kung ang bawat element ng array ay isang pointer sa ulo ng isang listahan ng mga link? At pagkatapos ay maaari kaming bumuo ng mga listahan ng link at maging ang mga ito nagkataon, dahil pinapayagan listahan ng link sa amin upang maging at pag-urong ng maraming higit pa flexibly kaysa sa isang array ay. Kaya kung ano kung kami ay gamitin ngayon, naming pagkilos na ito, i-right? Simulan namin na palaguin ang mga kadena out ng mga lokasyon na array. 

Ngayon ay maaari naming magkasya sa isang walang hanggan halaga ng data, o hindi walang katapusan, isang di-makatwirang halaga ng data, sa aming hash table nang hindi kailanman tumatakbo sa ang problema ng banggaan. Na inalis rin namin clustering pamamagitan ng paggawa nito. At well alam namin na kapag ipasok namin sa isang listahan ng mga link, kung ang pagpapabalik sa iyo mula sa aming mga video sa listahan ng link, isa-isa naka-link na mga listahan at mga doble-link na listahan, ito ay isang patuloy na operasyon ng panahon. Lang kaming nagdadagdag sa harap. 

At para sa hitsura up, well alam natin na tumingin up sa isang listahan ng mga link maaaring maging isang problema, di ba? Mayroon kaming upang maghanap sa pamamagitan ng ito mula sa umpisa hanggang katapusan. Walang random access sa isang naka-link na listahan. Ngunit kung sa halip ng pagkakaroon ng isa na naka-link list kung saan ang isang lookup ay O ng n, kami ngayon ay mayroon ng 10 mga listahan na naka-link, o 1,000 mga listahan na naka-link, ngayon ito ay O ng n hinati sa 10, o O ng n hinahati sa pamamagitan ng 1,000. 

At habang kami ay pakikipag-usap theoretically tungkol kumplikado babalewalain natin constants, sa tunay na mundo ng mga bagay na talagang mahalaga, right? Kami ay talagang mapansin na nangyari ito upang magpatakbo ng 10 beses na mas mabilis, o 1,000 beses na mas mabilis, dahil kami ay namamahagi ng isang mahabang chain sa buong 1,000 mas maliliit na kadena. At kaya sa bawat oras na namin sa paghahanap sa pamamagitan ng isa sa mga chains ng aming makakaya huwag pansinin ang 999 chains hindi namin pakialam tungkol sa, at hanapin lang ang isa. 

Alin sa average na 1,000 beses na mas maikli. At gayon pa rin kami uri ng tending patungo ito average case ng pagiging pare-pareho ang oras, ngunit lamang dahil tayo ay pagdaragdag naghahati sa pamamagitan ng ilang mga napakalaking constant factor. Tayo'y makita kung paano maaaring ito Hayaan aktwal na hitsura kahit na. Kaya ito ay ang talahanayan hash namin ay bago namin ipinahayag ng isang hash table na ay kaya ng pagtatago ng 10 string. Hindi namin pagpunta sa gawin na anymore. Alam na namin ang limitasyon ng pamamaraan na iyon. Ngayon ang aming hash table ay magiging isang array ng 10 nodes, mga payo sa mga ulo ng mga naka-link na mga listahan. 

At ngayon ito ay null. Ang bawat isa sa mga 10 mga payo ay null. Walang wala sa aming hash talahanayan ngayon. 

Ngayon sabihin simulan upang ilagay ang ilang ipaalam mga bagay na ito sa hash table. At makita kung paano ang paraan na ito ay ipaalam pagpunta upang makinabang sa amin nang kaunti. Ngayon sumira ni Joey Hayaan. Susubukan naming tatakbo ang string Joey pamamagitan isang hash at kami ay bumalik 6. Well kung ano ang gagawin namin ngayon? 

Well ngayon ay nagtatrabaho sa naka-link na mga listahan, hindi namin ay nagtatrabaho sa array. At kapag kami ay nagtatrabaho may mga listahan ng link namin Alam na kailangan namin upang simulan ang magilas paglaan ng space at mga gusali ng kadena. Iyan ay ang uri ng mga how-- iyon ay ang mga core mga elemento ng pagbuo ng isang listahan ng mga link. Kaya sabihin magilas maglaan ng espasyo para Joey, at pagkatapos ay sabihin magdagdag ng kanya sa chain. 

Kaya tingnan mo ngayon kung ano ang aming nagawa. Kapag hash namin Joey namin nakuha ang hashcode 6. Ngayon ang pointer sa array lokasyon 6 puntos sa ulo ng isang listahan ng mga link, at ngayon ito ay ang tanging elemento ng isang listahan ng mga link. At ang mga node sa na listahan ng mga link ay Joey. 

Kaya kung kailangan namin upang tumingin up Joey mamaya, hash namin lamang Joey muli, makakakuha tayo ng 6 muli dahil ang aming hash ay deterministic. At pagkatapos ay simulan namin sa ulo mga listahan ng mga link tulis sa pamamagitan ng lokasyon array 6, at maaari naming umulit kabuuan na sinusubukan mong hanapin Joey. At kung bumuo kami ng aming hash talahanayan mabisa, at ang aming hash epektibong upang ipamahagi na rin ang data, sa average na bawat isa sa mga naka-link mga listahan sa bawat lokasyon array ay 1/10 ang laki ng kung tayo Nagkaroon lamang ito bilang isang solong malaking listahan ng mga link sa lahat ng bagay sa loob nito. 

Kung ipamahagi namin na malaking naka-link list sa buong 10 mga listahan na naka-link bawat listahan ay 1/10 ang laki. At kaya 10 beses na mas mabilis upang maghanap sa pamamagitan ng. Kaya sabihin gawin ito muli. Ngayon sumira ni Ross Hayaan. 

At sabihin natin Ross, kapag ginagawa namin na ang code hash makuha namin pabalik ay 2. Well ngayon dynamic allocate kami ng isang bagong node, inilalagay namin Ross sa na node, at sinasabi namin ngayon lokasyon array 2, sa halip na tumuturo sa null, puntos sa ulo ng isang naka-link list na ang tanging node ay Ross. At maaari naming gawin ito ng isa pang beses, kami ay Maaari hash Rachel at makakuha hashcode 4. malloc isang bagong node, ilagay Rachel in buko, at sabihin ang isang lokasyon array 4 ngayon puntos sa ulo ng isang listahan ng mga link na mangyayari lamang ang sangkap na Rachel. 

OK ngunit kung ano ang mangyayari kung kami ay may isang banggaan? Tayo'y makita kung paano namin pinangangasiwaan ang mga banggaan Ipaalam gamit ang hiwalay na paraan chaining. Ni hash Phoebe Hayaan. Makuha namin ang hashcode 6. Sa aming nakaraang halimbawa kami ay lamang pag-iimbak ng mga string sa array. Ito ay isang problema. 

Hindi namin nais na gumulpi Joey, at kami Na nai makikita na maaari naming makakuha ng ilang clustering problema kung susubukan namin at hakbang sa pamamagitan at sa probe. Ngunit paano kung namin lamang uri ng gamutin ito sa parehong paraan, di ba? Ito ay tulad ng pagdagdag ng isang sangkap sa ulo ng isang naka-link na listahan. Sabihin lang malloc espasyo para sa Phoebe. 

Susubukan naming sabihin sa susunod na pointer puntos Phoebe sa lumang ulo ng naka-link na listahan, at pagkatapos lamang ng 6 na puntos sa mga bagong ulo ng naka-link na listahan. At ngayon, tumingin, binago namin Phoebe in. Maaari naming ngayon tindahan ng dalawang elemento na may hashcode 6, at hindi namin ay may anumang problema. 

Iyan ay medyo marami ang lahat ng doon ay upang chaining. At pagdudugtong ay tiyak ang paraan na magiging pinaka-epektibo para sa iyo kung ikaw ay pagtatago ng data sa isang hash table. Ngunit ang kumbinasyon ng mga array at mga listahan ng link magkasama upang bumuo ng hash table talagang kapansin-pansing mapabuti ang iyong kakayahan upang mag-imbak ng malaking halaga ng data, at masyadong mabilis at mahusay sa paghahanap sa pamamagitan ng na data. 

Mayroong isa pang pa rin istraktura ng data out there na maaaring kahit na maging isang bit mas mahusay sa mga tuntunin ng guaranteeing na ang aming insertion, pagtanggal, at maghanap ng mga oras ay mas mabilis pa. At kami na makita na sa isang video sa pagsusubok. Ako Doug Lloyd, ito ay CS50.