[CHWARAE CERDDORIAETH] DOUG LLOYD: Erbyn hyn yr ydych yn gwybod llawer am araeau, a ydych yn gwybod llawer am restrau cysylltiedig. Ac rydym wedi trafod y manteision ac anfanteision, rydym wedi trafodwyd a oedd yn cysylltu rhestri yn gallu cael mwy a llai, ond maent yn cymryd mwy maint. Araeau yn llawer mwy syml i'w defnyddio, ond maent yn gyfyngol mewn cymaint fel yr ydym wedi gosod maint yr amrywiaeth ar y cychwyn cyntaf ac yna rydym yn sownd ag ef. 

Ond dyna, rydym wedi 'n bert lawer dihysbyddu ein holl bynciau am restrau cysylltiedig a arrays. Neu mae'n rhaid i ni? Efallai y gallwn wneud rhywbeth hyd yn oed yn fwy creadigol. A'r math yna o benthyg y syniad o dabl hash. 

Felly, mewn tabl hash rydyn ni'n mynd i roi cynnig ar cyfuno amrywiaeth gyda rhestr cysylltiedig. Rydym yn mynd i gymryd y manteision y rhesi, fel mynediad ar hap, y gallu i jyst yn mynd i amrywiaeth Elfen 4 neu array elfen 8 heb orfod ailadrodd ar draws. Dyna 'n bert gyflym, dde? 

Ond rydym hefyd eisiau cael ein data strwythur yn gallu tyfu ac yn crebachu. Nid oes angen i ni, nid ydym yn ei wneud eisiau cael eu cyfyngu. Ac rydym am fod yn gallu i ychwanegu a dileu pethau yn hawdd iawn, ac os ydych yn cofio, yn gymhleth iawn gydag amrywiaeth. A gall rydym yn galw hyn beth newydd tabl hash. 

Ac os gweithredu'n gywir, rydym yn fath o gymryd y manteision o ddau ddata strwythurau rydych chi wedi gweld yn barod, araeau a rhestrau cysylltiedig. Gall Mewnosod ddechrau yn tueddu tuag at theta o 1. Theta nid ydym wedi trafod mewn gwirionedd, ond theta yn unig yw yr achos ar gyfartaledd, beth mewn gwirionedd yn mynd i ddigwydd. Nid ydych bob amser yn mynd i yn cael y sefyllfa waethaf, ac nad ydych yn bob amser yn mynd i gael y senario achos gorau, felly beth y senario ar gyfartaledd? 

Wel mae mewnosod ar gyfartaledd mewn tabl hash Gall dechrau i ddod yn agos i'w gilydd yn gyson. A gall dileu gael cau i dro cyson. A gall ei gael am-edrych cau i dro cyson. That's-- nid oes gennym ddata strwythur eto a all wneud hynny, ac felly mae hyn eisoes yn swnio fel rhywbeth 'n bert da. Rydym wedi lliniaru mewn gwirionedd yn y anfanteision pob un ar ei ben ei hun. 

I gael y perfformiad hwn uwchraddio fodd bynnag, rydym yn angen i ni ailystyried sut rydym yn ychwanegu data i mewn i'r strwythur. Yn benodol rydym am i'r data ei hun i ddweud wrthym ble y dylai fynd yn y strwythur. Ac os ydym, yna mae angen i weld a yw'n mewn strwythur, os bydd angen i ddod o hyd iddo, rydym am edrych ar y data eto a gallu yn effeithiol, ddefnyddio'r data, ar hap gael gafael arno. Dim ond drwy edrych ar y data dylem gael syniad o ble yn union rydym yn mynd i ddod o hyd iddo yn y tabl hash. 

Nawr bod y Anfantais hash tabl yw eu bod yn wirioneddol eithaf gwael yn archebu neu'n didoli data. Ac yn wir, os byddwch yn dechrau i'w defnyddio i archebu neu ddidoli data byddwch yn colli pob un o'r manteision i chi o'r blaen Roedd yn nhermau mewnosod a dileu. Mae'r amser yn dod yn nes at theta o n, ac rydym wedi bôn llithro'n ōl i mewn i restr cysylltiedig. Ac felly rydym yn unig am eu defnyddio hash tablau os nad ydym yn poeni am a yw'r data yn cael ei datrys. Ar gyfer y cyd-destun y byddwch yn eu defnyddio yn CS50 mae'n debyg nad oes ots bod y data yn cael ei datrys. 

