[Musiikkia] DOUG Lloyd: mennessä sinun tietää paljon paneelit, ja tiedät paljon linkitettyjen listojen. Ja olemme keskustella hyvät ja huonot puolensa, olemme keskustelivat että liittyvät luettelot voi saada isompi ja pienempi, mutta ne vievät enemmän koko. Taulukot ovat paljon yksinkertaisempaa käyttää, mutta ne rajoittavat niin paljon koska meidän on asettaa koko array aivan alussa ja sitten me pääse siitä eroon. 

Mutta se, olemme melko paljon käyttänyt kaikki meidän aiheista noin liittyvät luettelot ja taulukot. Tai me? Ehkä voimme tehdä jotain Luovempaan. Ja tällaista se lainaa ajatus hajautustaulun. 

Joten hajautustaulun aiomme kokeilla yhdistää array linkitetty lista. Aiomme ottaa edut array, kuten random access, että voimme vain mennä array elementti 4 tai ryhmän elementin 8 ilman kerrata poikki. Se on melko nopeasti, eikö? 

Mutta haluamme myös olla tietomme rakenne voi kasvaa ja kutistua. Emme tarvitse, emme haluavat rajoittaa. Ja haluamme pystyä lisätä ja poistaa asioita hyvin helposti, joka Jos muistatte, on erittäin monimutkainen jono. Voimme kutsua tätä uusi asia hajautustaulua. 

Ja jos ne toteutetaan oikein, olemme tavallaan ottaen edut sekä data- rakenteet olet jo nähnyt, taulukot ja linkitettyjen listojen. Asennus voi alkaa pyrkivän kohti thetalla 1. Theta emme ole oikeastaan ​​keskusteltu, mutta theta on vain keskimääräisestä tapauksesta, mitä todella tapahtuu. Et aina aio on pahimmassa tapauksessa, ja et aina olemaan Parhaassa tapauksessa niin mitä keskimääräinen skenaario? 

No keskimääräinen lisäys osaksi hash table voi alkaa päästä lähelle vakio aikaa. Ja poisto voi saada lähes vakio aikaa. Ja lookup voi saada lähes vakio aikaa. That's-- meillä ei ole tietoa rakenne vielä, että voi tehdä sitä, ja niin tämä jo kuulostaa kuten melko suuri asia. Olemme todella lieventää haittoja kunkin omasta. 

Jotta saat tämän suorituskyvyn päivittää vaikka me on harkittava uudelleen, kuinka lisäämme tietojen rakenteeseen. Erityisesti haluamme tiedot itse kertoa meille jos se pitäisi mennä rakenteessa. Ja jos me sitten täytyy nähdä, jos se on rakenne, jos meidän on löydettävä se, haluamme tarkastella tietoja uudelleen ja pystyä tehokkaasti, käyttäen tietoja, satunnaisesti käyttää sitä. Vain tarkastelemalla tietojen pitäisi olla siitä, missä tarkalleen olemme menossa löytää sen tiiviste. 

Nyt haittapuoli hash pöytä on, että he todella melko huono tilaus tai lajittelu tietoja. Ja itse asiassa, jos käynnistät käyttää niitä tilata tai lajitella tiedot menetät kaikki etuja aiemmin oli kannalta paikoilleen ja poisto. Aika lähenee theta n, ja olemme periaatteessa taantunut osaksi linkitetty lista. Ja niin me vain haluamme käyttää hash taulukot jos emme välitä onko tiedot lajitellaan. Sillä asiayhteys, jossa voit käyttää niitä CS50 luultavasti eivät välitä että tiedot on järjestetty. 

Niin hash table on yhdistelmä kaksi erillistä kappaletta jonka kanssa olemme tuttuja. Ensimmäinen on toiminto, joka me yleensä kutsumme hajautusfunktio. Ja että tiivistefunktiota aikoo palata joitakin ei-negatiivinen kokonaisluku, joka me yleensä kutsumme hashcode, OK? Toinen kappale on matriisi, joka on joka pystyy tallentamaan dataa tyypin me haluavat sijoittaa osaksi tietorakennetta. Me pitää pois linkitetty lista osa nyt ja juuri aloittaa perusasiat tiiviste saada pään ympärille, ja sitten me ehkä puhalla mielesi hieman kun me yhdistää taulukot ja linkit yhteen. 

