[Prehrávanie hudby] DOUG LLOYD: Do teraz ste vedia veľa o pole, a viete, že veľa o spojových zoznamov. A máme diskutovať klady a zápory, ktoré sme diskutovali, ktorý spájal zoznamy Môžete získať väčšie a menšie, ale zaberajú väčšiu veľkosť. Polia sú oveľa jednoduchšie na použitie, ale oni sú reštriktívne v tej miere, ako musíme nastaviť veľkosť polia na samom začiatku a potom sme s tým nenarobia. 

Ale to je, máme celkom veľa vyčerpal všetky naše tém o prepojených zoznamov a polí. Alebo máme? Možno, že môžeme niečo urobiť ešte viac kreatívne. A to druh, požičiava myšlienka na hash tabuľky. 

Takže v tabuľke hash budeme sa snažiť kombinujú pole so zoznamom Google. Budeme mať výhody matice, rovnako ako náhodný prístup, budú môcť len ísť do poľa element 4 alebo prvok poľa 8 bez toho aby museli prechádzať cez. To je dosť rýchlo, nie? 

Ale tiež chceme mať naše dáta štruktúra moci rast a zmenšiť. Nepotrebujeme, my nie chcú byť obmedzené. A my chceme byť schopní pridávať a odoberať veci veľmi ľahko, ktoré, ak si spomínate, je veľmi zložitá s radom. A môžeme volať toto Novinkou hash tabuľky. 

A ak by bola vykonaná správne, my sme nejako prevzatia výhod oboch údajov štruktúry, ktoré ste už videli, poľa a spojové zoznamy. Vkladanie môže začať inklinovať k theta z 1. Theta sme sa naozaj diskutuje, ale theta je len priemerný prípad, čo sa vlastne bude diať. Nie ste vždycky majú najhorší možný scenár, a vy nie vždy bude mať najlepší scenár, takže to, čo je priemerný scenár? 

No priemerná vloženie do hash tabuľky Môžete začať sa dostať blízko k konštantnom čase. A mazanie môže dostať blízko k konštantnom čase. A vyhľadávanie môže dostať blízko k konštantnom čase. That's-- nemáme dáta: štruktúra napriek tomu, že môže robiť to, a tak to už znie ako celkom veľkú vec. My sme naozaj mierni nevýhody každého z nich na jeho vlastné. 

Ak chcete získať toto predstavenie upgradovať aj keď sme je potrebné premyslieť, ako pridáme dát do konštrukcie. Konkrétne chceme, Dáta sama o sebe, aby nám povedali ak by malo ísť v štruktúre. A keď sme potom je potrebné zistiť, či je to vo štruktúra, ak budeme potrebovať, aby ju nájsť, Chceme sa pozrieť na dáta, Znovu a musí byť schopný efektívne, použitia dát, náhodne prístup. Len tým, že pri pohľade na Údaje by sme mali mať nápad, kde presne sme bude nájsť v tabuľke hash. 

Teraz Nevýhodou hash Tabuľka je, že sú naozaj dosť zlé na objednávke alebo pri radení dát. A v skutočnosti, keď začnete použiť im nariadiť alebo triedenie Dáta stratíte všetky Výhody, ktoré ste predtým mal, pokiaľ ide o vkladanie a mazanie. Čas sa stáva bližšie theta n, a my sme v podstate ustúpila do prepojeného zoznamu. A tak sme sa len chcete použiť hash stoly, keby sme sa nestarajú o či sa dáta budú zoradené. Pre kontextu, v ktorom budete používať ich v CS50 pravdepodobne nezaujíma že dáta sú radené. 

Takže hash tabuľka je kombináciou z dvoch odlišných kusov s ktorými sme oboznámení. Prvým z nich je funkcia, ktorá zvyčajne nazývame hash funkcie. A to hash funkcie sa chystá vrátiť nejaké nezáporné celé číslo, ktoré zvyčajne zavolať hodnotu hash, OK? Druhá časť je pole, čo je schopný ukladanie dát typu my umiestniť do dátovej štruktúry. Budeme odložiť na spájať zoznam prvku teraz a len začať so základmi hash tabuľky, aby si hlavu okolo neho, a potom budeme možno fúkať vaša myseľ trochu, keď sme kombinujú poľa a prepojenie zoznamov dohromady. 

