[Muusika mängib] DOUG LLOYD: Nüüdseks olete teavad palju massiivid, ja sa tead palju ahelloendid. Ja me oleme arutada plusse ja miinuseid, me oleme arutati, et ahelloendid saavad suuremad ja väiksemad, kuid nad võtavad rohkem suurust. Massiivid on palju lihtne kasutada, kuid nad piiravad nii palju kui me peame seadma suurus massiivi alguses ja siis me ummikus see. 

Aga see, me oleme päris palju ammendanud kõik meie teemasid umbes ahelloendid ja massiivid. Või on meil? Võib-olla me saame teha midagi isegi loovamaks. Ja seda sorti laenab idee hash tabelit. 

Nii et hash tabelit me ei kavatse proovida ühendada massiivi ahelloend. Me läheme eelised massiivi, nagu muutmälu, on võimalik lihtsalt minema massiivi element 4 või massiivi element 8 ilma et korrata üle. See on päris kiire, eks? 

Aga tahame ka meie andmeid struktuuri saaks kasvada ja kahaneb. Meil ei ole vaja, me ei tahan olla piiratud. Ja me tahame, et oleks võimalik lisada ja eemaldada asju väga lihtne, mis siis, kui te mäletate, on väga keeruline massiivi. Ja me nimetame seda uus asi räsi tabelis. 

Ja kui rakendatakse õigesti, me mingi võttes eeliseid nii andmete struktuuride olete juba näinud, massiivid ja ahelloendid. Sisestamine võib hakata kalduvust teeta 1. Theta me ei ole tõesti arutatud, kuid teeta on lihtsalt keskmisest juhul, mis tegelikult juhtub. Sa ei ole alati läheb on halvimal juhul, ja sa ei ole alati saab olema Parimal juhul, siis millised keskmine stsenaarium? 

Noh keskmiselt sisestamise arvesse hash tabelis saab hakkama saada lähedal konstantset aega. Ja kustutamist saad sulgeda pidevalt aega. Ja lookup saab sulgeda pidevalt aega. On-- me ei ole andmebaasi struktuuri veel, et ei saa seda teha, ja nii see juba kõlab nagu päris suur asi. Me oleme tõesti kergendanud puudused iga oma. 

Et saada selle etenduse uuendada küll, me vaja mõelda, kuidas me lisada andmed selle struktuuri. Nimelt tahame andmed ise meile öelda kus see peaks minema struktuuri. Ja kui me siis peame nägema, kui see on struktuuri, kui meil on vaja üles leida, tahame vaadata andmeid uuesti ja suutma tõhusalt, Andmete kasutamisel juhuslikult ligi. Lihtsalt vaadates andmed meil peaks olema idee, kus täpselt me ​​oleme leiame seda hash tabelit. 

Nüüd negatiivsed räsi Tabelis on see, et nad on tõesti päris halb tellimise või sorteerimine andmeid. Ja tegelikult, kui hakkate kasutada neid tellida või järjesta andmed sa kaotad kõik eeliseid, mida varem oli nii sisestamise ja kustutamise. Kell saab lähemale teeta n, ja me oleme põhiliselt taandarenenud arvesse ahelloend. Ja nii me ainult tahame kasutada hash tabelid, kui me ei hooli kas andmed on järjestatud. Selles kontekstis, kus saate neid kasutada CS50 siis ilmselt ei hooli et andmed järjestatud. 

Nii hash tabelis on kombinatsioon kahest erinevast tükki kellega me oleme tuttavad. Esimene on funktsioon, mis me tavaliselt nimetame hash funktsiooni. Ja et hash funktsiooni saab tagasi mõned mittenegatiivne täisarv, mis me tavaliselt nimetame räsikood, OK? Teine tükk on massiiv, mis on võimeline talletama andmeid tüübi me tahad pane andmestruktuur. Me hoidke off ahelloendid element nüüd ja lihtsalt alustada põhitõdesid hash tabelit, et su pea ümber, ja siis me võibolla puhuda meelt natuke, kui me ühendada massiivid ja link nimekirjad koos. 

Põhiidee kuigi on meil võtta mõned andmed. Juhime et andmete abil hash funktsiooni. Ja nii andmeid töödeldakse ja see sülitab välja mitmeid, OK? Ja seejärel, et number me lihtsalt salvestada andmeid Me tahame hoida ka massiivi selles asukohas. Nii näiteks on meil võibolla see hash tabelit stringid. See ju 10 elementi, seega meil mahub 10 stringid ta. 