Felly tabl hash yn gyfuniad o ddau ddarn ar wahân rydym yn gyfarwydd â hwy. Y cyntaf yn swyddogaeth, a oedd yn Fel arfer, rydym yn galw swyddogaeth hash. A bod swyddogaeth hash yn mynd i dychwelyd rhywfaint cyfanrif heb fod yn negyddol, a oedd yn Fel arfer, rydym yn galw hashcode, OK? Mae'r ail ddarn yn array, sydd yn gallu storio data o'r math yr ydym yn awyddus i roi i mewn i'r strwythur data. Byddwn yn dal i ffwrdd ar y cysylltu elfen rhestr ar hyn o bryd a dim ond dechrau gyda'r pethau sylfaenol o hash tabl i gael eich pen o'i gwmpas, ac yna byddwn efallai chwythu eich meddwl ychydig bach pan fyddwn cyfuno araeau a rhestrau cyswllt at ei gilydd. 

Y syniad sylfaenol er yw ein cymryd rhywfaint o ddata. Rydym yn cynnal y data hynny drwy y swyddogaeth hash. Ac felly mae'r data yn cael ei brosesu ac mae'n poeri allan nifer, OK? Ac yna gyda nifer hwnnw rydym yn unig storio'r data rydym am i storio yn y amrywiaeth yn y lleoliad hwnnw. Felly, er enghraifft mae gennym efallai y tabl hwn hash o dannau. Mae'n got 10 elfen ynddo, felly gallwn ffitio 10 dannau ynddo. 

Lets 'ddeud rydym am hash John. Felly John gan fod y data yr ydym am i fewnosod i mewn i dabl hash hwn yn rhywle. Ble rydym yn ei roi? Wel fel arfer gyda amrywiaeth hyd yn hyn rydym yn ôl pob tebyg Byddai roi yn lleoliad array 0. Ond yn awr mae gennym y swyddogaeth hash newydd. 

A gadewch i ni ddweud ein bod yn rhedeg John drwy swyddogaeth hash hon ac mae'n poeri allan 4. Wel dyna lle rydym yn mynd i eisiau rhoi John. Rydym yn awyddus i roi John yn y lleoliad array 4, oherwydd os ydym yn hash John again-- gadewch i ni ddweud yn ddiweddarach rydym yn am ei chwilio a gweld os John yn bodoli yn hash hwn table-- pob mae angen i ni ei wneud yn cael ei rhedeg drwy'r un hash swyddogaeth, yn cael y rhif 4 allan, ac yn gallu canfod John ar unwaith yn ein strwythur data. Dyna 'n bert da. 

Lets 'ddeud ein bod yn awr yn gwneud hyn eto, rydym am hash Paul. Rydym eisiau ychwanegu Paul i mewn i dabl hash hwn. Lets 'ddeud bod y cyfnod hwn rydym yn cynnal Paul drwy'r swyddogaeth hash, mae'r hashcode a gynhyrchir yw 6. Wel nawr gallwn roi Paul yn y lleoliad array 6. Ac os bydd angen i edrych i fyny a yw Mae Paul yn yn nhabl hash hwn, i gyd mae angen i ni ei wneud yn cael ei redeg Paul drwy'r swyddogaeth hash eto ac rydym yn mynd i gael 6 allan eto. 

Ac yna rydym yn dim ond yn edrych yn y lleoliad array 6. A yw Paul yno? Os felly, mae yn y tabl hash. A yw Paul does? Dyw e ddim yn yn y tabl hash. Mae'n eithaf syml. 

Nawr, sut ydych chi'n diffinio swyddogaeth hash? Wel does 'n sylweddol oes terfyn ar nifer o swyddogaethau hash posibl. Yn wir mae 'na nifer o mewn gwirionedd, rhai gwirioneddol dda ar y rhyngrwyd. Mae 'na nifer o mewn gwirionedd, rhai drwg iawn ar y rhyngrwyd. Mae hefyd yn eithaf hawdd i ysgrifennu un drwg. 

