[Speel van musiek] DOUG LLOYD: By nou is jy weet 'n baie oor skikkings, en jy weet 'n baie oor geskakelde lyste. En ons het bespreek die voor- en nadele, ons het bespreek wat gekoppel lyste kan groter en kleiner te kry, maar hulle neem meer grootte. Skikkings is baie meer eenvoudig om gebruik, maar hulle is beperkende in soveel as ons die grootte van stel die skikking aan die begin En dan is ons vas met dit. 

Maar dit is, ons het pretty much uitgeput van al ons onderwerpe oor geskakelde lyste en skikkings. Of het ons? Miskien kan ons iets doen selfs meer kreatief. En dat die soort van leen die idee van 'n hash tafel. 

So in 'n gemors tafel gaan ons probeer kombineer 'n verskeidenheid met 'n geskakelde lys. Ons gaan die voordele te neem van die skikking, soos ewetoeganklike, om te gaan net na array staat element 4 of skikking element 8 sonder om oor Itereer. Dit is redelik vinnig, reg? 

Maar ons wil ook ons ​​data het struktuur in staat wees om te groei en krimp. Ons hoef nie, ons doen nie wil beperk. En ons wil in staat wees om by te voeg en te verwyder dinge baie maklik, wat as jy onthou, is baie kompleks met 'n skikking. En ons kan dit noem nuwe ding wat 'n hash tafel. 

En indien dit korrek geïmplementeer word, ons soort van die neem van die voordele van beide data strukture wat jy reeds gesien het, skikkings en geskakelde lyste. Invoeging kan begin neig na theta van 1. Theta ons het nie regtig bespreek, maar theta is net die gemiddelde geval, wat eintlik gaan gebeur nie. Jy is nie altyd gaan het die ergste geval scenario, en jy nie altyd gaan hê die beste scenario, so wat is die gemiddelde scenario? 

Wel 'n gemiddelde invoeging in 'n hash tafel kan begin om naby aan konstante tyd. En skrap kan kry sluit aan konstante tyd. En lookup kan kry sluit aan konstante tyd. That's-- ons nie 'n data het struktuur nog wat kan dit doen, en so dit alreeds klink soos 'n mooi groot ding. Ons het regtig versag die nadele van elk op sy eie. 

Om hierdie prestasie te kry gradeer al is, ons moet dink hoe ons by te voeg data in die struktuur. Spesifiek wil ons die data self om ons te vertel waar dit moet gaan in die struktuur. En as ons dan nodig om te sien of dit is in die struktuur, indien ons dit nodig om dit te vind, ons wil om te kyk na die data weer en in staat wees om effektief, die gebruik van die data, lukraak toegang nie. Net deur te kyk na die data wat ons moet hê 'n idee van waar ons presies is gaan om dit te vind in die hash tafel. 

Nou is die nadeel van 'n hash tabel is dat hulle is regtig baie sleg by die bestel of sorteer data. En in die feit, as jy begin om dit te gebruik om te bestel of soort data verloor jy al die voordele wat jy voorheen het in terme van inplanting en skrap. Die tyd raak nader aan theta van N, en ons het basies agteruitgang in 'n geskakelde lys. En so het ons net wil hash gebruik tafels as ons nie omgee of data is gesorteer. Vir die konteks waarin jy sal gebruik om hulle in CS50 het jy waarskynlik nie omgee dat die data is gesorteer. 

So 'n gemors tafel is 'n kombinasie twee afsonderlike stukke waarmee ons bekend is. Die eerste is 'n funksie, wat ons gewoonlik noem 'n hash funksie. En dat hash funksie gaan terug sommige nie-negatiewe heelgetal wat ons gewoonlik noem 'n hashcode, OK? Die tweede stuk is 'n skikking, wat kan stoor data van die tipe wat ons wil plaas in die data struktuur. Ons sal te hou oor die geskakelde lys element vir nou en net begin met die basiese beginsels van 'n hash tabel om jou kop te kry om dit en dan sal ons dalk blaas jou gedagtes 'n bietjie wanneer ons kombineer skikkings en skakel lyste saam. 

Die basiese idee al is ons 'n paar data te neem. Ons loop dat die data deur middel van die hash funksie. En so het die data verwerk en dit spoeg 'n aantal, OK? En dan met dat die getal ons het net die data te stoor ons wil slaan in die opgestel by die plek. So byvoorbeeld het ons miskien hierdie hash tafel snare. Dit het 10 elemente in dit, so kan ons 10 snare inpas nie. 

