[Ag seinm ceoil] DOUG LLOYD: Faoin am tú fhios ag a lán faoi arrays, agus tá a fhios agat go leor faoi liostaí nasctha. Agus tá muid plé a dhéanamh ar buntáistí agus míbhuntáistí, tá muid a pléadh go liostaí nasctha Is féidir a fháil níos mó agus níos lú, ach a ghlacann siad suas le méid níos mó. Tá arrays i bhfad níos simplí a úsáid, ach tá siad sriantach sa mhéid mar atá againn a shocrú ar an méid de an sraith ag an tús an- agus ansin táimid greamaithe leis. 

Ach go, tá muid go leor i bhfad ídithe i ngach ceann dár topaicí faoi ​​liostaí nasctha agus arrays. Nó mór dúinn? B'fhéidir gur féidir linn a dhéanamh rud éigin fiú níos mó cruthaitheach. Agus gur saghas lends an smaoineamh tábla hash. 

Mar sin, i dtábla hash táimid ag dul chun iarracht a le chéile le sraith le liosta nasctha. Táimid ag dul a chur ar na buntáistí an eagar, cosúil le rochtain randamach, a bheith in ann dul díreach chun eagar eilimint 4 nó sraith eilimint 8 gan a bheith a iterate trasna. Sin go leor go tapa, ceart? 

Ach ba mhaith linn freisin go bhfuil ár sonraí struchtúr a bheith in ann fás agus ag crapadh. Ní chuirimid gá, ní dhéanaimid ag iarraidh a bheith srianta. Agus ba mhaith linn a bheith in ann a chur leis agus rudaí a bhaint an-éasca, agus má tá tú chun cuimhne, Tá an-chasta le sraith. Agus is féidir linn glaoch seo rud nua tábla hash. 

Agus má chuirtear i bhfeidhm i gceart, tá muid ag saghas cur na buntáistí a bhaineann an dá sonraí struchtúir tú atá le feiceáil cheana féin, arrays agus liostaí nasctha. Is féidir le leanas a chur isteach tús a claonadh a bhíonn i dtreo téite de 1. Téite Nach bhfuil pléite againn i ndáiríre, ach tá téite ach an cás ar an meán, cad atá ar siúl i ndáiríre a tharlóidh. Nach bhfuil tú ag dul i gcónaí go dtí tá an chás is measa, agus nach bhfuil tú ag dul i gcónaí a bheith acu an scéal chás is fearr, mar sin cad atá an meán scéal? 

Bhuel an chur isteach ar an meán isteach i dtábla hash Is féidir tús a chur a fháil gar go ham tairiseach. Agus is féidir a scriosadh a fháil gar go ham tairiseach. Agus is féidir a chuardach a fháil gar go ham tairiseach. That's-- nach bhfuil againn a sonraí Struchtúr ach is féidir a dhéanamh, agus mar sin an fuaimeanna cheana cosúil le rud deas mór. Táimid tar éis a mhaolú i ndáiríre an míbhuntáistí a bhaineann le gach ceann ar a chuid féin. 

Chun a fháil ar an fheidhmíocht uasghrádú áfach, táimid ag Ní mór a rethink conas chur linn sonraí isteach i struchtúr. Go sonrach, ba mhaith linn an sonraí féin a insint dúinn nuair ba chóir dó dul i struchtúr. Agus más gá dúinn ansin a fheiceáil má tá sé i an struchtúr, más gá dúinn a fháil air, ba mhaith linn chun breathnú ar na sonraí arís agus a bheith in ann go héifeachtach, ag baint úsáide as na sonraí, go randamach rochtain a fháil air. Díreach trí bhreathnú ar an Ba chóir go mbeadh na sonraí atá againn smaoineamh ar an áit ina bhfuil muid go díreach dul chun é a fháil sa tábla hash. 

Anois an downside de hash Tá tábla go mbíonn siad i ndáiríre olc go leor ag ordú nó a shórtáil sonraí. Agus go deimhin, má thosaíonn tú chun iad a úsáid chun a ordú nó a shórtáil sonraí a chailleann tú gach ceann de na buntáistí agat cheana Bhí thaobh a chur isteach agus a scriosadh. Éiríonn an t-am níos gaire do téite n, agus muid go bunúsach regressed i liosta nasctha. Agus mar sin ba mhaith linn ach hash a úsáid táblaí más rud é nach bhfuil muid cúram faoi cibé an bhfuil na sonraí curtha in eagar. Maidir leis an comhthéacs ina go mbainfidh tú iad a úsáid i CS50 tú dócha nach bhfuil cúram go bhfuil na sonraí curtha in eagar. 