Felly beth sy'n gwneud i fyny yn dda swyddogaeth hash, dde? Wel dylai swyddogaeth hash da defnyddio dim ond y data sy'n cael eu hashed, a phob un o'r data sy'n cael eu hashed. Felly nid ydym am eu defnyddio anything-- nid ydym yn ymgorffori unrhyw beth arall heblaw am y data. Ac rydym eisiau defnyddio holl ddata. Nid ydym am i ddim ond defnyddio darn ohono, rydym eisiau defnyddio cyfan ohono. Swyddogaeth hash dylai hefyd fod yn benderfynedig. Beth yw ystyr hynny? Wel mae'n golygu bod pob tro y byddwn yn pasio'r union un darn o ddata i mewn i'r swyddogaeth hash byddwn bob amser yn yn cael yr un hashcode allan. Os byddaf yn mynd heibio John i mewn i'r swyddogaeth hash Rwy'n cael allan 4. Dylwn fod yn gallu gwneud hynny 10,000 amserau a byddaf bob amser yn cael 4. Felly nid oes rhifau ar hap yn effeithiol Gall fod yn rhan o'n hash tables-- yn ein swyddogaethau hash. 

Dylai Swyddogaeth hash hefyd unffurf dosbarthu data. Os bob tro y byddwch yn rhedeg y data trwy'r swyddogaeth hash i chi gael y hashcode 0, dyna debyg nad mor fawr, dde? Mae'n debyg y byddwch am i fawr amrediad o godau hash. Hefyd, gall pethau gael eu lledaenu allan drwy gydol y tabl. A hefyd y byddai'n wych os 'n sylweddol data tebyg, fel John a Jonathan, efallai eu gwasgaru i bwyso a mesur gwahanol leoliadau yn y tabl hash. Byddai hynny yn fantais 'n glws. 

Dyma enghraifft o un o swyddogaethau hash. Ysgrifennais yr un yma yn gynharach. Nid yw'n arbennig swyddogaeth hash da am resymau nad ydynt mewn gwirionedd arth yn mynd i mewn ar hyn o bryd. Ond a ydych yn gweld beth sy'n digwydd yma? Mae'n ymddangos fel ein bod yn datgan newidyn Gelwir swm a gosod ei hafal i 0. Ac yna mae'n debyg fy mod yn gwneud rhywbeth ar yr amod nad strstr [j] yn hafal i slaes 0. Beth ydw i'n ei wneud yno? 

Mae hyn yn y bôn yn unig un arall ffordd o weithredu [? strl?] a chanfod pan eich bod wedi cyrraedd diwedd y llinyn. Felly nid oes rhaid i Fi 'n weithredol cyfrifo hyd y llinyn, Im 'jyst yn defnyddio pan fyddaf yn cyrraedd y slaes 0 gymeriad yr wyf yn gwybod Rydw i wedi cyrraedd diwedd y llinyn. Ac yna dwi'n mynd i gadw ailadrodd drwy'r llinyn, gan ychwanegu strstr [j] i grynhoi, ac yna yn y diwedd y dydd yn mynd i ddychwelyd swm mod HASH_MAX. 

Yn y bôn yr holl hash hwn swyddogaeth yn ei wneud yn ychwanegu i fyny pob un o'r gwerthoedd ASCII o fy llinyn, ac yna mae'n dychwelyd rhywfaint hashcode modded gan HASH_MAX. Mae'n debyg mai dyma'r maint fy array, dde? Nid wyf am i fod yn mynd hash Codau os yw fy casgliad o faint 10, Dydw i ddim eisiau bod yn cael Codau hash allan 11, 12, 13, ni allaf roi pethau mewn lleoliadau hynny y rhesi, a fyddai'n anghyfreithlon. Id 'yn dioddef nam segmentu. 

Nawr dyma un arall gyflym neilltu. Yn gyffredinol, mae'n debyg nad yn mynd i am ysgrifennu eich swyddogaethau hash hun. Mae'n mewn gwirionedd yn dipyn o yn gelfyddyd, nid gwyddoniaeth. Ac mae llawer sy'n mynd i mewn iddynt. Mae'r rhyngrwyd, fel y dywedais, yn llawn swyddogaethau hash gwirioneddol dda, a dylech ddefnyddio'r rhyngrwyd i dod o hyd i swyddogaethau hash oherwydd ei fod yn wir yn yn unig fath o diangen wastraff amser i greu eich hun. 

Gallwch ysgrifennu rhai syml at ddibenion profi. Ond pan fyddwch mewn gwirionedd yn mynd i dechrau stwnsio data a'i storio mewn tabl hash eich bod yn yn ôl pob tebyg yn mynd i eisiau i ddefnyddio rhai swyddogaeth a gynhyrchwyd i chi, sy'n bodoli ar y rhyngrwyd. Os ydych yn unig fod yn siŵr i ddyfynnu eich ffynonellau. Does dim rheswm i plagiarize unrhyw beth yma. 