Kom ons sê ons wil hash John. So John as die data wat ons wil voeg in hierdie hash tafel iewers. Waar kom ons sit dit? Wel tipies met 'n array so ver moontlik ons sou dit in verskeidenheid ligging 0. Maar nou het ons hierdie nuwe hash funksie. 

En laat ons sê dat ons hardloop John deur middel van hierdie hash funksie en dit is spoeg 4. Wel, dit is waar ons gaan wil John sit. Ons wil John opgestel plek sit 4, want as ons hash John again-- Kom ons sê ons later wil soek en kyk As John bestaan ​​in hierdie hash table-- al wat ons moet doen is loop dit deur dieselfde hash funksie, kry die nommer 4 uit en in staat wees om John te vind onmiddellik in ons data struktuur. Dit is redelik goed. 

Kom ons sê dat ons dit nou te doen weer, wil ons hash Paul. Ons wil Paul voeg in hierdie hash tafel. Kom ons sê dat ons hierdie keer hardloop Paulus deur die hash funksie, die hashcode wat gegenereer is 6. Wel nou kan ons Paulus sit in die skikking plek 6. En as ons nodig het om te kyk of Paul is in hierdie hash tafel, al wat ons nodig het om te doen, is hardloop Paul deur die hash funksie weer en ons gaan weer uit te kry 6. 

En dan ons net kyk op array plek 6. Paulus is daar? As dit so is, is hy in die hash tafel. Is Paulus nie daar? Hy is nie in die hash tafel. Dit is redelik eenvoudig. 

Nou hoe kan jy 'n hash funksie definieer? Wel daar is regtig geen beperking op die aantal moontlike hash funksies. In werklikheid is daar is 'n aantal van die baie, regtig 'n goeie kinders op die internet. Daar is 'n aantal van die baie, regtig slegte mense op die internet. Dit is ook redelik maklik om 'n slegte een te skryf. 

So, wat maak 'n goeie hash funksie, reg? Wel, 'n goeie hash funksie moet gebruik slegs die data wat hashed, en al die data wat hashed. Sodat ons nie wil anything-- gebruik ons nie iets inkorporeer anders as die data. En ons wil al die data te gebruik. Ons wil nie net gebruik 'n stuk dit, ons wil almal dit te gebruik. A hash funksie moet ook deterministies wees. Wat beteken dit? Wel dit beteken dat elke keer as ons slaag die presiese dieselfde stuk data in die hash funksie het ons altyd kry dieselfde hashcode uit. As ek slaag John in die hash funksie ek uit 4. Ek moet in staat wees om dit te doen 10000 keer en ek sal altyd 4. Sodat daar geen ewekansige getalle effektief betrokke kan wees in ons hash tables-- in ons hash funksies. 

A hash funksie moet ook eenvormig versprei data. As elke keer as jy data loop deur die hash funksie kry jy die hashcode 0, dit is waarskynlik nie so groot nie, reg? Jy wil waarskynlik groot 'n verskeidenheid van hash kodes. Ook dinge kan versprei dwarsdeur die tafel. En ook dit sou 'n groot as werklik soortgelyke data, soos John en Jonathan, Miskien is versprei om te weeg verskillende plekke in die hash tafel. Dit sou 'n mooi voordeel wees. 

Hier is 'n voorbeeld van 'n hash funksie. Ek het hierdie een vroeër. Dit is nie 'n besonder goeie hash funksie vir redes wat nie regtig dra gaan in nou. Maar jy sien wat gaan hier aan? Dit lyk asof ons 'n veranderlike verklaar genoem som en die opstel van dit gelyk aan 0. En dan glo ek om iets te doen so lank as strstr [j] nie gelyk is om agteroorskuinsstreep 0. Wat kan ek daar? 

Dit is basies net 'n ander manier van die implementering van [? strl?] en die opsporing Wanneer jy aan die einde van die tou. So ek het nie eintlik om bereken die lengte van die string, Ek is net die gebruik toe ek die backslash 0 karakter Ek weet Ek het die einde van die string bereik. En dan gaan ek hou iterating deur daardie string, toevoeging van strstr [j] op te som, en dan aan die einde van die dag gaan som mod terugkeer HASH_MAX. 

Basies al hierdie hash funksie doen, is die toevoeging van al die ASCII waardes van my string, en dan is dit terugkeer paar hashcode Gemodificeerde deur HASH_MAX. Dit is waarskynlik die grootte van my skikking, reg? Ek wil nie te wees om hash kodes as my skikking is van die grootte 10, Ek wil nie te wees om uit hash kodes 11, 12, 13, Ek kan nie dinge in die plekke van die skikking, dat onwettige sou wees. Ek sal ly 'n segmentering skuld. 