Dá bhrí sin tá tábla hash meascán de dhá phíosa ar leith lena bhfuil muid ar an eolas. Is é an chéad feidhm, a tugaimid de ghnáth feidhm hash. Agus is é sin an fheidhm hash ag dul go dtí ar ais roinnt slánuimhir neamh-diúltach, a tugaimid de ghnáth hashcode, ceart go leor? Is é an dara píosa le sraith, a bhfuil in ann sonraí a stóráil ar an linn a chineál ag iarraidh a chur isteach sa struchtúr sonraí. Beidh muid a shealbhú amach ar an nasctha eilimint liosta do anois agus díreach tús a chur leis an Basics de hash tábla a fháil do cheann timpeall air, agus ansin beidh muid buille b'fhéidir d'intinn le beagán nuair a muid arrays agus liostaí nasc le chéile le chéile. 

An smaoineamh bunúsach cé go Is chur orainn roinnt sonraí. Rithimid go bhfuil sonraí trí an fheidhm hash. Agus mar sin bpróiseálfar na sonraí go agus spits sé amach roinnt, ceart go leor? Agus ansin leis an uimhir táimid ag a stóráil go díreach ar na sonraí ba mhaith linn a stóráil sa sraith ag an suíomh sin. Mar sin, mar shampla, ní mór dúinn b'fhéidir an tábla hash de teaghráin. Tá sé fuair 10 eilimintí i sé, mar sin Is féidir linn a oiriúnach ar 10 teaghráin ann. 

Ligean le rá ba mhaith linn a hash John. Mar sin, John leis na sonraí ba mhaith linn a chur isteach isteach sa tábla hash áit éigin. Nuair a dhéanann muid a chur air? Well ghnáth le sraith go dtí seo táimid ag is dócha go mbeadh sé a chur i suíomh eagar 0. Ach anois ní mór dúinn an fheidhm hash nua. 

Agus a ligean ar rá go reáchtáil againn John tríd an fheidhm hash agus tá spits sé amach 4. Bhuel sin an áit mbeimid dul go dtí gur mian a chur John. Ba mhaith linn a chur ar John i suíomh eagar 4, mar má táimid ag hash John again-- ligean le rá ina dhiaidh sin táimid ag ag iarraidh a chuardach agus a fheiceáil más ann Seán sa hash table-- go léir is gá dúinn a dhéanamh Tá rith sé tríd an hash céanna fheidhm, a fháil ar an uimhir 4 out, agus a bheith in ann teacht ar John díreach in ár struchtúr sonraí. Sin maith go leor. 

Ligean le rá linn a dhéanamh anois seo arís, ba mhaith linn a hash Pól. Ba mhaith linn a chur Paul isteach sa tábla hash. A ligean ar rá go bhfuil an am seo reáchtáil againn Paul tríd an fheidhm hash, is é an hashcode a ghintear 6. Bhuel anois is féidir linn a chur Paul sa suíomh eagar 6. Agus más gá dúinn a breathnú suas cé acu Tá paul sa tábla seo hash, gach ní mór dúinn a dhéanamh ná a reáchtáil Paul tríd an fheidhm hash arís agus táimid ag dul a fháil ar 6 as arís. 

Agus ansin dúinn ach breathnú ag suíomh eagar 6. Paul ann? Más amhlaidh, tá sé sa tábla hash. Paul ní ann? Níl sé sa tábla hash. Tá sé deas simplí. 

Anois, conas a dhéanann tú a shainiú feidhm hash? Bhuel níl i ndáiríre níl aon teorainn leis an roinnt feidhmeanna hash is féidir. Go deimhin níl roinnt i ndáiríre, cinn gur maith ar an idirlíon. Níl roinnt de i ndáiríre, cinn go dona ar an idirlíon. Tá sé éasca go leor freisin a scríobh aon droch. 

