[Zenelejátszási] DOUG LLOYD: Mostanra Sokat tud tömbök, és tudod, hogy sokat láncolt listák. És mi már megvitatására érvek és ellenérvek, most már megvitatták, hogy a kapcsolt listák kap nagyobb és kisebb, de ebben az esetben több méretben. A tömbök sokkal egyszerűbb a használja, de ők korlátozó annyi valamint át kell állítani a méretét A tömb a legelején majd ragadtunk vele. 

De ez, most már elég sok kimerítette minden kedves témák mintegy kapcsolódó listák és tömbök. Vagy van még? Talán tehetünk valamit még több kreatív. És ez a fajta kölcsönöz Az ötlet egy hash tábla. 

Tehát egy hash tábla fogunk próbálni egyesítik egy tömb, láncolt lista. Fogunk figyelembe előnyeit a tömb, mint a véletlen hozzáférésű, hogy képes csak megy a tömb 4 elem vagy tömb elemek 8 anélkül, hogy ismételget szerte. Ez elég gyors, nem igaz? 

De azt is szeretnénk, hogy adatainkat struktúra képes növekedni, és összezsugorodik. Nem kell, mi nem akarjuk korlátozni kell. És azt akarjuk, hogy képes hozzáadása és eltávolítása a dolgokat nagyon könnyen, amelyek, ha emlékeznek rá, nagyon komplex egy tömb. És nevezhetjük ezt új dolog egy hash tábla. 

És ha végre rendesen, mi fajta figyelembe előnyeit mindkét adat struktúrák már láttad, tömbök és kapcsolt listák. Behelyezés lehet kezdeni Hajlamos theta 1. Theta még nem igazán vitatták, de théta csak átlagos esetre, mi valóban meg fog történni. Te nem mindig lesz a legrosszabb forgatókönyv esetén, és te nem mindig megy, hogy A legjobb esetben, tehát mi Az átlagos forgatókönyv? 

Nos átlagosan beillesztés egy hash tábla lehet kezdeni, hogy közel állandó időt. És törlés kaphat közel állandó időt. És keresési kaphat közel állandó időt. That's-- nincs adat szerkezete még, hogy meg tudom csinálni, és így ez már hangzik mint egy szép nagy dolog. Már tényleg enyhíteni a hátrányait az egyes saját. 

Ahhoz, hogy ez a teljesítmény frissíteni mégis, akkor kell gondolnunk, hogyan tudjuk felvenni adatok a szerkezet. Különösen szeretnénk a adatok is, hogy elmondja nekünk ahol kell menni a szerkezetben. És ha majd kell, hogy ha ez a a szerkezet, ha meg kell találni azt, azt akarjuk, hogy nézd meg az adatokat újra és képes hatékonyan, adatok felhasználásával, véletlenszerűen hozzáférni. Ránézésre a adatokat kellett volna egy ötlet, hogy pontosan hol vagyunk fogja megtalálni a hash táblában. 

Most a hátránya a hash asztalhoz, hogy ők nagyon Elég rossz a megrendelésnél vagy válogatás adatokat. És valóban, ha elkezd használni őket rendelni, vagy egyfajta adatok elveszíti az összes előnyök korábban Volt szempontjából behelyezés és törlése. Az idő lesz közelebb téta N, és mi már alapvetően visszafejlődött egy láncolt lista. És így mi csak azt akarjuk használni hash asztalok ha nem érdekel hogy az adatok megfelelően rendezve. A környezet, amelyben akkor használja őket CS50 akkor valószínűleg nem érdekel hogy az adatok sorrendje. 

Tehát egy hash tábla kombinációja két különálló darab amellyel vagyunk tisztában. Az első egy olyan funkció, amely szoktunk hívni a hash függvény. És, hogy hash függvény fog visszatérni néhány nem-negatív egész, ami szoktunk hívni a hashcode, OK? A második darab egy tömb, amely tárolására képes adatok a típus mi kívánja helyezni adatstruktúrájába. Majd tartja magát a láncolt lista elem most és csak kezdeni az alapokat egy hash tábla, hogy a fejed körül, aztán majd talán robbantani az agyad egy kicsit, amikor egyesítik tömbök és linklisták együtt. 

Az alapötlet bár van veszünk néhány adatot. Futunk, hogy az adatok a A hash függvény. És így az adatfeldolgozás és kiköpi több, OK? És akkor ez a szám mi csak tárolja az adatokat szeretnénk tárolni a tömb az adott helyen. Így például már talán ez a hash tábla a szálakat. Van rajta 10 elemek is, így Mi fér 10 húrok benne. 