Nou hier is nog 'n vinnige eenkant. Algemeen is jy waarskynlik nie van plan om wil jou eie hash funksies te skryf. Dit is eintlik 'n bietjie van 'n kuns, nie 'n wetenskap. En daar is 'n baie wat gaan in hulle. Die internet, soos ek gesê het, is vol van baie goeie hash funksies, en jy moet die internet te gebruik vind hash funksies, want dit is regtig net soort van 'n onnodige vermorsing van tyd om jou eie te skep. 

Jy kan eenvoudiges skryf vir die toets doeleindes. Maar wanneer jy eintlik gaan begin hashing data en om dit te stoor in 'n hash tafel jy waarskynlik gaan om te wil om 'n funksie wat gegenereer gebruik vir jou, wat bestaan ​​op die internet. As jy net seker om jou bronne te noem. Daar is geen rede om plagiaat pleeg hier nie. 

Die rekenaarwetenskap gemeenskap is beslis groei, en regtig waardes open source, en dit is werklik belangrik om jou bronne te noem, sodat mense kan toeskrywing te kry vir die werk wat hulle is doen tot voordeel van die gemeenskap. So altyd sure-- wees en nie net vir hash funksies, maar oor die algemeen as jy gebruik van 'n buite-kode bron altyd noem jou bron. Gee krediet aan die persoon wat dit gedoen sommige van die werk, sodat jy nie hoef te. 

OK so laat heroorweeg hierdie hash tafel vir 'n tweede. Dit is waar ons opgehou af na ons plaas John en Paul in hierdie hash tafel. Het jy 'n probleem hier te sien? Jy kan sien twee. Maar in die besonder, het jy sien dit moontlike probleem? 

Wat gebeur as ek hash Ringo en dit blyk dat na die verwerking dat die data deur die hash funksie Ringo gegenereer ook die hashcode 6. Ek het al 'data op hashcode-- verskeidenheid ligging 6. So dit is waarskynlik gaan om 'n bietjie te wees van 'n probleem vir my nou, reg? 

Ons noem dit 'n botsing. En die botsing vind plaas wanneer twee stukkies data loop deur dieselfde hash funksie lewer dieselfde hashcode. Vermoedelik het ons nog wil beide kry stukke data in die hash tafel, anders sou ons nie hardloop Ringo arbitrêr deur die hash funksie. Ons wil vermoedelik te kry Ringo in daardie skikking. 

Hoe doen ons dit al is, as hy en Paul beide opbrengs hashcode 6? Ons wil nie oorskryf Paul, ons wil Paulus ook daar wees. So moet ons 'n manier te vind om te kry elemente in die hash tafel wat steeds bewaar ons vinnige inplanting en vinnige blik op. En een manier om dit te hanteer, is om iets genoem lineêre indringende doen. 

Die gebruik van hierdie metode as ons 'n botsing, wel, wat doen ons? Wel, ons kan hom nie in die rigting plek 6, of wat ook al hashcode was gegenereer, laat hom te hashcode plus 1. En as dit is vol laat se het hom in hashcode plus 2. Die voordeel van hierdie wese as hy nie presies waar ons dink hy is, en ons het om te begin soek, Miskien het ons nie te ver gaan nie. Miskien het ons nie hoef te soek alle n elemente van die hash tafel. Miskien moet ons soek 'n paar van hulle. 

En so is ons nog steeds neig na dat die gemiddelde geval wat naby aan 1 vs naby aan n, so miskien is dit sal werk. So laat ons sien hoe dit kan uit te werk in die werklikheid. En laat ons sien of miskien kan ons spoor die probleem wat hier mag voorkom. 

Kom ons sê ons hash Bart. So nou gaan ons 'n nuwe stel hardloop snare deur die hash funksie, en ons hardloop Bart deur die hash funksie, kry ons hashcode 6. Ons neem 'n blik, sien ons 6 is leeg, sodat ons kan Bart daar te vestig. 

Nou hash ons Lisa en dat genereer ook hashcode 6. Wel, nou dat ons die gebruik van hierdie lineêre indringende metode begin ons op 6, ons sien dat 6 is vol. Ons kan nie 'Lisa in 6. So waar gaan ons heen? Kom ons gaan na 7. 7 se leë, so wat werk. Kom ons stel Lisa daar. 

Nou hash ons Homer en ons kry 7. OK goed ons weet dat 7 se volle nou, so ons kan nie daar sit Homer. So laat ons gaan na 8. 8 beskikbaar? Ja, en 8 se naby aan 7, so as ons het om te begin soek ons nie van plan om te ver gaan. En so laat sit Homer op 8. 