Mar sin, cad a dhéanann suas le dea- fheidhm hash, ceart? Bhuel Ba chóir feidhm hash maith a úsáid ach amháin na sonraí á hashed, agus gach ceann de na sonraí atá á hashed. Mar sin ní féidir linn a iarraidh úsáid a bhaint anything-- ní féidir linn aon rud a ionchorprú eile seachas na sonraí. Agus ba mhaith linn a bhaint as gach ceann de na sonraí. Ní chuirimid iarraidh a úsáid ach píosa de, ba mhaith linn a bhaint as ar fad é. Ba chóir feidhm hash freisin a bheith deterministic. Cad is brí le sin? Bhuel ciallaíonn sé go bhfuil gach uair linn a pas a fháil sa phíosa ceannann céanna sonraí isteach ar an fheidhm hash muid i gcónaí a fháil ar an hashcode céanna amach. Má éiríonn liom John isteach sa fheidhm hash rachaidh mé amach 4. Ba chóir dom a bheith in ann a dhéanamh go 10,000 amanna agus beidh mé a fháil i gcónaí 4. Mar sin, aon uimhreacha randamacha go héifeachtach Is féidir a bheith páirteach inár hash tables-- inár feidhmeanna hash. 

Ba chóir feidhm hash freisin haonfhoirmeach dháileadh sonraí. Más rud é gach uair a ritheann tú na sonraí tríd an fheidhm hash gheobhaidh tú an hashcode 0, go dócha nach chomh mór sin, ceart? Ba mhaith leat is dócha go mór réimse cóid hash. Freisin, is féidir rudaí a leathadh amach ar fud an tábla. Agus chomh maith go mbeadh sé go hiontach má ndáiríre sonraí den chineál céanna, cosúil le John agus Jonathan, Cuireadh leathadh amach b'fhéidir a mheá áiteanna éagsúla sa tábla hash. Bheadh ​​sin a bheith ina buntáiste deas. 

Seo sampla d'fheidhm hash. Scríobh mé an ceann seo suas níos luaithe. Níl sé ina háirithe fheidhm hash maith ar chúiseanna nach é sin a dhéanamh i ndáiríre iompróidh dul isteach ceart anois. Ach an bhfuil tú a fheiceáil cad atá ar siúl anseo? Dealraíonn sé cosúil tá muid ag á dhearbhú athróg ar a dtugtar suim agus leagan sé cothrom le 0. Agus ansin cosúil tá mé ag déanamh rud éigin fad a bheidh strstr [j] nach bhfuil comhionann a cúlslais 0. Cad tá mé ag déanamh ann? 

Tá sé seo go bunúsach ach eile mhodh a chur chun feidhme [? strl?] agus a bhrath nuair atá tú shroich an deireadh an teaghráin. Mar sin, ní dóigh liom go bhfuil a ndáiríre ríomh an fad na sreinge, Tá mé ag baint úsáide as ach nuair a bhuail mé an cúlslais 0 carachtar a fhios agam Tá mé shroich an deireadh an teaghráin. Agus ansin mé ag dul a choinneáil iterating tríd an teaghrán, ag cur strstr [j] chun achoimre, agus ansin ag an deireadh an lae ag dul a thabhairt ar ais suim mod HASH_MAX. 

Go bunúsach go léir hash seo Tá feidhm ag déanamh go bhfuil ag cur suas gach ceann de na luachanna ASCII de mo teaghrán, agus ansin tá sé ag filleadh ar roinnt hashcode modded ag HASH_MAX. Tá sé dócha go bhfuil an méid mo eagar, ceart? Níl mé ag iarraidh a bheith ag fáil hash cóid má tá mo sraith de mhéid 10, Níl mé ag iarraidh a bheith ag fáil cóid hash amach 11, 12, 13, ní féidir liom a rudaí a chur isteach i na suímh na eagar, bheadh ​​mídhleathach. Ba mhaith liom a fulaingt locht deighilt. 

Anois tá anseo ceann eile mear ar leataobh. Go ginearálta bhíonn tú is dócha nach bhfuil ag dul go dtí ag iarraidh a scríobh do fheidhmeanna hash féin. Tá sé i ndáiríre le beagán de ealaíne, ní eolaíocht. Agus níl a lán a théann isteach iad. An idirlíon, mar a dúirt mé go bhfuil, iomlán feidhmeanna hash gur maith, agus ba chóir duit a bhaint as an idirlíon a teacht ar feidhmeanna hash mar tá sé i ndáiríre ach de chineál ar gan ghá amú ama a chruthú do chuid féin. 