Perusajatuksena vaikka on otamme joitakin tietoja. Otamme että dataa tiivistefunktio. Ja niin tietoja käsitellään ja se sylkee numero, OK? Ja sitten, että määrä me vain tallentaa tiedot Haluamme tallentaa array kyseisessä paikassa. Niinpä esimerkiksi meillä on ehkä tämä tiiviste merkkijonojen. Se sai 10 elementtejä se, niin me mahtuu 10 jousille se. 

Sanotaan haluamme hash John. Niin Johanneksen tiedot haluamme lisätä tähän tiiviste jonnekin. Mistä me laittaa sen? Hyvin tyypillisesti array toistaiseksi emme luultavasti asettaisi se array sijainti 0. Mutta nyt meillä on tämä uusi hajautusfunktio. 

Ja sanotaan, että otamme John kautta tiivistefunktio ja se sylkee 4. No siitähän olemme menossa halua laittaa John. Haluamme laittaa John array sijainti 4, koska jos me hash John again-- Sanotaan myöhemmin me haluat etsiä ja nähdä jos John olemassa tässä hash table-- kaikki meidän täytyy tehdä on ajaa se läpi sama tiiviste toiminto, saat numero 4 ulos, ja löytää John välittömästi meidän tietorakenne. Se on aika hyvä. 

Sanotaan nyt tehdä tämän jälleen, haluamme hash Paul. Haluamme lisätä Paul tähän tiiviste. Oletetaan, että tällä kertaa otamme Paul kautta hajautusfunktio, hashcode, joka syntyy on 6. No nyt voimme laittaa Paul jono sijainti 6. Ja jos meidän etsiä onko Paul on tässä tiiviste, kaikki meidän täytyy tehdä on ajaa Paul kautta tiivistefunktio uudelleen ja me aiomme saada 6 ulos. 

Ja sitten me vain katsoa at array Sijainti 6. Onko Paul siellä? Jos näin on, hän on tiiviste. Paavali ei siellä? Hän ei ole tiiviste. Se on melko yksinkertainen. 

Nyt Miten määrittelet hajautusfunktio? No siellä oikeastaan ​​mitään rajaa useita mahdollisia hash toimintoja. Itse asiassa on olemassa useita todella, todella hyviä Internetissä. On useita todella, todella huonoja internetissä. Se on myös melko helppo kirjoittaa huono. 

Joten mitä tekee jopa hyvää tiivistefunktiota, eikö? No hyvä hajautusfunktio pitäisi Käytä vain datan hashed, ja kaikki tiedot on hajauttamat. Joten emme halua käyttää anything-- emme sisällyttää mitään muualla kuin tiedot. Ja haluamme käyttää kaikki tiedot. Emme halua vain käyttää pala sitä, haluamme käyttää kaikki. Hajautusfunktio pitäisi myös deterministinen. Mitä se tarkoittaa? No se tarkoittaa, että joka kerta kun siirtää täsmälleen samoja tietoja osaksi tiivistefunktio aina saada sama hashcode ulos. Jos kuljen John osaksi tiivistefunktio pääsen pois 4. Minun pitäisi pystyä tekemään, että 10000 ajat ja tulen aina saada 4. Joten ei satunnaisia ​​numeroita tehokkaasti voi olla mukana meidän hash tables-- meidän hash toimintoja. 

Hajautusfunktio olisi myös tasaisesti jakaa tietoja. Jos aina käyttää dataa hajautusfunktio saat hashcode 0, se luultavasti ei ole niin suuri, oikea? Et luultavasti halua iso erilaisia ​​hash koodeja. Myös asiat voidaan levittää ulos koko pöydän. Ja myös se olisi hienoa, jos todella samoja tietoja, kuten John ja Jonathan, ehkä oli levittää punnita eri paikoissa tiiviste. Se olisi kiva etu. 