Oletame, et me tahame hash John. Nii Johannes andmeid me tahame lisada sellesse hash tabelis kusagil. Kust me seda? Noh tavaliselt koos massiivi nii kaugele me ilmselt paneks ta massiivi 0. Aga nüüd on meil see uus hash funktsiooni. 

Ja ütleme, et võtame John läbi selle hash funktsiooni ja see sülitab välja 4. Noh, et kus me oleme läheb taha panna John. Tahame panna John massiivi asukohta 4, sest kui me hash John again-- oletame hiljem me soovite otsida ja vaadata Kui John esineb selles hash table-- kõik me peame tegema juhib ta läbi sama räsi funktsioon, saada number 4 välja, ja suutma leida John kohe meie andmestruktuur. See on päris hea. 

Oletame, et me nüüd teeme seda jälle, me tahame hash Paul. Me tahame, et lisada Paul sellesse hash tabelit. Oletame, et seekord võtame Paul läbi hash funktsiooni, räsikood edastatakse, mis on loodud on 6. Noh nüüd saab panna Paul massiivi asukoha 6. Ja kui meil on vaja otsida, kas Paul on selles hash tabelit, kõik me peame tegema, on käivitada Paul läbi hash funktsiooni uuesti ja me ei kavatse saada 6 jälle. 

Ja siis me lihtsalt vaadata kell massiivi asukoha 6. Kas Paul on? Kui jah, ta on hash tabelit. Kas Paul ole olemas? Ta ei räsi tabelis. See on üsna lihtne. 

Nüüd, kuidas sa määratleda hash funktsiooni? Noh seal on tõesti mingeid piiranguid arvu võimalik räsifunktsioone. Tegelikult seal on mitmeid tõesti, tõesti head internetis. Seal on mitmeid tõesti, tõesti halvad internetis. See on ka üsna lihtne kirjutada halb. 

Nii teebki up hea hash funktsiooni, eks? Noh hea hash funktsiooni peaksid kasutada ainult andmed on räsitud, ja kõik andmed ohtu räsitud. Nii et me ei taha kasutada anything-- meil ei sisalda midagi muud peale andmeid. Ja me tahame kasutada kõiki andmeid. Me ei taha lihtsalt kasutada tükk sellest, tahame kasutada kõik. Hash funktsioon peab Samuti on determineeritud. Mida see tähendab? Aga see tähendab, et iga kord, kui me edasi täpselt sama tükk andmed arvesse hash funktsiooni me alati saada sama räsikood välja. Kui ma edasi John sisse hash funktsiooni ma saan välja 4. Ma peaks olema võimalik teha, et 10000 korda ja ma alati 4. Nii ei juhuslike arvude tõhusalt võib olla seotud meie hash tables-- Meie räsifunktsioone. 

Hash funktsioon peaks ka ühtlaselt jaotada andmed. Kui iga kord, kui käivitad kaudu andmeid hash funktsiooni saad räsikood 0, et ilmselt ei ole nii suur, eks? Sa ilmselt tahad suured vahemikus räsikoodid. Samuti asju võib levida välja kogu tabel. Ja ka see oleks tore, kui tõesti samasugune, nagu John ja Jonathan, võibolla olid laiali lööma erinevates kohtades hash tabelit. See oleks kena ära. 

Siin on näide hash funktsiooni. Kirjutasin selle ühe kuni varem. See ei ole eriti hea hash funktsiooni põhjustel, mis ei ole tegelikult kandma laskumist kohe. Aga sa vaata, mis siin toimub? Tundub nagu me kuulutab muutuja nimetatakse summa, ning kehtestatakse võrdne 0. Ja siis ilmselt teen midagi nii kaua kui strstr [j] ei ole võrdne to kurakriips 0. Mida ma teen seal? 

See on põhimõtteliselt lihtsalt üks rakendusaktiga [? strl?] ja avastada, kui olete jõudis lõpuks string. Nii et ma ei pea tegelikult arvutada stringi pikkusena, Ma lihtsalt kasutades, kui ma tabanud kurakriips 0 iseloomu Tean Olen jõudnud lõpuks string. Ja siis ma lähen hoida iterating läbi, et string, Lisades strstr [j] Kokkuvõttes, ja siis on Päeva lõpuks läheb tagasi summa mod HASH_MAX. 

Põhimõtteliselt kõik selle räsi funktsioon teeb lisab kuni kõik ASCII väärtused minu string, ja siis on see tagasi mõned räsikood modida poolt HASH_MAX. See on ilmselt suurus minu rida, eks? Ma ei taha saada hash koodid, kui minu rida on suurus 10, Ma ei taha olla saada välja räsikoodid 11, 12, 13, ma ei saa panna asjad need kohad massiivi, mis oleks ebaseaduslik. Ma kannatavad killustatust süü. 