Mae'r gymuned cyfrifiadureg yn bendant yn tyfu, ac yn wir gwerthoedd ffynhonnell agored, ac mae'n bwysig iawn i ddyfynnu eich ffynonellau fel bod pobl Gall gael priodoliad am y gwaith y maent yn wneud er budd y gymuned. Felly bob amser yn sure-- ac nid dim ond ar gyfer hash swyddogaethau, ond yn gyffredinol pan fyddwch yn defnyddio cod o ffynhonnell allanol, bob amser ddyfynnu eich ffynhonnell. Yn rhoi credyd i'r person a wnaeth rhywfaint o'r gwaith fel nad oes rhaid i chi. 

Iawn felly gadewch i ni edrych eto ar hyn tabl hash am eiliad. Dyma lle ni adael i ffwrdd ar ôl i ni mewnosod John a Paul i mewn i dabl hash hwn. A ydych yn gweld problem yma? Efallai y byddwch yn gweld dau. Ond yn benodol, a ydych gweld problem posibl hwn? 

Beth os byddaf yn hash Ringo, ac mae'n ymddangos bod ar ôl prosesu data hwnnw drwy'r swyddogaeth hash Ringo hefyd yn cynhyrchu y hashcode 6. Rwyf eisoes wedi cael data ar Lleoliad amrywiaeth hashcode-- 6. Felly, mae'n fwy na thebyg yn mynd i fod ychydig yn o broblem i mi nawr, dde? 

Rydym yn galw hyn yn gwrthdrawiad. Ac y gwrthdrawiad yn digwydd pan fydd dau darnau o ddata yn rhedeg drwy'r un hash swyddogaeth cynnyrch yr un hashcode. Yn ôl pob tebyg yr ydym yn dal yn awyddus i gael y ddau darnau o ddata yn y tabl hash, fel arall ni fyddem yn cynnal Ringo fympwyol drwy'r swyddogaeth hash. Rydym yn ôl pob tebyg am gael Ringo i mewn i'r casgliad. 

Sut rydym yn ei wneud fodd bynnag, os yw ef a Paul y ddau gynnyrch hashcode 6? Nid ydym am ei throsysgrifo Paul, rydym am i Paul fod yno hefyd. Felly mae angen i ddod o hyd i ffordd i gael elfennau yn y tabl hash sy'n dal cyffeithiau ein cyflym mewnosod a edrych yn sydyn i fyny. Ac un ffordd i ddelio ag ef yw gwneud rhywbeth a elwir yn llinol treiddgar. 

Gan ddefnyddio'r dull hwn os oes gennym gwrthdrawiad, wel, beth ydym yn ei wneud? Wel ni allwn ei roi mewn lleoliad array 6, neu beth bynnag hashcode ei greu, gadewch i ni ei roi ar hashcode ac 1. Ac os dyna osod llawn ei roi mewn hashcode a 2. Mantais o fod hwn os ei fod yn Nid yw union lle yr ydym yn meddwl ei fod yn, ac mae'n rhaid i ni ddechrau chwilio, efallai nad oes gennym i mynd yn rhy bell. Efallai nad oes gennym i chwilio holl elfennau'r n o'r tabl hash. Efallai mae'n rhaid i ni chwilio un neu ddau ohonynt. 

Ac felly rydym yn dal i dueddu tuag at yr achos ar gyfartaledd yn agos at 1 vs yn agos at n, felly efallai y bydd yn gweithio. Felly, gadewch i ni weld sut mae hyn yn Gallai gweithio allan mewn gwirionedd. A gadewch i ni weld os efallai y gallwn ganfod y broblem allai ddigwydd yma. 

Lets 'ddeud ein bod hash Bart. Felly nawr rydym yn mynd i redeg set newydd o linynnau drwy'r swyddogaeth hash, ac rydym yn rhedeg Bart drwy'r hash swyddogaeth, rydym yn cael hashcode 6. Rydym yn cymryd golwg, rydym yn gweld 6 yw'r gwag, fel y gallwn roi Bart yno. 