Tegyük fel, hogy szeretnénk a hash John. Szóval John mivel az adatok azt szeretné szúrni ebbe a hash tábla valahol. Hol rakjuk? Hát általában egy tömb eddig mi valószínűleg azt tedd tömb 0 helyen. De most itt van ez az új hash függvény. 

És mondjuk, hogy mi fut John ezen keresztül hash függvény és ez kiköpi 4. Hát ez az, ahol mi vagyunk szeretne majd fel John. Azt szeretnénk, hogy John a tömb helyét 4, mert ha hash John again-- mondjuk később kíván keresni és látni ha John létezik ezen a hash table-- minden meg kell tennie fut át ​​az azonos hash funkciót, hogy a 4-es számú ki, és képes megtalálni John Azonnal adataink szerkezete. Ez elég jó. 

Mondjuk most ezt Még egyszer, a hash-Paul. Szeretnénk felvenni Pál ebbe hash tábla. Tegyük fel, hogy ebben az időben futunk Paul át a hash függvény, a hashcode generált 6. Hát most tehetünk bele Paul A tömb helyen 6. És ha kell keresni, hogy Pál ebben a hash tábla, minden meg kell tennie, hogy fut Pál a hash függvény újra és mi lesz, hogy 6 ki újra. 

És akkor csak nézd A tömb helyen 6. Paul van? Ha igen, ő a hash táblában. Pál nem volt ott? Ő nem a hash táblában. Ez elég egyértelmű. 

Most hogyan határozná meg a hash függvény? Hát már tényleg nincs határa a számú lehetséges hash függvények. Valójában van néhány igazán, Nagyon jók az interneten. Van néhány igazán, Nagyon rosszak az interneten. Ez is nagyon egyszerű hogy írjon egy rossz. 

Szóval mit tesz egy jó hash függvény, igaz? Hát jó hash függvényt csak a továbbított adatok hashed, és az összes adatot, hogy hashed. Szóval nem akarjuk használni bármit mi nem bele semmit mást eltérő az adatokat. És szeretnénk használni az összes adatot. Nem akarjuk, ha csak egy darab azt, hogy szeretnénk használni az egészet. Egy hash függvényt szintén determinisztikus. Az mit jelent? Nos ez azt jelenti, hogy minden alkalommal át pontosan ugyanazt az adatot a hash függvény mindig kap ugyanaz hashcode ki. Ha elmegyek Johnt a hash függvény kikerülök 4. Azt kell tudni csinálni, hogy 10.000 idők és én mindig kap 4. Tehát nem véletlen számokat hatékonyan bevonhatók a hasító tables-- a hasító függvények. 

A hash funkció azt is egyenletesen osszuk adatok. Ha minden alkalommal futtatja az adatokat a hash függvény megkapja az hashcode 0, ez talán nem olyan nagy, igaz? Talán szeretnénk nagy egy sor hash kódok. Szintén dolgokat is terjed ki az egész táblázatot. És azt is, hogy jó lenne, ha tényleg hasonló, mint John és Jonathan, Talán arra terjedt ki, hogy mérjük különböző helyeken a hash táblában. Ez lenne a szép előnyt. 

Íme egy példa egy hash függvény. Írtam ezt fel korábban. Ez nem egy különösen jó hash függvény okok miatt nem igazán viselik megy most. De látod, mi folyik itt? Úgy tűnik, mintha mi nyilvánító változó nevezett összeg és a beállítás, 0-val egyenlő. És akkor nyilván én csinálok valamit mindaddig, amíg strstr [j] nem egyenlő a backslash 0. Mit csinálok itt? 

Ez alapvetően csak egy újabb végrehajtásán [? strl?] és felderítésére, ha már végére ért a húr. Szóval nem kell ténylegesen kiszámítja a hossza a húr, Én csak használ, amikor elütöttem a backslash 0 karaktert tudom Én elérte a végén a húr. És akkor fogok tartani iterációjával keresztül, hogy a húr, hozzátéve strstr [j] összefoglalni, majd a A nap végén fog visszatérni összeget mod HASH_MAX. 

Alapvetően mindez hash funkciót tesz, hogy összeadjuk az összes ASCII értékeinek én húr, és akkor itt visszatérő néhány hashcode Megvan a módosított által HASH_MAX. Valószínűleg ez a méret Az én tömb, ugye? Nem akarom, hogy egyre hash kódokat, ha a tömb mérete 10, Nem akarom, hogy egyre ki hash kódok 11, 12, 13, nem tudom tenni a dolgokat ezeken a helyeken a tömb, hogy jogellenes lenne. Én szenvednek szegmens hiba. 