Základná myšlienka hoci je berieme niektoré dáta. Prevádzkujeme dáta prostredníctvom funkcie hash. A tak sa dáta spracované a to vypľuje číslo, OK? A potom sa s týmto číslom my len ukladanie dát chceme uložiť do Poľa na tomto mieste. Tak napríklad máme možná Tento hash tabuľky reťazcov. Je tu 10 prvkov v ňom, tak môžeme vojde 10 reťazca v ňom. 

Povedzme, že chceme, aby hash Johna. Tak ako Ján dát chceme vložiť Do tejto tabuľky hash niekde. Kam dať? No typicky S array zatiaľ sme asi by sa dať do lokalite poľa 0. Ale teraz máme túto novú funkciu hash. 

A povedzme, že bežíme Johna Pomocou tejto funkcie hash a to vypľuje 4. No, to je miesto, kde sme bude chcieť dať Johna. Chceme dať Johnovi v mieste poľa 4, pretože ak by sme hash Johna again-- povedzme, že neskôr sme chcete vyhľadať a zobraziť ak John existuje v tomto hash table-- všetko, čo potrebujete urobiť, je prevádzkovaný cez rovnaké hash funkcie, dostanete číslo 4 out, a musí byť schopný nájsť John ihneď v našej dátovej štruktúre. To je celkom dobrý. 

Povedzme, že teraz to urobiť Znovu chceme hash Paul. Chceme pridať Paul Do tejto tabuľky hash. Povedzme, že sme tentoraz spustenie Paul pomocou funkcie hash, hashCode, ktorý je generovaný je 6. No teraz môžeme dať Paul v mieste poľa 6. A ak budeme musieť pozrieť do či Paul je v tejto tabuľke hash, všetko, čo potrebujeme urobiť, je spustiť Paul pomocou hash funkcie znova a budeme sa dostať 6 zase von. 

A potom sme sa len pozrieť v mieste poľa 6. Je tam Paul? Ak áno, je to v tabuľke hash. Nie je Paul nie? On nie je v tabuľke hash. Je to celkom jednoduché. 

Teraz, ako si definovať hash funkcie? No tam je naozaj žiadny limit na počet možných funkcií hash. V skutočnosti existuje celý rad naozaj, Naozaj dobrí na internete. K dispozícii je celý rad naozaj, Naozaj zlé tie na internete. Je to tiež celkom jednoduché napísať zlý jeden. 

Takže to, čo tvorí dobrý hash funkcie, že jo? No dobrá hashovacie funkcie by použiť iba sa Hashed dáta, a všetky dáta sú hash. Takže nechceme používať anything-- nemáme nič začleniť iný ako dáta. A chceme používať všetky dáta. Nechceme, aby stačí použiť kus z toho, chceme použiť všetko. Funkcia hash by mal byť tiež deterministické. Čo to znamená? No to znamená, že zakaždým, keď prejsť presne rovnaký kus dát do funkcie hash vždy získať rovnaký hodnotu hash von. Keby som prejsť Johna do hash funkcie sa dostanem von 4. Mal by som byť schopný to urobiť 10.000 časy a ja budem vždy 4. Takže žiadne náhodné čísla účinne sa môžu zapojiť do našej hash tables-- v našich hašovacej funkciách. 

Funkcia hash by tiež rovnomerne distribúciu dát. Ak by každý spusteniu údajov prostredníctvom hash funkcie dostanete hodnotu hash 0, že to asi nie je tak veľký, že jo? Pravdepodobne budete chcieť, aby veľký rad hash kódov. Tiež veci môžu byť rozložené v priebehu celého stola. A tiež, že by bolo skvelé, keby naozaj podobné údaje, ako sú John a Jonathan, Možno boli rozprestreté vážiť rôzne umiestnenia v tabuľke hash. To by bolo pekný výhoda. 