Is féidir leat scríobh na cinn simplí chun críocha tástála. Ach nuair a dhéanann tú i ndáiríre ag dul a tús sonraí hashing agus a stóráil isteach i dtábla hash bhfuil tú is dócha ag dul go dtí gur mian úsáid a bhaint as roinnt feidhm gineadh go ar do shon, ann sin ar an idirlíon. Má dhéanann tú ach a bheith cinnte a luann d'fhoinsí. Níl aon chúis a rud ar bith plagiarize anseo. 

Is é an pobal eolaíochta ríomhaireachta cinnte ag fás, agus i ndáiríre luachanna foinse oscailte, agus tá sé tábhachtach i ndáiríre a luann do fhoinsí ionas go mbeidh daoine Is féidir le sannadh a fháil le haghaidh an obair go bhfuil siad ag déanamh chun leasa an phobail. Mar sin, a bheith i gcónaí sure-- agus ní hamháin ar hash feidhmeanna, ach de ghnáth nuair a dhéanann tú úsáid a bhaint as cód ó fhoinse taobh amuigh, cite i gcónaí do foinse. Tabhair creidmheasa leis an duine a rinne cuid den obair sin ní gá duit a. 

OK mar sin a ligean ar athchuairt seo tábla hash le haghaidh an dara. Tá sé seo nuair a d'fhág muid amach tar éis cuireadh isteach táimid ag Eoin agus Paul isteach sa tábla hash. An bhfeiceann tú fadhb anseo? D'fhéadfá a fheiceáil dhá. Ach go háirithe, an bhfuil tú féach ar an fhadhb seo is féidir? 

Cad a tharlaíonn má hash mé Ringo, agus é a casadh amach gur tar éis a phróiseáil sonraí tríd an fheidhm hash Ringo ghintear chomh maith leis an hashcode 6. Tá mé cheana sonraí ag suíomh eagar hashcode-- 6. Mar sin, tá sé is dócha ag dul a bheith le beagán de fadhb dom anois, ceart? 

Tugaimid seo imbhualadh. Agus a tharlaíonn an imbhualadh nuair a dhá píosaí de shonraí reáchtáil trí mheán an hash céanna fheidhm toradh an hashcode céanna. Is dócha ba mhaith linn go fóill a fháil ar an dá píosaí de shonraí isteach sa tábla hash, nó ní ba mhaith linn a bheith ag rith Ringo treallach tríd an fheidhm hash. Ba mhaith linn is dócha a fháil Ringo isteach eagar. 

Conas is féidir linn é a dhéanamh áfach, má tá sé agus Paul araon toradh hashcode 6? Ní chuirimid iarraidh a fhorscríobh Paul, ba mhaith linn Paul a bheith ann freisin. Mar sin, ní mór dúinn a fháil ar bhealach a fháil eilimintí isteach sa tábla hash go caomhnaíonn fós ár tapaidh a chur isteach agus tapa breathnú suas. Agus is é bealach amháin chun déileáil leis é a rud ar a dtugtar líneach deacra a dhéanamh. 

Ag baint úsáide as an modh seo má táimid tar éis imbhualadh, go maith, cad a dhéanaimid? Bhuel ní féidir linn a chur air i suíomh eagar 6, nó bhí a ghintear cuma cén hashcode, a ligean ar a chur chuige ag hashcode móide 1. Agus más rud é go ligean iomlán ar a chur air i hashcode móide 2. Ar mhaithe seo a bheith má tá sé Ní go díreach nuair a cheapann muid go bhfuil sé, agus ní mór dúinn chun tús a chuardach, b'fhéidir nach bhfuil againn chun dul i bhfad ró. B'fhéidir nach bhfuil againn chun cuardach a gach eilimint n den tábla hash. B'fhéidir go bhfuil muid chun cuardach a cúpla ceann acu. 

Agus mar sin tá muid ag aireachasú i dtreo go fóill chás meán a bheith gar do 1 vs gar do n, agus mar sin b'fhéidir go mbainfidh an obair sin. Mar sin a ligean ar a fheiceáil conas an D'fhéadfadh obair amach i ndáiríre. Agus a ligean ar féach an féidir linn a bhrath b'fhéidir an fhadhb a d'fhéadfadh tarlú anseo. 

Ligean le rá hash linn a Bart. Mar sin, anois táimid ag dul a reáchtáil sraith nua de teaghráin tríd an fheidhm hash, agus reáchtáil againn Bart tríd an hash fheidhm, a fháil againn hashcode 6. Glacann muid le breathnú, feicimid go bhfuil 6 folamh, ionas gur féidir linn a chur Bart ann. 