Nüüd siin on teise kiire kõrvale. Üldiselt sa ilmselt ei kavatse tahan kirjutada oma räsifunktsioone. See on tegelikult natuke kunst, mitte teadus. Ja seal on palju, mis läheb neile. Internet, nagu ma ütlesin, on täis tõesti hea räsifunktsioone, ja sa peaksid kasutama internetti leida räsifunktsioone sest see on tõesti lihtsalt selline ebavajalik ajaraiskamine luua oma. 

Võite kirjutada lihtsaid testimise eesmärgil. Aga kui sa tegelikult ei kavatse alustada hashing andmed ja säilitamist arvesse hash tabelit sa oled ilmselt läheb taha kasutada mõnda funktsiooni, mis oli loodud teile, et on olemas internet. Kui sa just kindlasti tsiteerida oma allikaid. Ei ole mingit põhjust, et Plagioida siin midagi. 

Computer Science kogukond kindlasti kasvab, ja tõesti väärtused avatud lähtekoodiga, ja see on tõesti oluline tsiteerida oma allikatest, et inimesed saab omistamisega eest töö, et nad teeme selle hüvena. Nii alati sure-- ja mitte ainult hash funktsioone, kuid üldiselt kui kasuta koodi väljaspool allikas, alati tuua oma allikas. Anna krediidi isik, kes tegi mõned tööd, et sa ei pea. 

OK, nii olgem vaadata seda hash tabelis teiseks. See on koht, kus me lahkusime välja pärast me sisestatud John ja Paul sellesse hash tabelit. Kas te näete siin probleemi? Sa võid näha kaks. Aga eelkõige, kas sa vaata seda võimalikku probleemi? 

Mis siis, kui ma hash Ringo, ja see Selgub, et pärast töötlemist et andmed läbi hash funktsiooni Ringo ka genereerinud räsikood 6. Olen juba saanud andmeid hashcode-- massiivi asukoha 6. Nii et see on ilmselt saab olema natuke probleem minu jaoks praegu, eks? 

Me nimetame seda kokkupõrget. Ja kokkupõrge toimub siis, kui kaks tükki andmeid läbib sama räsi funktsiooni saada sama räsikood. Arvatavasti me ikka tahad nii tükki andmeid hash tabelit, muidu ei saa töötab Ringo suvaliselt läbi hash funktsiooni. Me ilmselt tahad saada Ringo arvesse, et massiivi. 

Kuidas me seda teeme küll, kui ta ja Paul nii tulu- räsikood 6? Me ei taha kirjutada Paul, tahame Paul olla ka seal. Seega peame leidma viisi, kuidas saada elemendid hash tabelit, et ikka säilitab oma kiire sisestamise ja pilgu üles. Ja üks viis lahendada see on teha midagi, mida nimetatakse lineaarselt katsetamine. 

Seda meetodit kasutades, kui meil on Kokkupõrke, noh, mida me teeme? Noh me ei saa teda massiivi asukohta 6, või mis iganes räsikood tekkinud, paneme teda räsikood pluss 1. Ja kui see täis olgem pani ta räsikood pluss 2. Kasu on see olevus, kui ta on ei täpselt, kus me arvan, et ta on, ja me peame hakkama otsima, võibolla me ei pea minema liiga kaugele. Võib-olla me ei pea otsima kõik n elemendid hash tabelit. Võib-olla on meil otsida paar neist. 

Ja nii me ikka kipub suunas et keskmine juhul on peaaegu 1 vs lähedal n, et äkki, et teen tööd. Vaatame, kuidas see võiks töötada välja tegelikkus. Ja vaatame, kui äkki saame tuvastada probleemi, mis võib esineda siin. 

Oletame, et meil hash Bart. Nüüd me läheme sõitma uued stringid läbi hash funktsiooni, ja võtame Bart läbi hash funktsiooni, saame räsikood 6. Me vaatleme, siis näeme 6 tühi, nii et me ei pane Bart seal. 

Nüüd hash Lisa ja et Samuti tekitab räsikood 6. Noh nüüd, et me kasutame seda lineaarne katsetamine meetod hakkame kell 6, näeme, et 6 on täis. Me ei saa panna Lisa 6. Nii et kui me läheme? Lähme 7. 7 on tühi, nii et töötab. Nii paneme Lisa olemas. 

Nüüd hash Homer ja saame 7. OK hästi teame, et 7 täielikku nüüd, et me ei saa Homer seal. Nii lähme 8. Kas 8 kättesaadav? Jah, ja 8 on ligi 7, nii et kui meil hakkab otsima me oleme ei kavatse lasta minna liiga kaugele. Ja nii paneme Homer kell 8. 