Tu je príklad funkcie hash. Napísal som tento privstať. Nie je to zvlášť dobrá funkcia hash z dôvodov, ktoré nemajú v skutočnosti medveď ísť do teraz. Ale vidíte, čo sa tu deje? Vyzerá to, že sme deklarovaní premennej volal súčet a nastavenie presne 0. A potom vraj robím niečo tak dlho, ako strstr [j] nerovná na spätné lomítka 0. Čo ja som tam robil? 

To je v podstate len ďalší spôsob vykonávania [? strl?] a detekciu, keď som dostal na koniec reťazca. Takže nemám skutočne vypočítať dĺžku reťazca, Ja som len pomocou, keď som hit spätné lomítko 0 postava viem Ja som došiel na koniec reťazca. A potom budem držať iterácie tohto reťazca, pridávanie strstr [j] sčítať, a potom na konci dňa vracať čiastky mod HASH_MAX. 

V podstate všetko hash Funkcia je robí, je sčítanie všetky hodnoty ASCII môj reťazec, a potom je to návratu hodnotu hash modded by HASH_MAX. Je to asi o veľkosti moje pole, nie? Nechcem sa dostať hash kódy, ak sú moje pole je veľkosti 10, Nechcem byť získanie out hash kódy 11, 12, 13, nemôžem dať veci do Tieto miesta z poľa, že by bolo nezákonné. Ja by som trpieť chybu segmentácie. 

Teraz je tu ďalší rýchly stranou. Všeobecne budete pravdepodobne nebude Chcete napísať vlastnú hash funkcie. Je to vlastne trochu umenia, nie je veda. A je tu veľa, že ide do nich. Internet, ako som povedal, je plný naozaj dobrých hašovacej funkcií, a vy by ste mali používať internet na nájsť hash funkcie, pretože je to naozaj len tak zbytočným strata času vytvoriť si vlastný. 

Môžete napísať tie jednoduché na účely testovania. Ale keď ste vlastne sa chystáte spustiť zatrieďovanie dáta a ukladá ich do hash tabuľky, ktorú ste pravdepodobne bude chcieť použiť nejakú funkciu, ktorá bola generovaná pre teba, ktorý existuje na internete. Ak si proste byť istí, citovať svoje zdroje. Neexistuje žiadny dôvod, aby napodobniť niečo tu. 

Počítač vedy komunita je rozhodne rastie, a naozaj hodnoty open source, a je to naozaj dôležité, citovať svoje zdroje tak, aby ľudia môžu získať autorstvo dielo, ktoré sú robí v prospech komunity. Takže vždy sure-- a to nielen pre hash funkcie, ale všeobecne, keď vás použiť kód z vonkajšieho zdroja, vždy uveďte svoj zdroj. Dať úver na osoby, ktorá ju niektoré práce, takže si nemusíte. 

OK, takže poďme to znova hash tabuľky na sekundu. To je miesto, kde sme opustili off potom, čo sme vkladajú John a Paul do tohto hash tabuľky. Vidíte tu problém? Môžete vidieť dva. Ale najmä, že nie pozri tento možný problém? 

Čo keď hash Ringo, a to Ukazuje sa, že po spracovaní že údaje prostredníctvom funkcie hash Ringo tiež generované na hodnotu hash 6. Už mám dáta hashcode-- umiestnenie poľa 6. Takže to asi bude trochu problému teraz pre mňa, že jo? 

Hovoríme tomu kolízie. A dochádza ku kolízii, keď dvaja objemy dát, prechádzajú rovnakým dátovým funkcie dávajú rovnakú hodnotu hash. Pravdepodobne stále chceme získať oba kusy dát do tabuľky hash, inak by sme byť spustený Ringo ľubovoľne pomocou hash funkcie. Pravdepodobne Chceme sa dostať Ringo do tohto poľa. 