Nawr rydym hash Lisa a bod hefyd yn cynhyrchu hashcode 6. Wel nawr ein bod yn defnyddio hyn llinol treiddgar dull yr ydym yn dechrau am 6, rydym yn gweld bod 6 yn llawn. Ni allwn roi Lisa mewn 6. Felly, ble rydyn ni'n mynd? Gadewch i ni fynd i 7. 7 wag, fel eu bod yn gweithio. Felly gadewch i ni roi Lisa yno. 

Nawr rydym hash Homer ac rydym yn cael 7. OK dda yr ydym yn gwybod bod 7 yn llawn erbyn hyn, felly ni allwn roi Homer yno. Felly gadewch i ni fynd i 8. Yw 8 ar gael? Yeah, ac 8 oed yn agos i 7, felly os rhaid i ni ddechrau chwilio ein bod Nid yw mynd i gael i fynd yn rhy bell. Ac felly gadewch i ni roi Homer yn 8. 

Nawr rydym hash Maggie a yn dychwelyd 3, diolch byth rydym yn gallu jyst rhoi Maggie yno. Nid oes rhaid i ni wneud unrhyw math o holi am hynny. Nawr rydym hash Marge, a Marge hefyd yn dychwelyd 6. 

Wel 6 yn llawn, 7 yn llawn, 8 yn llawn, 9, popeth yn iawn diolch i Dduw, 9 yn wag. Gallaf roi Marge am 9. Eisoes gallwn weld ein bod yn dechrau i gael y broblem hon lle erbyn hyn rydym yn dechrau ymestyn pethau caredig o bell i ffwrdd oddi wrth eu codau hash. A bod theta o 1, cyfartaledd y achos o fod yn amser cyson, yn dechrau cael ychydig yn more-- dechrau tueddu ychydig yn fwy tuag at theta o n. Rydym yn dechrau colli hynny mantais o dablau hash. 

Mae hyn yn broblem yr ydym newydd weld yn rhywbeth a elwir yn clystyru. A'r hyn sydd wir yn ddrwg am clystyru yw bod unwaith y byddwch yn awr ddwy elfen sy'n cael eu ochr yn ochr mae'n ei gwneud yn oed yn fwy tebygol, mae gennych dwbl y cyfle, eich bod yn mynd i gael gwrthdrawiad arall gyda hynny clwstwr, a bydd y clwstwr yn tyfu gan un. A byddwch yn cadw dyfu a thyfu eich tebygolrwydd o gael gwrthdrawiad. Ac yn y diwedd 'i' jyst mor ddrwg gan nad didoli data o gwbl. 

Y broblem arall fodd bynnag yw ein o hyd, a hyd yn hyn hyd at y pwynt hwn, rydym newydd wedi bod fath o deall yr hyn tabl hash yw, rydym yn dal dim ond lle i 10 o dannau. Os ydym am barhau i hash dinasyddion Springfield, ni allwn ond cael 10 ohonynt mewn 'na. Ac os ydym yn ceisio ychwanegu 11eg neu 12fed, nid oes gennym le i'w rhoi. Gallai Rydym yn unig fod yn troelli o gwmpas mewn cylchoedd yn ceisio dod o hyd i fan gwag, ac yr ydym efallai mynd yn sownd mewn dolen ddiddiwedd. 

Felly y math hwn o yn rhoi benthyg i'r syniad o rywbeth o'r enw gadwyno. A dyma lle rydym yn mynd i ddod rhestrau cysylltiedig yn ôl i mewn i'r darlun. Beth os hytrach na storio yn unig y data ei hun yn y casgliad, pob elfen y rhesi gallai cynnal lluosog o ddarnau o ddata? Wel nid yw hynny'n gwneud synnwyr, dde? Rydym yn gwybod y gall amrywiaeth yn unig hold-- pob elfen o amrywiaeth dim ond cynnal un darn o ddata o'r math hwnnw data. 

Ond beth os y math hwnnw data yn rhestr cysylltiedig, dde? Felly beth os yw pob elfen y rhesi oedd pwyntydd at bennaeth rhestr cysylltiedig? Ac yna gallem adeiladu rhestrau cysylltiedig y rhai a thyfu eu mympwy, oherwydd bod rhestrau cysylltiedig yn caniatáu ni i dyfu ac yn crebachu llawer mwy hyblyg na amrywiaeth yn ei wneud. Felly beth os ydym yn awr yn defnyddio, rydym yn trosoledd hyn, dde? Rydym yn dechrau tyfu cadwyni hyn y tu allan i leoliadau arae hyn. 