Tässä on esimerkki hajautusfunktiota. Kirjoitin tämän yhden jopa aikaisemmin. Se ei ole erityisen hyvä tiivistefunktio syistä, jotka eivät oikeastaan karhu menee juuri nyt. Mutta näetkö mitä täällä tapahtuu? Tuntuu siltä, ​​olemme julistamisesta muuttuja nimeltään summa ja asettamalla se yhtä suuri kuin 0. Ja sitten ilmeisesti olen tekemässä jotain niin kauan kuin strstr [j] ei ole yhtä suuri kuin on Kenoviiva 0. Mitä teen siellä? 

Tämä on pohjimmiltaan vain toinen tapa toteuttaa [? strl?] ja havaitsemaan milloin olet lopussa merkkijonon. Joten minun ei tarvitse itse laskea merkkijonon pituus, Olen vain käyttää kun osuin kenoviiva 0 merkki Tiedän Olen lopussa merkkijonon. Ja sitten aion pitää iteroimalla läpi merkkijono, lisäämällä strstr [j] Yhteenvetona, ja sitten Päivän päätteeksi palaavansa summa mod HASH_MAX. 

Periaatteessa kaikki tämä hash toiminto tekee on lisätä ylös kaikki ASCII-arvojen minun merkkijono, ja sitten se on palaavat jotkut hashcode modded mukaan HASH_MAX. Se on luultavasti koko minun array, eikö? En halua saada hash koodit jos joukko on koko 10, En halua olla saada out hash koodit 11, 12, 13, en voi laittaa asiat oikeisiin niihin paikkoihin array, että olisi laitonta. Olin kärsivät segmentointi vika. 

Nyt täällä on toinen nopea syrjään. Yleensä olet todennäköisesti aio haluavat kirjoittaa oman hash toimintoja. Se on oikeastaan ​​hieman taidetta, ei tiedettä. Ja siellä on paljon että menee niitä. Internet, kuten sanoin, on täynnä todella hyvä hash toimintoja, ja sinun pitäisi käyttää Internetiä löytää hash toimintoja, koska se on todella juuri sellainen tarpeeton ajanhukkaa luoda oman. 

Voit kirjoittaa yksinkertaisia, testausta varten. Mutta kun itse on menossa aloittaa hajautusta tiedot ja varastointia osaksi hash table olet luultavasti menossa haluavat käyttää joitakin toiminto luotiin sinulle, että on olemassa Internetissä. Jos et vain olla varma mainita käyttämäsi lähteet. Ei ole mitään syytä plagioida mitään täällä. 

Tietojenkäsittelytiede yhteisö on varmasti kasvaa, ja todella arvot avoimen lähdekoodin, ja se on todella tärkeää mainita lähteet niin, että ihmiset voi saada Nimeä varten työstä, jota he tekee koko yhteisön hyväksi. Joten aina sure-- ja ei vain hash toiminnot, mutta yleensä kun käytä koodia ulkopuolisista lähteistä, aina mainita lähde. Antaa tunnustusta henkilölle, joka teki osan työstä, joten sinun ei tarvitse. 

OK joten katsotaanpa uudelleen tämän tiiviste toista. Täällä jätimme pois, kun lisäsimme John ja Paul tähän tiiviste. Näetkö ongelma täällä? Saatat nähdä kaksi. Mutta erityisesti, oletteko katso tämä mahdollinen ongelma? 

Mitä jos hash Ringo, ja se Osoittautuu, että käsittelyn jälkeen että dataa hajautusfunktio Ringo myös tuotti hashcode 6. Olen jo saanut tietoja hashcode-- array Sijainti 6. Joten se luultavasti olemaan hieman ongelma minulle nyt, eikö? 

Kutsumme tätä törmäys. Ja törmäys tapahtuu, kun kaksi datajoukkoja läpi sama tiiviste toiminto saadaan sama hashcode. Oletettavasti haluamme kuitenkin saada molemmat kappaletta datan hash table, muuten emme olisi käynnissä Ringo mielivaltaisesti kautta hajautusfunktio. Me oletettavasti haluavat saada Ringo tuohon array. 