Most itt van egy újabb gyors félre. Általában akkor valószínűleg nem fog szeretné írni a saját hash függvények. Ez valójában egy kicsit művészet, nem tudomány. És van egy csomó, hogy megy be őket. Az internet, mint mondtam, tele van Az igazán jó hash függvények, és akkor használja az internetet találni hash függvények, mert nagyon csak ilyen szükségtelen időpocsékolás, hogy saját. 

Írhatsz egyszerű is tesztelési célokra. De ha valóban lesz kezdeni hashing adatok és tárolás hasító táblába te Valószínűleg szeretne majd használni néhány funkciót, hogy keletkezett Önnek, hogy létezik az interneten. Ha csak legyen biztos hogy idézni a forrást. Nincs ok arra, hogy plagizál itt semmit. 

A számítástechnika közösség egyértelműen növekszik, és tényleg értékek nyílt forráskódú, és ez nagyon fontos hogy idézni a forrást, hogy az emberek kaphat szerzőjének a munkát, amit ők Ennek az a közösség javára. Így mindig sure-- és nem csak a hash funkciók, de általában ha Használja kódot külső forrásból származó, Mindig idézni a forrást. Hitelt ad az a személy, aki nem a munka egy részét, így nem kell. 

OK úgyhogy újra ezt hash tábla egy pillanatra. Ez az, ahol hagytuk off miután behelyezett János és Pál ebbe a hash tábla. Látsz egy probléma van? Lehet, hogy két. De különösen igaz lásd erre a lehetséges problémára? 

Mit tegyek, ha hash Ringo, és ez Kiderül, hogy a feldolgozás után hogy az adatokat a hash függvény Ringo is előállítottak a hashcode 6. Már van adatok hashcode-- tömb helyen 6. Szóval ez valószínűleg lesz egy kicsit A probléma most nekem, ugye? 

Hívjuk ezt az ütközést. És az ütközés fordul elő, amikor a két adattartalommal végigmenni ugyanazon a hash funkciót, így azonos hashcode. Feltehetően még mindig szeretné, hogy a két adattartalommal a hash tábla, különben nem fut Ringo önkényesen át a hash függvény. Azt szeretnénk, hogy feltehetően Ringo be a tömbben. 

Hogy csináljuk, hogy mégis, ha és Paul mindkét hozam hashcode 6? Mi nem akarja felülírni Pál, akarunk Pál is ott lesz. Tehát meg kell találni a módját, hogy elemek a hash tábla még ma is őrzi a gyors behelyezése és gyors pillantást fel. És az egyik módja, hogy foglalkozzon vele, hogy tenni valamit az úgynevezett lineáris szondázás. 

Ezzel a módszerrel, ha van egy ütközés, nos, mit csináljunk? Hát nem tudunk vele tömb helyét 6, vagy bármi hashcode keletkezett, tegyük rá a hashcode plusz 1. És ha ez a teljes nézzük tedd rá hashcode plusz 2. Az előnye ennek a lénynek, ha ő Nem pontosan hol azt gondoljuk, ő, és meg kell kezdeni a keresést, talán nem kell túl messzire menni. Talán nem kell keresni minden n eleme a hash tábla. Talán meg kell keresni egy pár közülük. 

És ezért vagyunk még hajló hogy egy átlagos esetben, hogy közel 1 vs közel n, így lehet, hogy működni fog. Nézzük, hogy ez hogyan Lehet, dolgozzanak ki a valóságban. És lássuk, talán tudunk észlelni Az előforduló probléma, hogy itt. 

Mondjuk hash Bart. Tehát most fogunk futni egy sor új A húrok át a hash függvény, és mi fut Bart át a hash funkciót, kapunk hashcode 6. Veszünk egy pillantást, látjuk a 6. üres, így tudjuk Bart van. 

Most hash Lisa és hogy is generál hashcode 6. Hát most, hogy ezt a lineáris szondázás módszerrel kezdjük 6, azt látjuk, hogy a 6. megtelt. Nem tudunk Lisa 6. Szóval, ha nem megyünk? Menjünk 7. 7-es üres, hogy működik. Tehát mondjuk Lisa ott. 

Most hash Homer és kapunk 7. OK jól tudjuk, hogy a 7-es teljes most, így nem tudunk tenni Homer ott. Szóval menjünk 8. 8 rendelkezésre? Ja, és a 8-as közel 7, így ha meg kell keresni kezdi vagyunk nem megy, hogy túl messzire megy. És így tegyük Homer 8. 

Most hash Maggie és vissza 3, hála az égnek képesek vagyunk csak fel Maggie ott. Nem kell, hogy nem minden egyfajta tapintási erre. Most hash Marge, és Marge is visszaadja 6. 