Nou hash ons Maggie en terug 3, dankie tog ons is in staat om net sit Maggie daar. Ons het nie nodig om enige te doen soort van indringende vir daardie. Nou hash ons Marge, en Marge terug ook 6. 

Wel 6 is vol, 7 is vol, 8 is vol, 9, alles reg dank God, 9 is leeg. Ek kan Marge sit op 9. Al wat ons kan sien dat ons begin om hierdie probleem waar ons nou is het begin om dinge soort rek van ver weg van hul hash kodes. En dat theta van 1, dat die gemiddelde geval van wat konstant tyd begin om 'n bietjie te kry more-- begin om 'n bietjie meer geneig teenoor theta van n. Ons begin om te verloor wat voordeel van hash tabelle. 

Hierdie probleem dat ons nou net gesien het is iets genoem clustering. En wat is regtig sleg oor groepering is dat wanneer jy nou het twee elemente wat kant is deur kant maak dit selfs meer waarskynlik, jy dubbel die het kans dat jy gaan na 'n ander botsing het met daardie cluster, en die cluster sal groei vir een. En jy sal aanhou groei en groei jou waarskynlikheid van 'n botsing. En uiteindelik is dit net so erg as nie sorteer die data op alle. 

Die ander probleem is egter ons steeds, en so ver tot op hierdie punt, ons het net soort van nie verstaan ​​wat 'n hash tafel is, ons nog net ruimte vir 10 snare. As ons wil voortgaan om hash die burgers van Springfield, kan ons net kry 10 van hulle daar. En as ons probeer en voeg 'n 11de of 12de, Ons het nie 'n plek om hulle te sit. Ons kon net spin rond in sirkels probeer om 'n leë plek te vind, en ons dalk vashaak in 'n oneindige lus. 

So hierdie soort van leen aan die idee van iets genoem chaining. En dit is waar ons gaan bring geskakelde lyste terug in die prentjie. Wat as in plaas van die stoor net die data self in die skikking, elke element van die skikking kon hou verskeie stukke data? Goed dat nie sin maak nie, reg? Ons weet dat 'n skikking kan net hold-- elke element van 'n skikking kan slegs een stuk van data van daardie tipe data. 

Maar wat as die tipe data is 'n geskakelde lys, reg? So, wat as elke element van die skikking was 'n verwysing na die hoof van 'n geskakelde lys? En dan kan ons bou diegene geskakelde lyste en groei hulle arbitrêr, omdat geskakelde lyste toelaat ons om te groei en krimp 'n baie meer buigsaam as 'n skikking nie. So, wat as ons nou gebruik, Ons gebruik dit reg? Ons begin om die kettings te groei Uit hierdie verskeidenheid plekke. 

Nou kan ons pas 'n oneindige bedrag van data, of nie oneindig, 'n arbitrêre bedrag van data, in ons hash tafel sonder om ooit loop in die probleem van 'n botsing. Ons het ook uitgeskakel groepering deur dit te doen. En goed ons weet dat wanneer ons voeg in 'n geskakelde lys, as jy onthou van ons video op geskakelde lyste, enkel gekoppel lyste en dubbel geskakelde lyste, dit is 'n konstante werking. Ons is net die toevoeging aan die voorkant. 

En kyk op, en ons weet wat lyk in 'n geskakelde lys kan 'n probleem wees, reg? Ons het om te soek deur dit van begin tot einde. Daar is geen ewekansige toegang in 'n geskakelde lys. Maar as in plaas van om 'n verband lys waar 'n lookup O van n sal wees, ons het nou 10 geskakelde lyste, of 1000 geskakelde lyste, nou is dit O van n gedeel deur 10, of O van n gedeel deur 1000. 

En terwyl ons praat teoreties oor kompleksiteit ons ignoreer konstantes, in die werklike wêreld hierdie dinge eintlik saak, reg? Ons het eintlik sal sien dat dit gebeur 10 keer vinniger te hardloop, of 1000 keer vinniger, omdat ons die verspreiding van 'n lang ketting oor 1000 kleiner kettings. En so elke keer wanneer ons moet soek deur een van daardie kettings wat ons kan ignoreer die 999 kettings ons nie omgee oor, en net soek daardie een. 

Wat is gemiddeld tot wees 1000 keer korter. En so het ons nog soort van neig na dié gemiddelde geval om konstante tyd, maar net omdat ons gebruik te maak verdeel deur sommige groot konstante faktor. Kom ons kyk hoe dit kan eintlik lyk al is. So was dit die hash tafel moes ons voordat ons verklaar hash tafel wat was in staat om van die stoor 10 snare. Ons is nie van plan om dit te doen nie. Ons weet reeds die beperkinge van die metode. Nou ons hash tafel gaan wees 'n verskeidenheid van 10 knope, wysers aan hoofde van geskakelde lyste. 