Miten teemme sen kuitenkin, jos hän ja Paul sekä tuotto- hashcode 6? Emme halua korvata Paul, haluamme Paul olla sielläkin. Joten meidän on löydettävä tapa saada elementtejä tiiviste että on säilyttänyt meidän nopeasti paikoilleen ja nopea etsiä. Ja yksi tapa käsitellä sitä on tehdä jotain kutsutaan lineaarinen luotaa. 

Käyttämällä tätä menetelmää, jos meillä törmäys, hyvin, mitä me teemme? No emme voi häntä array sijainti 6, tai mitä tahansa hashcode syntyi, Laitetaan hänet hashcode plus 1. Ja jos se täydellinen Katsotaan pani hänet hashcode plus 2. Hyöty olennon jos hän on ei tarkalleen missä meidän mielestämme hän on, ja meidän on alkaa etsiä, Ehkä meidän ei tarvitse mennä liian pitkälle. Ehkä meidän ei tarvitse etsiä kaikki n elementit hajautustaulun. Ehkä meidän täytyy etsiä pari niistä. 

Ja niin olemme yhä omiaan kohti että keskimääräinen tapaus ovat lähellä 1 vs lähellä n, niin ehkä se täytyy harjoitella. Joten miten tämä voi treenata todellisuudessa. Ja katsotaanpa jos ehkä voimme havaita ongelma, joka voi esiintyä tässä. 

Sanotaan hash Bart. Joten nyt aiomme ajaa uusia merkkijonojen kautta hajautusfunktio, ja otamme Bart läpi hash toiminto, saamme hashcode 6. Me katsomaan, näemme 6 tyhjä, joten voimme laittaa Bart sinne. 

Nyt hash Lisa ja että tuottaa myös hashcode 6. No nyt, että käytämme tätä lineaarinen hyvää menetelmä aloitamme 6, näemme, että 6 on täynnä. Emme voi laittaa Lisa 6. Joten jos me menisimme? Mennään 7. 7: n tyhjä, niin että toimii. Joten laittaa Lisa siellä. 

Nyt hash Homer ja saamme 7. OK hyvin tiedämme, että 7 täyden nyt, joten emme voi laittaa Homer siellä. Joten mennään 8. On 8 käytettävissä? Joo, ja 8: n lähes 7, joten jos meidän täytyy alkaa etsiä olemme aio tarvitse mennä liian pitkälle. Ja niin katsotaanpa laittaa Homer 8. 

Nyt hash Maggie ja palauttaa 3, luojan kiitos pystymme vain laittaa Maggie siellä. Meidän ei tarvitse tehdä mitään tavallaan hyvää siitä. Nyt hash Marge, ja Marge myös palauttaa 6. 

No 6 on täynnä, 7 on täynnä, 8 on täynnä, 9, okei luojan kiitos, 9 on tyhjä. Voin laittaa Marge 9. Jo voimme nähdä, että olemme alkaneet on tämä ongelma, jossa nyt olemme alkaa venyttää asioita laji on kaukana niiden hash koodeja. Ja että theta 1, että keskimääräinen kyseessä on vakio aikaa, alkaa saada hieman more-- alkaa yleensä hieman enemmän kohti thetalla n. Olemme alkaneet menettää että etuna hash taulukoita. 

Tämä ongelma, että me juuri näin on jotain kutsutaan klustereiden. Ja mitä todella pahaa klusterointi on, että kun nyt on kaksi tekijää, jotka ovat rinta puolella se tekee siitä entistä todennäköisemmin, sinulla on kaksinkertainen mahdollisuus, että olet menossa on toinen törmäys kanssa, että klusteri, ja klusterin kasvaa yhdellä. Ja sinun pitää kasvaa ja kasvaa todennäköisyyttä, jolla törmäys. Ja lopulta se on aivan yhtä huono koska ei lajittelu tietoja lainkaan. 

Toinen ongelma kuitenkin on meidän edelleen, ja toistaiseksi tähän asti, Olemme juuri eräänlainen ymmärtää, mitä hajautustaulun on, meillä on edelleen vain on tilaa 10 jousille. Jos haluamme jatkaa hash kansalaiset Springfield, voimme vain saada 10 niistä siellä. Ja jos yritämme lisätä 11. tai 12., meillä ei ole paikka laittaa ne. Voisimme vain pyöriä ympäri piireissä yrittää löytää tyhjässä, ja me ehkä juuttua päättymättömään silmukkaan. 