Nüüd hash Maggie ja tagasi 3, jumal tänatud me saame lihtsalt panna Maggie seal. Me ei pea tegema muud omamoodi katsetamine selle eest. Nüüd hash Marge ja Marge ka tagasi 6. 

Noh 6 on täis, 7 on täis, 8 on täis, 9, kõik õige jumal tänatud, 9 on tühi. Ma ei pane Marge kell 9. Juba on näha, et me oleme hakanud on see probleem, kus nüüd oleme alates venitada asju omamoodi on kaugel oma räsikoodid. Ja et teeta 1, et keskmine Kui on pidev aega, hakkab natuke more-- hakanud kipuvad veidi rohkem suunas teeta n. Me küsime kaota ära hash tabeleid. 

See probleem, et me lihtsalt nägin on midagi, mida nimetatakse loomist. Ja mis on tõesti halb umbes rühmitamise on, et kui sa nüüd on kaks elementi, mis asuvad üksteise küljele see muudab veelgi tõenäolisem, Teil on kaks korda võimalus, et sa lähed on teine ​​kokkupõrge selle klastri, ja klastri kasvab üks. Ja sa hoida kasvab ja kasvab Sinu esinemise tõenäosus kokkupõrke. Ja lõpuks, see on lihtsalt nii halb mitte andmete sorteerimist üldse. 

Teine probleem, kuigi on meil ikka, ja seni kuni see punkt, oleme lihtsalt omamoodi mõista, mida hash tabelis on me alles on ruumi 10 stringe. Kui me tahame jätkata hash kodanike Springfield, meil on võimalik ainult saada neist 10 on. Ja kui me püüame lisada 11. või 12., meil ei ole koht, kus neid ellu. Me võiksime lihtsalt ketramine ringi ringid, püüdes leida tühja koha, ja me äkki jänni lõputu silmuse. 

Nii selline laenab idee on midagi, mida nimetatakse aheldamine. Ja see on koht, kus me ei kavatse tuua ahelloendid tagasi pildil. Mis siis, kui selle asemel ladustamiseks lihtsalt andmed ise massiivi, iga element massiivi võiks hoidke mitu tükki andmeid? Noh, et ei ole mõtet, eks? Me teame, et massiivi saab ainult hold-- iga massiivi elemendile saab omada ainult üks tükk andmete, et andmete tüübi. 

Aga mis siis, kui andmetüüp on seotud nimekirja, eks? Mis siis, kui iga massiivi element oli kursor juht ahelloend? Ja siis me võiks ehitada need ahelloendid ja kasvatada neid meelevaldselt, sest ahelloendid võimaldavad meil kasvada ja kahaneb palju paindlikumalt kui massiivi teeb. Mis siis, kui me nüüd kasutada, meil võimendada seda, eks? Meil hakkavad kasvama need ketid välja need massiivi kohtades. 

Nüüd mahub lõpmatu andmemaht või mitte lõpmatu, suvalise summa andmed, meie hash tabelis pole kunagi suubuvad probleemi kokkupõrget. Samuti oleme kõrvaldanud klastrite seda teed. Ja ka me teame, et kui me sisestada arvesse ahelloend, kui te mäletate meie video ahelloendid, üksikult ahelloendid ja kahekordselt ahelloendid, see on pidev aega tööd. Me lihtsalt lisades ees. 

Ja vaadake üles ja me ei tea, et otsida üles ahelloend võib olla probleem, eks? Meil on otsida see algusest lõpuni. Pole juhuslik juurdepääsu ahelloend. Aga kui selle asemel üks on seotud nimekirja, kus lookup oleks O n, nüüd on meil 10 ahelloendid, või 1000 ahelloendid, nüüd on O n jagatud 10, või O n jagatud 1000. 

Ja kuigi me rääkisime teoreetiliselt umbes keerukus me eirata konstandid, reaalses maailma need asjad tegelikult oluline, õige? Me tegelikult ei märka et see juhtub joosta 10 korda kiiremini, või 1000 korda kiiremini, sest me jaotavad üks pikk kett üle 1000 väiksemate ketid. Ja nii iga kord on meil otsida läbi üks neist kettidest saame ignoreerida 999 ketid me ei hooli umbes, ja lihtsalt otsida, et üks. 

Milline on keskmiselt olla 1000 korda lühem. Ja nii me ikka oleme omamoodi kalduvad selles suunas keskmiselt juhul olla pidev aega, kuid ainult sellepärast, et meil on võimendades jagades mõned suured konstandiks. Vaatame, kuidas see võib tegelikult vaatama küll. Nii et see oli hash tabelis pidime enne julistimme hash tabelit, et oli võimalik säilitada 10 stringe. Me ei kavatse seda teha enam. Me juba teame piiranguid, mis meetodil. Nüüd on meie hash tabelit saab olema massiivi 10 sõlmed, viiteid juhtidele ahelloendid. 