En nou is dit null. Elkeen van die 10 wenke is van nul. Daar is niks in ons hash tafel nou. 

Nou laat ons begin om 'n paar te sit dinge in hierdie hash tafel. En laat ons sien hoe hierdie metode is gaan baat ons 'n bietjie. Kom nou hash Joey. Ons sal die string Joey deur loop 'n hash funksie en ons terugkeer 6. Wel, wat doen ons nou? 

Wel, nou werk met geskakelde lyste, ons is nie besig met skikkings. En toe ons werk met geskakelde lyste ons weet ons nodig het om te begin dinamies toekenning ruimte en die bou van kettings. Dit is soort van how-- dit is die kern elemente van die bou van 'n geskakelde lys. So laat dinamies toeken ruimte vir Joey, en dan laat hom toe te voeg tot die ketting. 

So nou kyk wat ons gedoen het. Wanneer ons hash Joey ons het die hashcode 6. Nou is die wyser op array plek 6 dui op die hoof van 'n geskakelde lys, en nou is dit die enigste element van 'n geskakelde lys. En die knoop in daardie gekoppel lys is Joey. 

So as ons nodig het om te kyk Joey later, het ons net weer hash Joey, ons kry 6 weer, want ons hash funksie is deterministiese. En dan het ons begin by die hoof van die geskakelde lys wys om deur array plek 6, en ons kan Itereer oor wat probeer om Joey te vind. En as ons bou aan ons hash tafel effektief, en ons hash funksie effektief om data goed versprei, gemiddeld elk van daardie gekoppel lyste by elke array plek sal wees 10/01 van die grootte van as ons moes net dit as 'n enkele groot geskakelde lys met alles daarin. 

As ons versprei dat groot gekoppel lys regoor 10 geskakelde lyste elke lys sal wees 10/01 die grootte. En dus 10 keer vinniger om te soek deur. So laat dit weer te doen. Kom nou hash Ross. 

En kom ons sê Ross, wanneer ons dit doen die hash kode wat ons terug te kry is 2. Wel nou is ons dinamiese ken 'n nuwe node, ons sit Ross in daardie knoop, en ons nou sê array plek 2, in plaas van om te wys nul dui op die hoof van 'n gekoppelde lys wie se enigste node is Ross. En ons kan hierdie een meer tyd te doen, het ons kan hash Rachel en kry hashcode 4. malloc 'n nuwe node, sit Rachel in die node, en sê 'n verskeidenheid plek 4 wys nou aan die hoof van 'n geskakelde lys wie enigste element gebeur met Rachel wees. 

OK, maar wat gebeur as ons het 'n botsing? Kom ons kyk hoe ons omgaan botsings die gebruik van die afsonderlike aaneenskakeling metode. Kom ons hash Phoebe. Ons kry die hashcode 6. In ons vorige voorbeeld het ons net stoor die snare in die skikking. Dit was 'n probleem. 

Ons wil nie afranselen Joey, en ons het reeds gesien dat ons 'n paar groepering kan kry probleme as ons probeer en stap deur en ondersoek. Maar wat as ons net soort van behandel dit op dieselfde manier, reg? Dit is net soos voeg 'n element aan die hoof van 'n geskakelde lys. Laat ons net malloc ruimte vir Phoebe. 

Ons sal sê Phoebe se volgende wyser punte om die ou hoof van die geskakelde lys, en dan 6 net verwys na die nuwe hoof van die geskakelde lys. En kyk nou, ons het Phoebe verander in. Ons kan nou stoor twee elemente met hashcode 6, en ons weet nie enige probleme. 

Dit is pretty much al daar is om te aaneenskakeling. En aaneenskakeling is beslis die metode wat gaan die mees doeltreffende vir jou as om te wees jy data stoor in 'n hash tafel. Maar hierdie kombinasie van skikkings en geskakelde lyste saam 'n hash tafel regtig vorm dramaties verbeter jou vermoë om groot hoeveelhede data stoor, en baie vinnig en doeltreffend te soek deur daardie data. 

Daar is nog een data struktuur daar buite wat dalk selfs 'n bietjie wees beter in terme van die waarborg van dat ons inplanting, skrap, en opkyk tye is selfs vinniger. En ons sal sien dat in 'n video op drieë gedruk. Ek is Doug Lloyd, dit is CS50.