Joten tällainen se lainaa ajatus jotain kutsutaan ketjuttamalla. Ja tämä on, jos aiomme tuoda liittyvät luettelot takaisin kuvaan. Mitä jos sen sijaan tallentaa vain tiedot itse array, jokainen alkio voisi olla useita paloja tiedot? No se ei ole järkeä, eikö? Tiedämme, että jono voi vain hold-- kukin elementti array voi olla vain yksi pala datan tietojen tyyppi. 

Mutta entä jos se tietotyyppi on linkitetty lista, eikö? Joten mitä jos jokainen alkio oli osoitin johtaja linkitetty lista? Ja sitten voisimme rakentaa ne liittyvät luettelot ja kasvattaa ne mielivaltaisesti, koska linkitettyjen listojen avulla meille mahdollisuuden kasvaa ja kutistua paljon enemmän joustavasti kuin array tekee. Joten mitä jos me nyt käyttää, Hyödynnämme tätä, eikö? Meidän alkaa kasvaa nämä ketjut Näistä array paikoista. 

Nyt mahtuu ääretön datan määrä, tai ääretön, mielivaltainen määrä tiedot, meidän tiiviste ilman koskaan ajautumassa ongelma törmäyksen. Olemme myös poistettava klustereiden tekemällä näin. Ja hyvin me tiedämme, että kun lisäämme osaksi linkitetty lista, jos muistatte meidän video linkitettyjen listojen, yksittäin liittyvät luettelot ja kaksinkertaisesti liittyvät luettelot, se jatkuva aika operaatio. Olemme vain lisäämällä eteen. 

Ja katsoa ylös, hyvin tiedämme jotka näyttävät ylöspäin linkitetty lista voi olla ongelma, eikö? Meidän on etsiä se alusta loppuun. Ei ole satunnainen pääsy linkitetty lista. Mutta jos sen sijaan, että yksi yhdistetty lista jossa lookup olisi O n, meillä on nyt 10 linkitettyjen listojen, tai 1000 linkitettyjen listojen, nyt se on O n jaettuna 10, tai O n jaettuna 1000. 

Ja kun me puhuimme teoreettisesti noin monimutkaisuus emme ota huomioon vakiot, todellisessa maailma nämä asiat todella väliä, oikea? Me itse asiassa huomaavat että näin tapahtuu ajaa 10 kertaa nopeammin, tai 1000 kertaa nopeammin, koska me jakaa yksi pitkä ketju yli 1000 pienempiä ketjuja. Ja niin joka kerta meillä on etsiä kautta yksi näistä ketjuista voimme sivuuttaa 999 ketjut emme välitä noin, ja vain etsiä, että yksi. 

Joka on keskimäärin olla 1000 kertaa lyhyempi. Ja niin me vielä olemme tavallaan omiaan johtamaan tätä keskimääräistä tapauksessa olemisen jatkuva aikaa, mutta vain koska olemme vipuvaikutusta jakamalla valtavia vakiokertoimella. Katsotaanpa, miten tämä voisi todella näyttävät kuitenkin. Joten tämä oli tiiviste meillä oli ennen kuin julisti hajautustaulun joka oli pystyy varastoimaan 10 jouset. Emme aio tehdä sitä enää. Tiedämme jo rajoitukset kyseistä menetelmää. Nyt meidän tiiviste tulee olemaan joukko 10 solmuja, osoittimet päälliköille linkitettyjen listojen. 

Ja nyt se on null. Jokainen näistä 10 viitteitä on null. Ei ole mitään meidän hash taulukko juuri nyt. 

Nyt alkaa laittaa asiat tähän tiiviste. Ja katsotaan, miten tämä menetelmä on aikoo hyötyä meille hieman. Katsotaanpa nyt hash Joey. Me ajaa merkkijono Joey kautta hajautusfunktiota ja palaamme 6. No mitä teemme nyt? 