Nos 6 megtelt, 7 tele van, 8 tele van, 9, rendben hála Istennek, 9 üres. Én nem tud Marge 9. Már látjuk, hogy kezdünk hogy ez a probléma, ahol most vagyunk kezd nyúlik dolgokat természetbeni A távol a hash kódok. És, hogy theta 1, hogy az átlagos esetében pedig állandó idő, már kezd egy kicsit more-- kiindulva, hogy inkább egy kicsit felé theta n. Elkezdjük elveszíteni Használja ki hash táblák. 

Ez a probléma, hogy most láttam egy úgynevezett klaszterek kialakulását. És ami igazán rosszul csoportosítás az, hogy ha egyszer már Van két elemeket, amelyek egymás másikra ez teszi még inkább, Van dupla esélye, hogy fogsz hogy még egy ütközés azzal a klaszter, és a klaszter fog nőni az egyik. És akkor folyamatosan növekvő és egyre Ön valószínűsége annak ütközés. És végül ez ugyanolyan rossz ne válogatás az adatok egyáltalán. 

A másik probléma mégis az, hogy mi Mégis, és eddig a pontig, most voltunk valami megértése, hogy mi a hash tábla, még mindig csak van hely a 10 szálakat. Ha azt akarjuk, hogy továbbra is a hash polgárai Springfield, csak akkor tudjuk, hogy 10 oket oda. És ha megpróbáljuk, és adjunk hozzá egy 11. vagy 12., nincs olyan hely, hogy őket. Így egyszerűen forog körbe- körökben próbál találni egy üres helyre, és mi talán elakad végtelen ciklusba. 

Tehát ez a fajta kölcsönöz az ötlet Az úgynevezett láncolt. És ez az, hogy hová megyünk, hogy láncolt listák vissza a képet. Mi van, ha tárolása helyett csak az adatok is a tömbben, minden eleme a tömb lehetett tartsa több darab adatokat? Nos, hogy nincs értelme, nem igaz? Tudjuk, hogy egy tömb csak hold-- minden eleme egy tömb csak tartani egy darabban Az adatok ugyanilyen típusra. 

De mi van, ha ugyanilyen típusra egy láncolt lista, ugye? Szóval mi van, ha minden elem a tömb volt egy mutatót a fejét egy láncolt lista? És akkor tudnánk építeni azok láncolt listák és növekedni őket önkényesen, mert láncolt listák lehetővé teszik számunkra, hogy nő, és összezsugorodik sokkal több rugalmasan, mint egy tömb nem. Szóval mi van, ha most használni, Kihasználva ezt, ugye? Mi növekedni kezdenek ezek a láncok ezek közül tömb helyeken. 

Most elfér egy végtelen adatok mennyisége, vagy nem végtelen, tetszőleges mennyiségű adatok, a mi hash tábla anélkül, hogy valaha fut be A probléma az ütközés. Már azt is megszűnt csoportosítás ezt. És jól tudjuk, hogy ha betesszük egy láncolt lista, ha visszaemlékeztek a mi videót láncolt listák, önmagukban kapcsolt listák és kétszeresen láncolt listák, ez egy folyamatos működést. Mi csak hozzá a frontra. 

És felnéz, jól tudjuk, hogy felnéz egy láncolt lista lehet probléma, ugye? Meg kell keresni ez az elejétől a végéig. Nincs véletlen hozzáférést egy láncolt lista. De ha ahelyett, hogy mindegyik kapcsolódik lista, ahol egy keresési lenne O n, Most már 10 láncolt listák, vagy 1000 láncolt listák, most ez O n osztva 10, vagy O n osztva 1000. 

És miközben beszélgettünk elméletileg mintegy összetettsége eltekintünk állandók, az igazi világban ezek a dolgok valóban számít, ugye? Igazából észre fogja venni hogy ez történik futni 10-szer gyorsabb, vagy 1000-szer gyorsabb, mert mi terjesztése egy hosszú lánc-szerte 1000 kisebb láncok. És így minden alkalommal meg kell keresni révén az egyik ilyen láncok tudjuk figyelmen kívül hagyják a 999 lánc nem érdekel szól, és csak a keresési hogy az egyik. 

Ami átlagosan a legyen 1000-szer rövidebb. És így még mindig van valami hajló ez az átlag esetben lét állandó idő, de Csak azért, mert Kihasználjuk elosztjuk néhány hatalmas állandó tényező. Lássuk, hogyan lehet ezt valójában meg mégis. Szóval ez volt a hash tábla volt mielőtt nyilvánították hash tábla volt képes tárolni 10 szálakat. Nem fogunk tenni, hogy többé. Azt már tudjuk, korlátait, hogy módszer. Most a hash tábla lesz egy sor 10 csomópontok, pointerek a feje láncolt listák. 