Ja praegu on null. Iga üks neist 10 suunanäitajaks on null. Pole midagi meie hash tabelit kohe. 

Nüüd alustame panna mõned asju sellesse hash tabelit. Vaatame, kuidas see meetod on läheb meile kasu natuke. Olgem nüüd hash Joey. Me kestab string Joey läbi räsi funktsioon ja me tagasi 6. Noh, mis me nüüd teeme? 

Noh nüüd töötavad ahelloendid, me ei tööta massiivid. Ja kui me töötame lingitud nimekirjad me tea me peame hakkama dünaamiliselt eraldada ruumi ja hoone ketid. See on omamoodi how-- need on peamised elemendid hoone ahelloend. Nii saab dünaamiliselt eraldada ruumi Joey, ja siis lisame teda ketti. 

Nüüd vaatame, mida me oleme teinud. Kui me hash Joey saime räsikood 6. Nüüd osuti massiivi asukoha 6 osutab juht ahelloend, ja just nüüd on see ainus element ahelloend. Ja sõlme, et ahelloendid on Joey. 

Nii et kui meil on vaja üles otsima Joey hiljem, me lihtsalt hash Joey uuesti, saame 6 jälle, sest meie hash funktsiooni on determineeritud. Ja siis hakkame eesotsas on seotud nimekirja märkis poolt massiivi asukohta 6, ja me võime kinnitada, üle, mis üritab leida Joey. Ja kui me ehitame meie hash tabelis tõhusalt, ja meie hash funktsiooni efektiivselt levitada andmeid ka, keskmiselt iga neist seotud nimekirjad iga massiivi asukohta saab 1/10 suurust kui me oli just see ühe suure ahelloendid kõike seda. 

Kui me jagada, et tohutu seotud nimekirja üle 10 ahelloendid Iga nimekirjas on 1/10 suurust. Ja nii 10 korda kiiremini otsida. Nii teeme seda jälle. Olgem nüüd hash Ross. 

Ja oletame, et Ross, kui me seda teeme hash kood saame tagasi on 2. Noh nüüd me dünaamiliselt eraldada uus sõlm, paneme Ross, et sõlm, ja ütleme nüüd massiivi asukohta 2 asemel juhtides tühjaks, osutab juht seotud nimekirja, kelle ainus sõlm on Ross. Ja me saame seda teha veel üks kord, siis võib hash Rachel ja saada räsikood 4. malloc uus sõlm, pane Rachel sõlme, ja öelda massiivi asukohta 4 nüüd juhib pea on seotud nimekirja, kelle ainult element juhtub olema Rachel. 

OK, aga mis juhtub siis, kui meil kokkupõrge? Vaatame, kuidas me käsitleme kokkupõrked kasutades eraldi ühendamine meetod. Olgem hash Phoebe. Saame räsikood 6. Meie eelmises näites me olime lihtsalt ladustamiseks stringid massiivi. See ilmnes probleem. 

Me ei taha Tellida Joey, ja me oleme juba näha, et saame mõne klastrite probleeme, kui püüame ja samm läbi ja põhja. Aga mis siis, kui me lihtsalt selline käsitleda seda samamoodi, eks? See on nagu lisades element to juht ahelloend. Lihtsalt malloc ruumi Phoebe. 

Me ütleme Phoebe järgmise pointer punktid vana juht seotud nimekirja, ja siis 6 lihtsalt viitab uue juhi seotud nimekirja. Ja nüüd vaatame, oleme muutnud Phoebe. Nüüd on võimalik salvestada kaks elemente räsikood 6, ja meil ei ole mingeid probleeme. 

See on päris palju kõik seal on ühendamine. Ja ühendamine on kindlasti meetod, mis on saab olema kõige efektiivsem Sulle, kui te andmete salvestamiseks räsi tabelis. Aga see kombinatsioon massiivid ja ahelloendid kokku, moodustamaks hash tabelit tegelikult dramaatiliselt parandab teie võimet talletada suurel hulgal andmeid ja väga kiiresti ja tõhusalt otsida läbi, et andmeid. 

Seal on veel üks andmestruktuur seal et võib-olla isegi natuke parem nii tagamisel et meie lisamise, kustutamise ja otsida ajad on veelgi kiirem. Ja me näeme, et video proovib. Ma olen Doug Lloyd, see on CS50.