Ako to robíme aj keď, keby sa a Paul obaja výnos hashCode 6? Nechceme, aby prepísať Paula, Chceme Paul, aby sa tam taky. Preto musíme nájsť spôsob, ako dostať prvky do tabuľky hash, ktorý stále zachováva rýchlom vkladanie a rýchly pohľad hore. A jeden spôsob, ako sa s tým vysporiadať, je robiť niečo, čo nazýva lineárny sondovania. 

Pomocou tejto metódy, ak máme kolízie, no, čo budeme robiť? No nemôžeme ho v mieste poľa 6, alebo čokoľvek hashCode bol vytvorený, poďme ho na hashCode plus 1. A ak to plná poďme dal ho do hashCode plus 2. Výhodou tejto bytosti, ak je to Nie je presne tam, kde si myslíme, že je, a my musíme začať hľadať, Možno nemusíme ísť príliš ďaleko. Možno, že nemáme hľadať všetky n prvky tabuľky hash. Možno, že budeme musieť hľadať niekoľko z nich. 

A tak sme stále vedú k že priemerný prípad je blízko k 1 vs v blízkosti n, takže možno to bude fungovať. Takže poďme sa pozrieť, ako to by mohlo fungovať v praxi. A uvidíme, či by sme možno dokáže detekovať problém, že tu môže dôjsť. 

Povedzme, že sme Hashovať Barta. Takže teraz budeme prevádzkovať nový súbor reťazcov cez hash funkcie, a my beh Barta cez hash funkcie, dostaneme hodnotu hash 6. Sme sa pozrieť, vidíme, 6 prázdne, takže môžeme dať tam Barta. 

Teraz sme hash Lisu a že tiež generuje hodnotu hash 6. Tak teraz, keď sme pomocou tohto lineárne sondovania metódu začneme 6, vidíme, že 6 je plná. Nemôžeme dať Lisu v 6. Tak kam pôjdeme? Poďme až 7. 7 je prázdna, tak to funguje. Takže poďme dať Lisa tam. 

Teraz sme hash Homera a dostaneme 7. OK dobre vieme, že 7 je plný Teraz, takže nemôžeme dať tam Homer. Tak poďme na 8. Je k dispozícii 8? Jo, v blízkosti 8 k 7, takže ak musíme začať hľadať sme nebude musieť ísť príliš ďaleko. A tak sa poďme dať Homerovi v 8. 

Teraz sme hash Maggie a 3 sa vracia, vďaka bohu sme schopní len dať Maggie tam. Nemusíme robiť akýkoľvek druh sondovania za to. Teraz sme hash Marge, a Marge tiež vracia 6. 

No 6 je plná, 7 je plná, 8 je plná, 9, v poriadku vďaka Bohu, 9 je prázdny. Môžem dať Marge na 9. Už môžeme vidieť, že my teraz začíname aby tento problém, kde teraz sme začína natiahnuť veci druh ďaleko od svojich hash kódy. A to theta 1, že priemerný Prípad je konštantný čas, začína byť trochu more-- začína o niečo väčšiu tendenciu smerom k theta n. Začíname strácať, že Výhodou stoly mriežky. 

Tento problém, ktorý sme práve videli je niečo, čo nazýva zhlukovaniu. A čo je naozaj zlé na tom, clustering je, že akonáhle vás teraz majú dva prvky, ktoré sú vedľa stranu to robí to ešte pravdepodobnejšie, Máte dvojnásobok šanca, že budete mať ďalšie kolízie klastra s tým, a cluster porastie o jedno. A budete neustále rastú a rastie Váš pravdepodobnosť mať kolízii. A nakoniec je to rovnako zlé tak, že triedenie dát vôbec. 

Ďalším problémom však je, že sme stále, a tak ďaleko, až do tohto bodu, práve sme boli tak nejako pochopenie toho, čo hash tabuľka je, máme stále len priestor pre 10 reťazcov. Ak chceme, aby aj naďalej hash občania Springfieldu, môžeme len získať 10 z nich tam. A keď sa budeme snažiť a pridajte 11. alebo 12., nemáme miesto, aby ich dal. Mohli by sme sa točí okolo kruhy sa snažia nájsť prázdne miesto, a my sme možno uviaznu v nekonečnej slučke. 