És most ez null. Minden egyes ilyen 10 mutató null. Nincs semmi a mi hasítótábla most. 

Most kezdjük, hogy egy kis dolgok ebbe hash tábla. És nézzük meg, hogyan ez a módszer fog részesülni nekünk egy kicsit. Nézzük most hash Joey. Majd fog futni a húr Joey keresztül a hash függvény, és visszatérünk 6. Nos, mit tegyünk most? 

Hát most dolgozik láncolt listák, már nem dolgozunk együtt tömbök. És amikor dolgozunk A láncolt listák vagyunk tudom, el kell kezdenünk dinamikusan foglalt hely és az építési láncok. Ez a fajta how-- ezek a mag elemei épület egy láncolt lista. Úgyhogy dinamikusan osztja helyet Joey, majd tegyük hozzá, hogy a lánc. 

Szóval most nézd, mit tettünk. Amikor hash Joey megkaptuk az hashcode 6. Most a mutató a tömb helyen 6 rámutat, hogy a feje egy láncolt lista, és most ez az egyetlen eleme egy láncolt lista. És a csomópont, hogy láncolt lista Joey. 

Tehát, ha szükségünk van, hogy néz ki Joey Később, mi csak hash Joey újra, jutunk ismét a 6, mert a hash függvény determinisztikus. És akkor kezdjük élén A láncolt lista rámutatott hogy a tömb helyét 6, és mehetünk szerte, hogy megpróbálja megtalálni Joey. És ha építünk hash tábla hatékony, és mi hash hatékonyan működnek terjeszteni adatok is, átlagosan minden egyes ilyen kapcsolódik listák minden tömb helyét lesz 1/10 a méret, ha Csak volt, mint egy egyetlen hatalmas kapcsolt lista minden benne van. 

Ha terjeszteni, hogy hatalmas összefüggő lista fölött 10 láncolt listák Minden lista lesz 1/10 méretét. És így 10-szer gyorsabb keresgélni. Úgyhogy ezt újra. Nézzük most hash Ross. 

És mondjuk Ross, amikor ezt tesszük A hash kódot kapunk vissza 2. Hát most már dinamikusan hozzárendel egy Új csomópont tesszük Ross abban csomópont, és azt mondjuk most tömb helyét 2, ahelyett, rámutatva, hogy null, rámutat, hogy a feje egy kapcsolt listán, akiknek egyetlen csomópont Ross. És ezt meg tudjuk tenni még egyszer, mi lehet hash Rachel és kap hashcode 4. malloc egy új csomópont, tedd Rachel A csomópont, és mondjuk egy tömb helyét 4. utal most már a fejét Egy hivatkozott lista, amelynek egyetlen elem előfordul, hogy Rachel. 

OK, de mi történik, ha van egy ütközés? Lássuk, hogyan kezeljük ütközések az önálló láncolás módszer. Nézzük hash Phoebe. Kapunk a hashcode 6. Korábbi például voltunk, csak tárolja a húrok a tömbben. Ez volt a probléma. 

Nem akarunk a cucc Joey, és mi már Látható, hogy mi tud kap valamiféle csoportosulás problémákat, ha megpróbálunk lépést keresztül és a szonda. De mi van, ha csak ilyen kezeli ezt ugyanúgy, ugye? Olyan ez, mint egy elem hozzáadásával hogy a feje egy láncolt lista. Nézzük csak malloc helyet Phoebe. 

Majd azt mondjuk, Phoebe következő mutató a régi vezetője a láncolt lista, majd 6 csak arra utal, hogy a új vezetője a láncolt lista. És most nézd, mi már megváltozott Phoebe in. Most már tárolni két elemek hashcode 6, és nincs semmilyen probléma. 

Ez elég sok minden van, hogy láncolás. És láncolatok határozottan A módszer ez lesz a leghatékonyabb az Ön számára, ha akkor tárolja az adatokat egy hash tábla. De ez a kombináció tömbök és láncolt listák együtt alkotnak egy hash tábla igazán drámaian javítja a képességét, tárolni nagy mennyiségű adatot, és Nagyon gyorsan és hatékonyan keresni révén, hogy az adatok. 

Van még egy további adatstruktúra odakinn hogy talán még egy kicsit Jobb a biztosító hogy a mi inszerció, deléció, és felnéz alkalommal még gyorsabbak. És majd meglátjuk, hogy egy videót próbál. Én Doug Lloyd, ez CS50.