[Musika jotzen] DOUG LLOYD: orain By duzu Array buruz asko jakin, eta lotutako zerrendak buruz asko ezagutzen duzu. Eta eztabaidatzeko dugu abantailak eta desabantailak, dugu zerrendak lotuta dagoela eztabaidatu handiagoa eta txikiagoa lor daiteke, baina hartu zuten tamainako gehiago. Arrayak askoz gehiago zuzenean daude erabili, baina murriztailea ari dira bezainbeste batean tamaina ezartzeko dugun bezala hasieran oso array eta orduan ari gara bertan gelditzen da. Hori, ordea, nahiko askoz dugu Gure gaien guztiak agortu zerrendak lotuta array buruz. Edo behar dugu? Agian zerbait egin dezakegu are gehiago sortzaile. Eta erabaki moduko hori Hash taula baten ideia. Beraz, hash taula bat ere ari gara saiatzen joan array bat konbinatu lotuta zerrenda batekin. Abantaila hartu goaz Array, ausazko sarbidea bezala, ahal izateko besterik joan array nahi izateagatik elementu 4 edo array elementu 8 zehar batetik bestera joateko beharrik gabe. Hori nahiko azkarra, ezta? Baina, era berean, gure datu eduki nahi dugu egitura izango hazten eta txikitu gai. Ez dugu behar, ez dugu mugatuta egon nahi. Eta gai izan nahi dugu gehitzeko eta gauzak kendu Oso erraz, zein gogoratzen baduzu, oso konplexua sorta batekin da. Eta hau esan genezake hash taula bat gauza berria. Eta behar bezala eginez gero, sort gara hartzen dugu bai datuak abantailak Dagoeneko ikusi duzu egiturak, array eta zerrendak lotutako. Txertatze has daiteke 1 theta norabidean joera. Theta ez dute benetan aztertu ditugu, baina theta batez beste kasu besterik ez da, zer benetan gertatuko. Oraindik ez duzu beti joan kasu okerrena izan, eta ez zaren beti behar joan kasurik onenean, beraz, zer da Bidaiarien batez besteko eszenatoki? Beno bataz-sartzeak bat hash taula batean etengabeko denbora hurbiltzeko has daiteke. Eta ezabatzeko lor daiteke etengabeko denbora itxi. Eta bilatu lor daiteke etengabeko denbora itxi. That ez dugu datu bat izan egitura oraindik hori egin daiteke, eta, beraz, honek dagoeneko soinuak gauza nahiko handi bat bezala. Nik benetan arindu dugu bakoitzaren desabantailak bere kabuz. Performance hau lortzeko berritzea arren, ez dugu birpentsatzeko nola dugu gehitzeko behar den egitura sartu datuak. Hain zuzen ere nahi dugu Datu bera kontatzen digu, non behar egitura ere joan da. Eta bada, ondoren, behar dugun da, ikusteko egitura, hura aurkitu behar badugu, Datuak begiratu nahi dugu behin eta egin ahal izango dute, modu eraginkorrean, datuak erabiliz, ausaz sar ezazu. Just begira Datu izan behar dugu non zehatz-mehatz ari garen ideia bat aurkitu hash taula doa. Orain egiaztapen bat arazotxo mahai benetan ari dira nahiko txarra ordenatzen edo datuen arabera ordenatzeko at. Eta hain zuzen ere, hasiko baduzu horiek erabili ahal izateko, edo horrelako galtzen duzu datu guztiak abantailak aurretik zuk eta ezabaketa dagokionez izan. Denbora bihurtzen gertuago theta n, eta guk dut funtsean Lotuta zerrenda atzera. Eta horrela bakarrik hash erabili nahi dugu mahaiak ez badugu zaintzeko Datu ordenatuko da ala ez. Testuinguruan bertan Horiek erabili ahal izango duzu CS50 Ziurrenik ez duzu axola Datu hori horrela antolatu. Beraz, hash taula bat konbinazioa da bi pieza desberdin baten bertan ezagutzen ari gara. Lehenengo eta behin, funtzio bat da, eta horrek Ohi hash funtzio bat deitu dugu. Eta hash funtzio hori joan itzuli zenbaki oso ez negatiboa batzuk, eta horrek Ohi hashcode deritzogu, OK? Bigarren pieza sorta bat, eta hori da mota dugun du datuak gordetzeko gai Datuen egitura sartu jarri nahi. Eutsi off egingo dugu buruzko Zerrenda elementu lotuta oraingoz eta besterik baten oinarriak hasteko Hash taula zure burua lortzeko bere inguruan, eta orduan, agian egingo dugu putz zure burua pixka bat dugunean matrizeak eta link zerrendak konbinatu batera. Oinarrizko ideia arren datu batzuk hartu ditugu. Datu hori zehar ibiltzen gara hash funtzioa. Eta beraz, datuak prozesatu eta zenbaki bat spits, OK? Eta gero, zenbaki horrekin datuak gordetzeko besterik ez dugu to the gorde nahi dugu kokapena hartan array. Beraz, adibidez, agian ez dugu hash kateen mahai honetan. Honez bertan 10 elementu lortu, beraz, 10 kateak doi dezakegu bertan. Demagun John hash nahi dugu. Beraz, John txertatu nahi ditugu, datu gisa Hash taula hau nonbait sartu. Nora jarri dugu? Beno, normalean batekin array orain arte seguruenik dugu jartzen array kokapena 0 da. Baina orain hash funtzio berri hau dugu. Eta demagun John run garela hash funtzio honen bidez eta nik tu egiten du 4. Beno, hortxe gaude John jarri nahi du. John jarri array kokapena Nahi dugu 4, John hash bagenu, berriro delako demagun geroago dugu bilatu eta ikusi nahi John hash hau badago mahaian egin behar dugun guztia da hash bera zehar ibiltzen da funtzioa, lortu zenbakia 4 out, eta gai izango John aurkitu Berehala gure datu-egitura. Hori nahiko ona. Demagun orain egiten dugun honetan Berriro, Paul hash nahi dugu. Paul gehitu nahi dugu hash taula batean. Demagun exekutatu dugu denbora honetan Paul hash funtzio bidez, bat sortzen da, hashcode 6 da. Beno, orain, Paul jarri ahal izango dugu Array kokapena 6 ere. Eta ala bilatuko behar badugu Paul hash taula hau da, Egin behar dugun guztia da exekutatu Paul hash funtzioa bidez berriro eta 6 ateratzeko berriro joan ginen. Eta gero, begiratu besterik ez dugu array kokapena 6 etan. Paul ez? Hala bada, da hash taula zuen. Paul, ez dago? Bera ez da hash taula. Nahiko erraza da. Orain, nola ez, hash funtzio bat definitzen duzu? Beno, ez da benetan ez du mugarik Posible hash funtzio kopurua. Izan ere, zenbaki bat da, benetan, Interneten benetan onak. Badira zenbaki bat da benetan, Interneten benetan txarra ere bai. Gainera, nahiko erraza da txarra bat idazteko. Beraz, zerk ona hash funtzioa, ezta? Beno hash funtzioa ona egin beharko lukete bakarrik ari hash- datuak erabili, eta ari hash- datu guztiak. Beraz, ez dugu nahi ezerk baino erabili Ez dugu ezer erantsiko Bestela datuak baino beste. Eta datu guztiak erabili nahi dugu. Ez dugu nahi pieza bat bakarrik erabili hura, hura guztia erabili nahi dugu. Hash funtzioa beharko lukete A halaber determinista izan. Zer esan nahi du horrek? Beno, esan nahi du, aldi bakoitzean dugu zehatza datuak pieza bera pasatzen Hash funtzioa dugu beti the hashcode bera lortu. Pasatzen dut John bada sartu hash funtzioa ateratzeko I 4. Horretarako gai izan behar dut 10.000 aldiz eta ez dut beti lortu 4. Beraz ausazko zenbakiak ez eraginkortasunez den gure hash inplikatutako daiteke tables-- gure hash funtzioak. Hash funtzioa behar ere uniformeki datuak banatu. Bidez datuak exekutatzen duzunetan bada hash funtzioa hashcode 0 eta lortuko duzu, Hori ez da, seguruenik, hain handia da, ezta? Ziurrenik dezakezu big nahi hash kodeak sorta bat. Era berean, gauzak zabaldu ahal izango da mahai zehar egindako. Eta, gainera, handia izango litzateke benetan bada antzeko datuak, John eta Jonathan bezala, Agian zabaldu ziren pisatzen Hash taula leku desberdinetan. Hori polita abantaila bat izango litzateke. Hemen hash funtzio bat adibide bat. Inork idatzitakoa up lehenago dut. Ez da bereziki bat hash funtzioa ona benetan ez duten arrazoiak direla-eta bear oraintxe sartu. Baina zer gertatzen da hemen ikusten duzu? Aldagai bat deklaratzen dugun bezala ari dela dirudi batuketa eta 0 berdina ezarriz deitzen. Eta gero, itxuraz zerbait egiten ari naiz hain luze strstr [j] ez da berdin 0 backslash to. Zer ari naiz hor? Hau da, funtsean, besterik gabe, beste gauzatzeko [modu? Strl?] eta detektatzeko denean duzun kate amaiera iritsi. Beraz, ez daukat benetan luzera kalkulatzeko katea, Besterik ez denean hit I naiz erabiliz backslash 0 pertsonaia dakit Katea amaieran Iritsi dut. Eta ondoren, naiz mantentzeko joan kate horretan zehar errepikatzean, , laburbildu strstr [j] gehituz eta ondoren hartu du Egunaren amaieran batura mod itzuli egingo da HASH_MAX. Funtsean hash hau guztia funtzioa egiten ari dena gehituz ASCII balioak guztia Nire katea, eta, ondoren, hashcode batzuk itzuli HASH_MAX arabera modded. Seguruenik tamainaren nire array, ezta? Ez dut nahi den hash lortzean kode nire array tamaina 10 da, bada, Ez dut lortzean izan nahi out hash 12 kodeak 11, 13 Ezin dut jarri gauzak sartu Array kokapenak horiek, hori legez kanpokoa izango litzateke. Segmentazio errua jasango nuke. Orain hemen beste bat da, azkar alde batera utzita. Oro har, seguruenik ari zaren ez da joan Zeure hash funtzioak idatzi nahi. Benetan da apur bat arte, ez da zientzia. Eta ez dagoela horiek sartzen da asko. Interneten, esan bezala, beteta dago hash funtzio benetan ona, eta internet erabili behar duzu hash funtzio aurkitu da benetan delako Mota besterik ez beharrezkoa Denbora hondakin propioak sortzeko. Simple direnak idatzi ditzakezu probetarako. Baina duzunean benetan joan hasteko datuak osatzerakoan eta gordetzeko hash taula bat bazara sartu ziurrenik nahi joan Sortu funtzio batzuk erabili Zuretzat, Interneten existitzen. Zuk ez ziur egon bada Zure iturriak aipatu beharrik. Ez da, arrazoirik ez plagiarize ezer hemen. Informatikako komunitatea da , balioak betiko hazten eta benetan kode irekia, eta benetan garrantzitsua da Zure iturriak aipatu, jendeak eskuduntza lor daiteke lana ari dira Komunitatearen onurarako egiten. Beraz, beti egon sure-- eta ez bakarrik hash egiteko funtzioak, baina, oro har duzunean kodea erabili kanpoko iturri batetik, Beti aipatu zure iturburu. Eman kreditu pertsonaren egin nahi lan batzuk, beraz, ez duzu behar. OK beraz Dezagun berriro honetan bigarren bat mahai hash. Hau da, non utzi dugun off dugu txertatuko ondoren John eta Paul hash taula batean. Ez da arazo bat ikusten duzu hemen? Baliteke bi ikusiko duzu. Baina batez ere, ez duzu ikusi posible arazo hau? Zer hash dut Ringo bada, eta hura bihurtzen duten prozesatu ondoren Datu hori hash funtzio bidez Ringo halaber hashcode 6 sortzen. Nik dagoeneko lortu datuak hashcode-- array kokapena 6. Beraz, ziurrenik, pixka bat izango da niretzat arazo bat, ezta? Hau deitu dugu talka bat. Eta talka gertatzen denean bi datu zati hash bera zehar ibiltzen Funtzio amore hashcode bera. Ustezko oraindik bi lortu nahi dugu datu zati hash taula sartu, bestela ez genuke Ringo exekutatzen arbitrarioki hash funtzio bidez. Zentzuzkoa lortu nahi dugu, Array horretan sartu Ringo. Nola egiten dugu ordea, bada zuen eta Paul bai etekin hashcode 6? Ez dugu Paul gainidatzi nahi, Paul han ere izan nahi dugu. Beraz, modu bat aurkitu lortu behar dugu hash taula sartu elementu hori oraindik gure azkar kontserbak sartzeak, azkar itxura eman. Eta horri aurre egiteko modu bat da lineala deitzen kraterrak zerbait egin. Metodo hau erabiliz bat badaukagu Talka, bai, zer egiten dugu? Beno, ezin dugu jarri zion array kokapenean 6, edo dena hashcode sortu da, dezagun jarri zion hashcode plus 1ean. Eta hori da, bada utzi beteta en jarri zion hashcode plus 2. Izate hau onerako egin baldin badu Ez zehazki non dagoen uste dugu, eta bilatzen hasi beharko dugu, Agian ez dugu urrunegi joan. Agian ez dugu bilatu n hash taula elementu guztiak. Agian bilatu behar dugu Horietako pare bat. Eta beraz, bidean oraindik dugun joera ari bataz Kasu horretan hurbil vs izateaz 1 n hurbil, beraz, agian lan egingo. Beraz, ikus dezagun nola hau egindako lan baliteke errealitatean. Eta ikus dezagun agian detektatu ahal badugu Hemen gerta zitekeen arazoa. Demagun Bart hash ditugu. Beraz, orain ari gara multzo berri bat exekutatu joan hash funtzioa bidez kateak, eta Bart exekutatu dugu hash bidez funtzioa, hashcode 6 lortuko dugu. Begirada bat hartu dugu, ikusiko dugu 6 da hutsik, beraz, jarri ahal izango dugu Bart dago. Orain Lisa eta Hash dugu halaber hashcode 6 sortzen. Beno, orain dela hau erabiltzen ari gara artesiak lineala hasten 6 dugun metodoa, ikusten dugun 6 betea. Ezin dugu jarri Lisa 6 ere. Beraz, nora goaz? Goazen 7ra en. 7 hutsik, beraz, lan egiten duen. Hargatik jarri Lisa dago. Orain Homer hash dugu eta lortuko dugu 7. OK ondo ezagutzen dugun 7 osoko dagoela orain, beraz, ezin dugu jarri Homer dago. Beraz, goazen 8 en. Eskuragarri dagoen 8? Bai, 8 7 hurbil, beraz, eta bada bilatzen ari gara hasteko aukera izango dugu ez oso urrun joan nahi izan du. Eta, beraz dezagun jarri Homer 8etan. Orain hash ditugu Maggie eta 3 itzultzen, eskerrak besterik jarri Maggie ez gai gara. Guk ez dugu izan inolako egin Sort duten probak. Orain hash ditugu Marge, eta Marge halaber 6 itzultzen. Beno 6 beteta dago, 7 beteta dago, 8 beteta dago, 9, guztiak eskuineko Jainkoari eskerrak, 9 hutsik dago. Jarri ahal izango dut Marge 9etan. Dagoeneko ikusi ahal dugu hasten ari gara Arazo hau non orain gaude dute Gauza mota luzatzeko hasita far euren hash kodeak urrun. Eta 1 theta dela, batez besteko hori etengabeko denbora izatearen kasuan, more-- pixka bat lortzeko hasi apur bat gehiago joera hasita n theta bidean. Ari dela galtzen hasita gaude hash taulak abantaila. Arazo hau ikusi besterik ez dugu clustering izeneko zerbait da. Eta zer da benetan txarra clustering da zuk behin orain Bi elementu hori albo dira by dute alde egiten du, are gehiago egongo da, bikoitza egin behar duzu aukera, hori gertatzen ari zarela Talka beste bat izan kluster horrekin, eta kluster egingo banan hazten. Eta gero eta gehiago hazten mantentzeko duzu Zure talka bat izateko arriskua. Eta, azkenean, ez da bezain txarra ez bezala Datuak guztiak ordenatzeko. Beste arazoa guk da oraindik, eta orain arte, puntu honetan, besterik ez dugu izan da sort hash taula bat zer den ulertzeko, dugu oraindik 10 kateak gela bakarra izan. Hash jarraitu nahi badugu Springfield herritarrek, Horietako 10 bakarrik gaitezke hor. Eta saiatu gara eta 11an edo 12an gehitzeko, ez dugu leku bat jartzea dute. Besterik ezin izango spinning dugu inguruan zirkuluak leku hutsik aurkitu nahian, eta, agian get itsasten dugu begizta infinitua. Beraz, ideia erabaki moduko honetan Zerbait izeneko kateatzea. Eta hau da, non ari gara ekartzea joan zerrendak lotutako argazki sartu atzera. Ordez zer bada besterik gordetzeko datu bera array, array elementu guztietan Could eutsi datu zati bat baino gehiago? Beno, ez du zentzurik, ezta? Badakigu array soilik array baten elementu bakoitzaren hold-- Pieza bat egon daiteke Datu mota horretako datuen. Baina zer gertatzen da datu-mota hori lotutako zerrenda bat da, ezta? Beraz, zer da bada array elementu izan zen lotuta zerrenda burua erakuslea? Eta gero, ezin dugu eraiki lotutako zerrendak horiek eta hazten horiek arbitrarioki, delako lotuta zerrendak baimendu gurekin hazten eta txikitu askoz gehiago malgutasunez array bat baino ez. Beraz, orain zer erabili badugu, honek onura dugu, ezta? Kate horiek hazten hasten dugu array kokaleku horietan egindako. Orain amaigabe bat doi dezakegu datu zenbatekoa, edo ez da infinitua, kopuru arbitrario bat datuak, gure hash taula sartu inoiz sartu exekutatzen gabe Talka arazoa. Ere kendu dugu hau eginez clustering. Eta ondo ezagutzen dugun noiz sartu dugu Lotuta zerrenda, gogoratzen baduzu Gure zerrendak lotuta buruzko bideo-tik, banaka lotutako zerrendak eta bi aldiz lotuta zerrendak, denbora etengabeko eragiketa bat da. Ari gara aurrealdean gehituz. Eta begirada bat ireki, ondo jakin nahi dugu itxura eman lotuta zerrenda batean arazo bat izan daiteke, ezta? Bidez bilatu behar dugu hasieratik amaierara da. Ez da, ausazko ez lotuta zerrenda batean sartzeko aukera. Baina horren ordez, bada bat izatearen lotuta Zerrenda non bilatu a n O izango litzateke, orain dugu 10 lotuta zerrendak, edo 1.000 lotuta zerrendak, Orain bat, O n 10 arabera banatzen da, edo n O 1.000 arabera banatuta. Eta hitz egiten genuen bitartean teorikoki konplexutasuna buruz konstanteak iezaiozu dugu, erreala Mundu gauza horiek benetan axola, ezta? Benetan dugu nabarituko Hori gertatzen dela 10 aldiz azkarragoa, edo 1.000 aldiz azkarrago, Oraindik inork luze banatzeko dugulako 1.000 kateak txikiagoa zehar katean. Eta beraz, aldi bakoitzean bilatu ahal dugun kateak horietakoa bidez 999 kateak ez dugu axola ez ikusi buruz, eta besterik ez bilatu bat dela. Zein batez beste da 1.000 aldiz laburragoa izan. Eta, beraz, oraindik ez gara Sort bataz Kasu honetan doazen etengabeko denbora izatea, baina aprobetxatuz dugun bakarra delako Etengabeko faktore handi batzuk zatituz. Ikus nola liteke dezagun Egia esan, nahiz eta itxura. Beraz, hau izan zen taula hash izan genuen hash taula bat deklaratu dugu aurretik 10 kateak gordetzeko gai izan zen. Ez dugu hori gehiago egin behar. Dagoeneko badakigu Metodo horren mugak. Orain gure hash taula da hori izango da 10 nodo, erakusle bat array zerrendak lotuta buruak. Eta oraintxe nulua da. Bakoitzak 10 erakusleak horietako bat da nulua. Ez dago ezer gure in Hash taula oraintxe. Orain dezagun hasteko batzuk jarri hash taula batean gauzak. Eta ikus dezagun metodo hau nola da guri mesede pixka bat doa. Let hash en orain Joey. Egingo dugu Joey kate bidez exekutatu egingo hash funtzio bat eta gu itzuli 6. Beno, zer egingo dugu orain? Beno, orain zerrendak lotutako lan egitea, ez gara hilarak lanean. Eta lanean ari gara zerrendak lotuta dugu Badakizu dinamikoki hasi behar dugu espazio eta eraikin kateak esleitzean. Hori da Ordena how-- horiek dira muina lotutako zerrenda bat eraikitzeko elementu. Hargatik dinamikoki esleitu espazioa Joey egiteko, eta, ondoren, dezagun gehitu zion kateari. Beraz, orain zer egin dugu begiratu. When Joey hash ditugu hashcode 6 lortu dugu. Orain array kokapena 6 erakuslea lotutako zerrenda baten buru puntu, eta oraintxe bakarrik da lotuta zerrenda elementua. Eta hori nodoarentzat Zerrenda lotuta Joey da. Beraz Joey begiratu behar badugu geroago, hash dugu besterik Joey berriro, lortuko dugu 6 berriro gure duelako hash funtzioa determinista da. Eta orduan hasten buru izaten dugu lotuta zerrendaren adierazi array kokapena ek 6, eta batetik bestera joateko aukera izango dugu Hori Joey bilatzen saiatzen zeharkatuz. Eta guk eraikiko balitz, gure Hash taula eraginkorrean, eta gure hash funtzioa eraginkortasunez Datu ondo banatzeko, batez beste horietako bakoitzean lotuta array kokapena guztietan zerrendak 1/10 izango bada tamainaren dugu besterik handi bakar bat bezala izan da lotuta bertan dena batera zerrenda. Lotuta dagoela handi banatu badiogu 10 lotuta zerrendak zeharkatuz zerrenda Zerrenda bakoitzak 1/10 tamaina izango da. Eta horrela, 10 aldiz azkarrago bilatu bidez. Beraz Berriro egin dezagun. Let hash en orain Ross. Eta demagun Ross, noiz egiten dugun hash-kodea itzultzen garen 2 da. Beno, orain dinamikoki esleitu a dugu nodo berria, Ross jarri dugu nodo horretan, eta orain esaten dugu array kokapena 2, ordez null seinalatuz, a lotuta buru seinalatzen Zerrenda zeinen nodo bakarra Ross da. Eta denbora gehiago bat hau egin ahal izango dugu, ez dugu Rachel hash dezakegu eta hashcode 4. Nodo berria malloc, jarri Rachel hasi nodoa, eta array kokapena batek esaten 4 orain buruan seinalatzen lotutako zerrenda bat zeinen elementu bakarra gertatzen Rachel izan. Ados, baina bada zer gertatzen den Talka izan dugu? Ikus dezagun talkak nola kudeatu dugu utzi aparteko kateatzea metodoa erabiliz. Dezagun hash Phoebe. Hashcode 6 lortuko dugu. Gure aurreko Adibidez besterik ginen Array en kateak gordetzeko. Hau arazo bat izan zen. Guk ez dugu nahi gainean idazteko nahi Joey, eta dagoeneko dugu Ikusten duten clustering batzuk eskuratu ahal izango dugu arazoak saiatzen bagara eta urrats bidez eta zunda. Baina ez dugu zer bada mota besterik hau tratatzeko modu berean, ezta? Besterik ez da elementu bat gehitzen bezalakoa da lotutako zerrenda baten buru izateko. Let Phoebe dagoen espazio besterik malloc. Esan dugu Phoebe hurrengo erakuslea puntu lotuta zerrendaren burua zaharrari, eta ondoren, 6 puntu Zerrenda lotuta buru berria. Eta orain, begira, aldatu dugu Phoebe ere. Orain dugu bi gorde ahal izateko hashcode 6 elementu, eta ez dugu inolako arazorik izan. Hori nahiko askoz guztiak ez kateatzea da. Eta kateatzea da betiko hori da metodoaren gehien baduzu eraginkorra izango da datuak gordetzeko duzu hash taula batean. Baina konbinazio honetan array eta zerrendak lotutako elkarrekin hash taula bat osatzeko benetan nabarmen gaitasuna hobetzen datu kantitate handiak gordetzeko, eta Oso azkar eta modu eraginkorrean bilatu Datu hori bidez. Ez da oraindik bat gehiago Datuen egitura daude Hori izan liteke, nahiz eta pixka bat izan bermatzean hobeto gure txertatzeko, ezabatzeko, eta itxura eman aldiz are azkarrago. Eta hori ikusiko dugu saiatzen bideo batetan. Naiz Doug Lloyd, hau CS50 da.