No nyt työskentelee linkitettyjen listojen, emme kanssa paneelit. Ja kun pyrimme linkitettyjä luetteloita meillä tietävät meidän on aloitettava dynaamisesti jakamisesta tilaa ja rakennuksen ketjut. Se on eräänlainen how-- ne ovat keskeisiä elementit rakentaa linkitetyn listan. Joten dynaamisesti jakaa tilaa Joey, ja sitten katsotaanpa lisätä hänet ketjuun. 

Joten nyt näyttää mitä olemme tehneet. Kun me hash Joey saimme hashcode 6. Nyt kohdistin array sijainti 6 viittaa pään linkitetty lista, ja nyt se on ainoa osa linkitetyn listan. Ja solmu että linkitetty lista on Joey. 

Joten jos meidän etsiä Joey myöhemmin, me vain hash Joey uudelleen, saamme 6 uudelleen, koska meidän tiivistefunktio on deterministinen. Ja sitten aloitamme kärjessä on linkitetyn listan huomautti TO array sijainti 6, ja voimme kerrata poikki yrittää löytää Joey. Ja jos me rakennamme tiiviste tehokkaasti, ja meidän hajautusfunktio tehokkaasti jakaa tietoja hyvin, keskimäärin jokainen näistä liittyvät luettelot kaikissa array sijainti on kymmenesosa koko, jos me vain oli se yhtenä valtava linkitetty lista kaiken siinä. 

Jos jaamme että valtava liittyvät luettelo yli 10 linkitettyjen listojen kukin luettelo on kymmenesosa koko. Ja näin 10 kertaa nopeammin etsiä. Joten tehdä tätä uudelleen. Katsotaanpa nyt hash Ross. 

Ja sanotaanko Ross, kun me teemme, että hash palaamme on 2. No nyt meillä dynaamisesti jakaa uusi solmu, laitamme Ross että solmu, ja sanomme nyt array sijainti 2, sen sijaan osoittaa null, viittaa pää liittyy lista jonka ainoa solmu on Ross. Ja voimme tehdä tämän vielä kerran, me voi hash Rachel ja saada hashcode 4. malloc uusi solmu, laita Rachel vuonna solmu, ja sanoa array sijainti 4 nyt viittaa pään linkitetyn listan, jonka vain osa sattuu olemaan Rachel. 

OK, mutta mitä tapahtuu, jos meillä törmäyksen? Katsotaanpa, miten voimme käsitellä törmäykset käyttämällä erillistä ketjutuksen menetelmällä. Katsotaanpa hash Phoebe. Saamme hashcode 6. Edellisessä esimerkissä olimme tallennetaan merkkijonoja jono. Tämä oli ongelma. 

Emme halua hakata Joey, ja olemme jo nähdä, että saamme joitakin klustereiden ongelmia, jos yritämme askel kautta ja koetin. Mutta entä jos olemme juuri sellainen käsitellä tätä samalla tavalla, eikö? Se on aivan kuten lisäämällä elementti johtaja linkitetyn listan. Haluan vain malloc tilaa Phoebe. 

Me sanoa Phoeben seuraava osoitin vanha johtaja linkitetyn listan, ja sitten 6 vain osoittaa uusi johtaja linkitetyn listan. Ja nyt näyttää, olemme muuttaneet Phoebe. Voimme nyt tallentaa kaksi elementtien hashcode 6, ja meillä ei ole mitään ongelmia. 

Se on aika paljon kaikki siellä on ketjutus. Ja ketjutus on ehdottomasti menetelmä, joka on olemaan tehokkain sinulle, jos tallennat tietoja hash table. Mutta tämä yhdistelmä taulukot ja linkitettyjen listojen yhteen muodostaen hajautustaulun todella dramaattisesti parantaa kykyäsi tallentaa suuria määriä dataa, ja hyvin nopeasti ja tehokkaasti etsiä kautta, että tiedot. 

Vielä yksi tietorakenne siellä jotka saattavat jopa olla hieman paremmin ehdoin taata että lisäys, poisto, ja etsiä ajat ovat vieläkin nopeammin. Ja näemme, että video yrittää. Olen Doug Lloyd, tämä on CS50.