Anois táimid ag hash Lisa agus go Gineann freisin hashcode 6. Bhuel anois go bhfuil muid ag baint úsáide as an líneach probing modh tús a chur orainn ag 6, feicimid go bhfuil 6 iomlán. Ní féidir linn a chur Lisa i 6. Mar sin, i gcás ina bhfuil muid ag dul? A ligean ar dul go dtí 7. 7 ar folamh, mar sin go n-oibríonn. Mar sin, a ligean ar a chur Lisa ann. 

Anois táimid ag hash Homer agus a fhaigheann muid 7. OK go maith a fhios againn go bhfuil 7 ar iomlán anois, mar sin ní féidir linn a chur Homer ann. Mar sin, a ligean ar dul go dtí 8. Is 8 ar fáil? Yeah, agus 8 ar gar do 7, mar sin má ní mór dúinn chun tús a chuardach táimid nach bhfuil ag dul a bheith acu chun dul i bhfad ró. Agus mar sin a ligean ar a chur Homer ag 8. 

Anois táimid ag hash Maggie agus Filleann 3, buíochas a ghabháil feabhas tá muid in ann a chur díreach Maggie ann. Nach bhfuil againn a dhéanamh ar bith saghas probing as sin. Anois táimid ag hash Marge, agus Marge tuairisceáin freisin 6. 

Is Bhuel 6 iomlán, 7 is iomlán, 8 Is é iomlán, 9, ceart go léir buíochas le Dia, 9 folamh. Is féidir liom a chur Marge ag 9. Cheana féin is féidir linn a fheiceáil go bhfuil muid ag tosú go bhfuil an fhadhb seo i gcás anois tá muid ag tosú chun rudaí a stráice de chineál de i bhfad ar shiúl óna cóid hash. Agus sin téite de 1, an meán sin gcás a bheith am tairiseach, ag tosú a fháil ar more-- beag ag tosú a claonadh a bhíonn beagán níos mó i dtreo téite de n. Táimid ag tosú a chailleadh go leas a bhaint as táblaí hash. 

An fhadhb seo a chonaic muid díreach Tá rud ar a dtugtar braisliú. Agus cad atá i ndáiríre go dona faoi Is braisliú go uair tú anois Tá dhá ghné atá taobh le taobh dhéanann sé sé níos mó seans, tá tú dhá oiread an seans, go bhfuil tú ag dul a bheith acu imbhualadh eile leis braisle, agus beidh an bhraisle fás ag amháin. Agus beidh tú a choinneáil ag fás agus ag fás do dóchúlacht a bhfuil imbhualadh. Agus ar deireadh thiar tá sé díreach chomh dona mar nach sórtáil na sonraí ar chor ar bith. 

Is í an fhadhb eile cé go táimid ag go fóill, agus sa mhéid suas go dtí an bpointe seo, táimid ag Bainim díreach saghas tuiscint cad é tábla hash, againn fós ach tseomra ar feadh 10 teaghráin. Más mian linn leanúint ar aghaidh ag hash na saoránaigh de Springfield, Is féidir linn a fháil ach 10 acu in ann. Agus má táimid iarracht a dhéanamh agus cuir 11ú nó 12ú, nach bhfuil againn áit chun iad a chur. D'fhéadfadh muid díreach a bheith sníomh timpeall i ciorcail ag iarraidh teacht ar an láthair folamh, agus táimid ag b'fhéidir a fháil greamaithe i lúb gan teorainn. 

Mar sin, an saghas lends leis an smaoineamh de rud ar a dtugtar shlabhrú. Agus é seo i gcás ina bhfuil muid ag dul a thabhairt liostaí nasctha ar ais isteach an pictiúr. Cad a tharlaíonn má in ionad an stóráil díreach na sonraí féin sa eagar, gach gné den eagar fhéadfadh shealbhú píosaí iolraí de shonraí? Bhuel nach bhfuil ciall a bhaint as, ceart? Tá a fhios againn go gur féidir le sraith amháin hold-- gach eilimint de sraith Is féidir a shealbhú ach píosa amháin sonraí den chineál sonraí. 