Takže tento druh požičiava myšlienku niečo volal reťazenie. A to je miesto, kde budeme prinášať spojové zoznamy späť do obrazu. Čo keď miesto uloženia práve samotné dáta v poli, každý prvok matice mohla držať viac častí dát? No, to nedáva zmysel, že jo? Vieme len to, že pole môže hold-- každého prvku poľa môže mať iba jeden kus údajov tohto typu dát. 

Ale čo keď ten typ dát je prepojený zoznam, nie? Takže čo keby každý prvok poľa bola ukazovateľ na hlave prepojeného zozname? A potom by sme mohli stavať tie spojové zoznamy a rast je ľubovoľne, preto, že spojové zoznamy umožňujú náš rast a zmenšiť oveľa viac pružnejšie než pole robí. A čo keď budeme teraz používať, sme využiť to, že jo? Máme začať pestovať tieto reťaze z týchto miest poľa. 

Teraz sme sa zmestí nekonečným množstvo dát, alebo nie je nekonečná, ľubovoľná čiastka Údaje, do nášho hash tabuľky bez toho aby sa beh do problém kolízie. Tiež sme eliminovať zhlukovaniu tým, že robí to. A dobre vieme, že keď sme sa vložiť do prepojeného zoznamu, ak si spomínate z nášho videa na previazané zoznamy, jednotlivo prepojené zoznamy a dvojnásobne spojové zoznamy, je to neustály doba prevádzky. Sme len pridať na front. 

A Look Up, dobre vieme, ktoré vyzerajú v prepojenom zozname môže byť problém, že jo? Musíme prehľadávať je od začiatku až do konca. Nie je náhodné pripojenie k internetu v Google zoznamu. Avšak v prípade, namiesto toho, aby sa jeden z prepojených Zoznam kde by vyhľadávania byť O n, teraz máme 10 previazané zoznamy, alebo 1000 prepojené zoznamy, teraz je to ó n delené 10, alebo O n delené 1,000. 

A keď sme hovorili teoreticky o zložitosti Opomenieme konštanty, v skutočný svet tieto veci skutočne záleží, v poriadku? Vlastne sme si všimnete , Že sa to stane bežať 10 krát rýchlejšie, alebo 1000 krát rýchlejší, preto, že sme rozdelenie jednej dlhej reťaz cez 1000 menších reťazcoch. A tak zakaždým, keď sa musíme hľadať prostredníctvom jedného z týchto reťazcov je v našich silách ignorovať 999 reťazcov nás nezaujíma o, a len hľadať, že jeden. 

Čo je v priemere byť 1000x kratšie. A tak sme stále sú tak nejako smerujúce k tomuto priemerný prípad z toho, že konštantnom čase, ale len preto, že sme sa pákového efektu delenie nejakým veľkým konštantným faktorom. Pozrime sa, ako by to mohlo v skutočnosti vyzerajú hoci. Tak toto bola tabuľka hash sme mali Ako sme deklarovali hash tabuľku, ktorá bol schopný ukladať 10 reťazcov. Nebudeme robiť, že už nie. My už vieme, že Obmedzenie tejto metódy. Teraz náš hash tabuľky to bude rad 10 uzlov, ukazovatele vedúcim spojových zoznamov. 

A práve teraz je to null. Každý z tých 10 ukazovateľov je null. Na tom nie je nič v Our hash tabuľky práve teraz. 

Teraz poďme začať, aby niektoré veci do tohto hash tabuľky. A pozrime sa, ako je táto metóda bude nám prospech trochu. Poďme sa teraz Hashovať Joey. Budeme sa spustí reťazec Joey prostredníctvom funkcie hash a vraciame sa 6. Tak čo budeme robiť teraz? 