Nawr gallwn ffitio yn ddiddiwedd faint o ddata, neu beidio ddiddiwedd, swm mympwyol o data, i mewn i'n bwrdd hash heb erioed yn rhedeg i mewn i y broblem o gwrthdrawiad. Rydym hefyd wedi dileu clystyru trwy wneud hyn. Ac dda yr ydym yn gwybod bod pan fyddwn yn mewnosod i mewn i restr cysylltiedig, os ydych yn cofio oddi wrth ein fideo ar restrau cysylltiedig, yn unigol rhestrau cysylltiedig a rhestrau cysylltiedig ddwywaith, mae'n llawdriniaeth amser cyson. Rydym yn unig yn ychwanegu at y blaen. 

Ac ar gyfer edrych i fyny, dda yr ydym yn gwybod sy'n edrych i fyny mewn rhestr cysylltiedig Gall fod yn broblem, dde? Mae'n rhaid i ni chwilio drwy mae'n o'r dechrau i'r diwedd. Does dim hap mynediad mewn rhestr cysylltiedig. Ond os yn lle cael un cysylltiedig Rhestr lle byddai am-edrych yn O n, mae gennym bellach 10 o restrau cysylltiedig, neu 1,000 o restrau cysylltiedig, nawr mae'n O o n rannu gan 10, neu O n rhannu â 1,000. 

Ac er ein bod yn siarad ddamcaniaethol am gymhlethdod fe anwybyddir cysonion, yn y go iawn byd y pethau hyn mewn gwirionedd yn fater, iawn? Rydym mewn gwirionedd yn sylwi bod hyn yn digwydd i redeg 10 gwaith yn gyflymach, neu 1,000 o gwaith yn gyflymach, oherwydd ein bod yn dosbarthu'r un hir cadwyn ar draws 1,000 o gadwyni llai. Ac felly bob tro y mae'n rhaid i ni chwilio drwy un o gadwyni rhai y gallwn anwybyddwch y cadwyni 999 Nid ydym yn poeni am, a dim ond yn chwilio bod un. 

Sydd, ar gyfartaledd i fod 1,000 o weithiau fyrrach. Ac felly rydym yn dal yn fath o tueddu tuag at yr achos ar gyfartaledd o fod yn amser cyson, ond Dim ond oherwydd ein bod yn ddylanwad busnes rhannu gan rai ffactor enfawr gyson. Gadewch i ni weld sut y gallai hyn mewn gwirionedd yn edrych er. Felly dyma oedd y tabl hash cawsom cyn i ni ddatgan tabl hash sy'n Roedd gallu storio 10 o dannau. Nid ydym yn mynd i wneud hynny anymore. Rydym eisoes yn gwybod y gyfyngiadau'r dull hwnnw. Nawr ein tabl hash yn mynd i fod amrywiaeth o 10 o nodau, awgrymiadau i benaethiaid rhestrau cysylltiedig. 

Ac ar hyn o bryd mae'n null. Mae pob un o'r rhai 10 awgrymiadau yn null. Does dim byd yn ein hash tabl ar hyn o bryd. 

Nawr, gadewch i ni ddechrau i roi rhai pethau i mewn i dabl hash hwn. A gadewch i ni weld sut mae dull hwn yn mynd i fod o fudd i ni ychydig. Gadewch i ni yn awr hash Joey. Byddwn yn rhedeg y llinyn Joey drwy swyddogaeth hash ac yn dychwelyd 6. Wel beth ydym yn ei wneud nawr? 

Wel bellach yn gweithio gyda rhestrau cysylltiedig, nid ydym yn gweithio gyda arrays. A phan rydym yn gweithio gyda rhestrau cysylltiedig i ni gwybod bod angen i ni ddechrau ddeinamig dyrannu gofod ac adeiladu cadwyni. Dyna fath o how-- dyna'r craidd elfennau o adeiladu rhestr cysylltiedig. Felly gadewch i ni ddeinamig dyrannu lle ar gyfer Joey, ac yna gadewch i ni ychwanegu ef i'r gadwyn. 