Ach cad más rud é go bhfuil an cineál sonraí Tá liosta nasctha, ceart? Mar sin, cad más rud é gach Ba ghné na eagar pointeoir chuig ceann de liosta nasctha? Agus ansin d'fhéadfadh muid a thógáil na liostaí nasctha agus iad ag fás treallach, mar gheall ar liostaí nasctha a cheadú dúinn chun fás agus Laghdaigh a lán níos mó solúbtha ná mar a dhéanann eagar. Mar sin, cad má úsáidimid anois, linn a ghiaráil seo, ceart? Tús a chur againn ag fás ar na slabhraí amach as na suímh eagar. 

Anois is féidir linn oiriúnach ar gan teorainn méid na sonraí, nó nach gan teorainn, méid treallach de sonraí, isteach inár tábla hash gan riamh ag rith isteach fadhb na imbhualadh. Táimid tar éis a dhíchur freisin braisliú trí é seo a. Agus go maith a fhios againn go nuair a chur isteach a chuirimid i liosta nasctha, más rud é tá tú chun cuimhne as ár físeán ar liostaí nasctha, ina n-aonar liostaí nasctha agus liostaí nasctha doubly, tá sé ina oibríocht am tairiseach. Táimid ag cur go díreach chun tosaigh. 

Agus do breathnú suas, go maith a fhios againn go breathnú suas i liosta nasctha Is féidir a bheith ina fhadhb, ceart? Ní mór dúinn a cuardach a dhéanamh trí sé ó thús go deireadh. Níl aon randamach Rochtain ar liosta nasctha. Ach más rud é in ionad a bheith ar cheann nasctha liosta ina mbeadh Lookup bheith O n, ní mór dúinn anois ar 10 liostaí nasctha, nó 1,000 liostaí nasctha, anois tá sé O de n arna roinnt 10, nó O de n arna roinnt 1,000. 

Agus fad is a bhí muid ag caint teoiriciúil faoi chastacht linn a neamhaird Tairisigh, sa fíor domhan na rudaí ábhar i ndáiríre, ceart? Beidh muid a faoi deara go hiarbhír go dtarlaíonn sé seo a reáchtáil 10 huaire níos tapúla, nó 1,000 uair níos tapúla, mar gheall orainn ag dáileadh ceann fada slabhra thar 1,000 slabhraí níos lú. Agus mar sin gach uair ní mór dúinn chun cuardach a trí cheann de na slabhraí féidir linn neamhaird a dhéanamh ar an 999 slabhraí ní dhéanaimid cúram faoi, agus díreach a chuardach go bhfuil ceann. 

Cé acu is ar an meán a a bheith 1,000 uair níos giorra. Agus mar sin táimid fós saghas aireachasú i dtreo an cás ar an meán a bhaineann le bheith am tairiseach, ach ach amháin mar gheall orainn ag giaráil roinnt ar roinnt fachtóir tairiseach ollmhór. A ligean ar a fheiceáil conas a d'fhéadfadh sé seo breathnú i ndáiríre cé. Mar sin, ba é seo an tábla hash bhí againn roimh dhearbhú táimid ag tábla hash go Bhí ann a stóráil 10 teaghráin. Níl muid ag dul a dhéanamh sin níos mó. Tá a fhios againn cheana féin ar an teorainneacha sin modh. Anois tá ár tábla hash ag dul a bheith le sraith de 10 nóid, leideanna le ceannairí na liostaí nasctha. 

Agus an ceart anois tá sé null. Tá gach ceann de na 10 leideanna null. Níl aon rud in ár hash tábla ceart anois. 

Anois, a ligean ar tús a chur ar roinnt rudaí isteach sa tábla hash. Agus a ligean ar a fheiceáil conas é seo an modh dul chun sochair dúinn le beagán. A ligean ar hash anois Joey. Beidh muid a reáchtáil an teaghrán Joey trí feidhm hash agus muid ar ais 6. Bhuel cad a dhéanann muid anois? 

Bhuel anois ag obair le liostaí nasctha, nach bhfuil muid ag obair le arrays. Agus nuair a bhíonn muid ag obair le liostaí nasctha linn a tá a fhios is gá dúinn a thosú dinimiciúil leithdháileadh slabhraí spás agus tógála. Sin saghas how-- sin iad na croí gnéithe de thógáil liosta nasctha. Sin a ligean le dinimiciúil spás a leithdháileadh le haghaidh Joey, agus ansin a ligean ar chur air go dtí an slabhra. 