Tak teraz pracuje s prepojenými zoznamy, nie sme prácu s poľami. A keď pracujeme s prepojenými zoznamy my viete, musíme začať dynamicky prideľovanie priestoru a stavebné reťaze. To je druh how-- tie sú jadrom prvky budovania prepojeného zoznamu. Takže poďme dynamicky prideliť priestor pre Joey, a potom dodajme ho reťaze. 

Takže teraz sa pozrite, čo sme urobili. Keď sme hash Joey sme dostali hodnotu hash 6. Teraz je ukazovateľ v mieste poľa 6 poukazuje na čele zoznamu Google, a teraz je to jediná prvok prepojeného zoznamu. A uzol sa tým, že spájať zoznam je Joey. 

Takže ak budeme musieť pozrieť do Joey neskôr, práve sme hash Joey znova, dostaneme 6 znova, pretože naša hash funkcia je deterministický. A potom začneme v čele prepojeného zoznamu poukázal sa podľa umiestnenia poľa 6, a môžeme iterácii cez ktorý sa snaží nájsť Joey. A ak budeme budovať našu účinne hash tabuľky, a naše hash funkcie efektívne distribuovať dát dobre, v priemere každá z tých, ktoré súvisia zoznamy na každom mieste pole bude 1/10 veľkosť keby sme jednoducho musel to ako jeden obrovský spájať zoznam so všetkým, čo v ňom. 

Ak budeme distribuovať, že obrovské spojené Zoznam cez 10 spojových zoznamov každý zoznam bude desatín veľkosť. A teda 10 krát rýchlejší prehľadávať. Takže poďme to urobiť znova. Poďme sa teraz Hashovať Ross. 

A povedzme, že Ross, keď budeme robiť, že hash kód sa vrátime je 2. Tak teraz sme dynamicky prideliť nový uzol, dáme Ross v tomto uzle, a hovoríme, teraz umiestnenie array 2, namiesto toho, smerujúce na null, poukazuje na hlavu spojené Zoznam ktorých jediným uzol je Ross. A môžeme to urobiť ešte jeden čas, my môžu hash Rachel a získať hodnotu hash 4. malloc nový uzol, dal Rachel v uzol, a hovoria, umiestnenie polia 4 teraz ukazuje na hlave prepojeného zozname, ktorého Jediným prvkom sa stane byť Rachel. 

OK, ale čo sa stane, keď máme kolízii? Pozrime sa, ako nakladáme s kolízií pomocou samostatného metódy zreťazenie. Poďme hash Phoebe. Dostaneme hodnotu hash 6. V našom predchádzajúcom príklade sme boli len uloženie reťazcov v poli. To bol problém. 

Nechceme, aby naložiť Joey, a už sme vidieť, že môžeme získať nejaké clustering problémy, ak sa snažíme krok až do konca a sonda. Ale čo keď sme práve druh zaobchádzať to rovnako, nie? Je to ako pridanie prvku na hlavu prepojeného zozname. Poďme sa len malloc priestor pre Phoebe. 

Povieme ďalšie ukazovatele bodov Phoebe na staré hlave Google zoznamu, a potom na 6 len poukazuje na nový šéf Google zoznamu. A teraz sa pozri, že sme zmenili Phoebe v. Teraz môžeme uložiť dva prvky s hashCode 6, a my nemáme žiadne problémy. 

To je skoro všetky tam je reťazenie. A reťazenie je určite Metóda, ktorá je bude najefektívnejší pre vás, ak ste ukladanie dát do tabuľky hash. Ale táto kombinácia poľa a spojové zoznamy spolu tvoriť hash tabuľku naozaj výrazne zlepšuje vašu schopnosť pre ukladanie veľkých objemov dát, a veľmi rýchlo a efektívne vyhľadávať prostredníctvom tohto dátumu. 

Je tu ešte jeden štruktúra tam údaje to by mohlo byť aj trochu lepšie, pokiaľ ide o zabezpečenie že naše vkladanie, mazanie, a Vyhľadá časy sú ešte rýchlejšie. A uvidíme, že vo videu na pokusoch. Som Doug Lloyd, je to CS50.