Felly, yn awr yn edrych yr hyn yr ydym wedi ei wneud. Pan fyddwn yn hash Joey rydym yn cael y hashcode 6. Nawr bod y pwyntydd yn y lleoliad array 6 yn cyfeirio at y pennaeth rhestr cysylltiedig, ac ar hyn o bryd dyma'r unig elfen o restr cysylltiedig. A'r nôd yn hynny rhestr gysylltiedig yn Joey. 

Felly, os bydd angen i edrych i fyny Joey yn ddiweddarach, rydym yn unig hash Joey eto, rydym yn cael 6 eto oherwydd bod ein swyddogaeth hash yn benderfynedig. Ac yna rydym yn dechrau ym mhen o'r rhestr gysylltiedig sylw at y ffaith i yn ôl lleoliad array 6, a gallwn ailadrodd ar draws y ceisio dod o hyd Joey. Ac os ydym yn adeiladu ein hash tabl yn effeithiol, ac mae ein swyddogaeth hash yn effeithiol i ddosbarthu data'n dda, ar gyfartaledd bob un o'r rhai a cysylltiedig rhestrau ym mhob lleoliad array fydd 1/10 maint pe baem newydd gael fel enfawr sengl rhestr gysylltiedig â phopeth sydd ynddo. 

Os byddwn yn dosbarthu oedd yn cysylltu enfawr Rhestr draws 10 o restrau cysylltiedig Bydd pob rhestr fod 1/10 maint. Ac fel hyn 10 gwaith yn gyflymach i chwilio drwy. Felly, gadewch i ni wneud hyn eto. Gadewch i ni yn awr hash Ross. 

A gadewch i ni ddweud Ross, pan fyddwn yn gwneud hynny y cod hash yr ydym yn mynd yn ôl yw 2. Wel nawr rydym ddeinamig dyrannu nod newydd, rydym yn rhoi Ross yn y nod, ac rydym yn dweud nawr lleoliad array 2, yn lle pwyntio at null, cyfeirio at y pennaeth cysylltiedig Rhestr y mae ei nod yn unig yw Ross. A gallwn wneud hyn yn un mwy o amser, rydym yn Gall hash Rachel a chael hashcode 4. malloc yn nod newydd, rhowch Rachel yn y nôd, ac yn dweud lleoliad arae 4 awr yn cyfeirio at y pen o restr cysylltiedig y mae ei unig elfen digwydd bod Rachel. 

OK ond beth sy'n digwydd os mae gennym gwrthdrawiad? Gadewch i ni weld sut yr ydym yn ymdrin â gwrthdrawiadau gan ddefnyddio'r dull gadwyno ar wahân. Gadewch i hash Phoebe. Rydym yn cael y hashcode 6. Yn ein enghraifft flaenorol roeddem yn unig storio'r tannau yn y rhesi. Roedd hon yn broblem. 

Nid ydym am i trosysgrifo'r Joey, ac rydym wedi eisoes gweld y gallwn gael rhywfaint o glystyru problemau os ydym yn ceisio cam trwy a chwiliedydd. Ond beth os ydym yn unig fath o drin hyn yr un ffordd, dde? Mae'n union fel ychwanegu elfen i bennaeth y rhestr cysylltiedig. Gadewch i le unig malloc i Phoebe. 

Byddwn yn dweud pwyntiau pwyntydd nesaf Phoebe yn i'r hen bennaeth y rhestr cysylltiedig, ac yna 6 dim ond cyfeirio at y pennaeth newydd y rhestr cysylltiedig. Ac yn awr yn edrych, rydym wedi newid Phoebe yn. Gallwn yn awr yn storio dau elfennau gyda hashcode 6, ac nid oes gennym unrhyw broblemau. 

Dyna 'n bert lawer holl mae i gadwyno. Ac gadwyno yn bendant y dull sy'n mynd i fod fwyaf effeithiol i chi os ydych yn storio data mewn tabl hash. Ond mae cyfuniad hwn o araeau a rhestrau cysylltiedig at ei gilydd i ffurfio tabl hash 'n sylweddol yn gwella yn ddramatig eich gallu i storio symiau mawr o ddata, a yn gyflym iawn ac yn effeithlon chwilio trwy ddata hynny. 

Mae dal un yn fwy strwythur data i maes 'na a allai fod hyd yn oed fod ychydig yn well o ran gwarantu bod ein mewnosod, dileu, a Amseroedd edrych i fyny hyd yn oed yn gynt. A byddwn yn gweld bod mewn fideo ar gais. Rwy'n Doug Lloyd, mae hyn yn CS50.