Mar sin, breathnú anois an méid atá déanta againn. Nuair a hash táimid ag Joey fuair muid an hashcode 6. Anois an pointeoir ag suíomh eagar 6 pointí go dtí an ceann liosta nasctha, agus an ceart anois tá sé an t-aon eilimint de liosta nasctha. Agus an nód sa mhéid is go tá liosta de na nasctha Joey. 

Mar sin, más gá dúinn chun breathnú suas Joey ina dhiaidh sin, táimid ag hash ach Joey arís, a fháil againn 6 arís mar gheall ar ár Is é feidhm hash deterministic. Agus ansin tús a chur againn ag ceann an liosta nasctha Léirigh go de réir suímh eagar 6, agus is féidir linn a iterate trasna go bhfuil ag iarraidh a fháil Joey. Agus má thógáil againn ár hash tábla héifeachtach, agus ár fheidhm hash go héifeachtach chun sonraí a dháileadh go maith, ar an meán gach ceann de na nasctha liostaí ag gach suíomh eagar Beidh 1/10 an méid má táimid ach bhí sé mar ollmhór amháin liosta a nasctha le gach rud ann. 

Má dháil amach againn go mór atá nasctha liosta thar 10 liostaí nasctha Beidh gach liosta a bheith 1/10 an méid. Agus dá bhrí sin 10 uair níos tapúla a cuardach a dhéanamh trí. Mar sin, a ligean ar é seo a dhéanamh arís. A ligean ar hash anois Ros Mhic Thriúin. 

Agus a ligean le rá Ross, nuair a dhéanann muid go Is é an cód hash a fháil againn ar ais 2. Bhuel anois táimid ag leithdháileadh dinimiciúil a nód nua, chuir muid Ros Mhic Thriúin sa nód, agus a rá againn anois suíomh eagar 2, in ionad dírithe ar null, pointí go dtí an ceann nasctha tá liosta de na a bhfuil a nód amháin Ross. Agus is féidir linn é seo a níos mó ama amháin, táimid ag Is féidir le hash Rachel agus hashcode 4 a fháil. malloc nód nua, a chur i Rachel an nód, agus a rá a suíomh eagar 4 pointí anois go dtí an ceann de liosta nasctha a bhfuil a tharlaíonn eilimint amháin a bheith Rachel. 

OK ach cad a tharlaíonn má ní mór dúinn a imbhualadh? A ligean ar a fheiceáil conas a láimhseáil linn a imbhuailtí baint úsáide as modh shlabhrú ar leith. A ligean ar hash Phoebe. Faighimid an hashcode 6. I ár shampla roimhe seo bhí muid díreach stóráil na teaghráin sa eagar. Bhí sé seo ina fhadhb. 

Nílimid ag iarraidh a clobber Joey, agus muid cheana le feiceáil gur féidir linn a fháil ar roinnt braisliú fadhbanna má iarracht muid agus céim trí agus probe. Ach cad má muid díreach de chineál ar chóireáil seo ar an mbealach céanna, ceart? Tá sé díreach cosúil le cur gné chuig ceann liosta nasctha. A ligean ar spás ach malloc do Phoebe. 

Beidh orainn a rá pointí pointeoir seo chugainn Phoebe s go dtí an ceann d'aois ar an liosta nasctha, agus ansin 6 pointí díreach go dtí an ceann nua ar an liosta nasctha. Agus táim ag anois, tá muid athraigh Phoebe i. Is féidir linn a stóráil anois dhá eilimintí a bhfuil hashcode 6, agus ní dhéanaimid aon fadhbanna. 

Sin go leor i bhfad go léir tá le shlabhrú. Agus is é shlabhrú cinnte an modh sin ag dul a bheith is éifeachtaí duit má tá tú ag a stóráil sonraí i dtábla hash. Ach seo meascán de arrays agus liostaí nasctha le chéile chun foirm a tábla hash i ndáiríre mór tagtha ar feabhas ar do chumas a stóráil suimeanna móra sonraí, agus go han-tapa agus go héifeachtach cuardaigh trí na sonraí sin. 

Níl fós amháin níos mó Struchtúr sonraí amach ann d'fhéadfadh a bheith fiú beagán níos fearr i dtéarmaí a ráthú go bhfuil ár a chur isteach, scriosadh, agus Is breathnú suas amanna fiú níos tapúla. Agus beidh orainn a fheiceáil go bhfuil i físeán ar iarracht. Tá mé Doug Lloyd, is é seo CS50.