[Přehrávání hudby] DOUG LLOYD: Do teď jste vědí hodně o pole, a víte, že hodně o spojových seznamů. A máme diskutovat klady a zápory, které jsme diskutovali, který spojoval seznamy Můžete získat větší a menší, ale zabírají větší velikost. Pole jsou mnohem jednodušší na použití, ale oni jsou restriktivní v té míře, jak musíme nastavit velikost pole na samém začátku a pak jsme s tím nenadělají. Ale to je, máme docela hodně vyčerpal všechny naše témat o propojených seznamů a polí. Nebo máme? Možná, že můžeme něco udělat ještě více kreativní. A to druh, půjčuje myšlenka na hash tabulky. Takže v tabulce hash budeme se snažit kombinují pole se seznamem Google. Budeme mít výhody matice, stejně jako náhodný přístup, budou moci jen jít do pole element 4 nebo prvek pole 8 aniž by museli přecházet přes. To je dost rychle, ne? Ale také chceme mít naše data struktura moci růst a zmenšit. Nepotřebujeme, my ne chtějí být omezeno. A my chceme být schopni přidávat a odebírat věci velmi snadno, které, pokud si vzpomínáte, je velmi složitá s řadou. A můžeme volat toto Novinkou hash tabulky. A pokud by byla provedena správně, my jsme nějak převzetí výhod obou údajů struktury, které jste již viděli, pole a spojové seznamy. Vkládání může začít inklinovat k theta z 1. Theta jsme se opravdu diskutováno, ale theta je jen průměrný případ, co se vlastně bude dít. Nejste vždycky mají nejhorší možný scénář, a vy ne vždy bude mít nejlepší scénář, takže to, co je průměrný scénář? No průměrná vložení do hash tabulky Můžete začít se dostat blízko k konstantním čase. A mazání může dostat blízko k konstantním čase. A vyhledávání může dostat blízko k konstantním čase. That's-- nemáme data: struktura přesto, že může dělat to, a tak to už zní jako docela velkou věc. My jsme opravdu mírní nevýhody každého z nich na jeho vlastní. Chcete-li získat toto představení upgradovat i když jsme je třeba promyslet, jak přidáme dat do konstrukce. Konkrétně chceme, Data sama o sobě, aby nám řekli pokud by mělo jít ve struktuře. A když jsme pak je třeba zjistit, jestli je to ve struktura, pokud budeme potřebovat, aby ji najít, Chceme se podívat na data, Znovu a musí být schopen efektivně, použití dat, náhodně přístup. Jen tím, že při pohledu na Údaje bychom měli mít nápad, kde přesně jsme bude najít v tabulce hash. Nyní Nevýhodou hash Tabulka je, že jsou opravdu dost špatné na objednávce nebo při řazení dat. A ve skutečnosti, když začnete použít jim nařídit nebo třídění Data ztratíte všechny Výhody, které jste předtím měl, pokud jde o vkládání a mazání. Čas se stává blíž theta n, a my jsme v podstatě ustoupila do propojeného seznamu. A tak jsme se jen chcete použít hash stoly, kdybychom se nestarají o zda se data budou seřazeny. Pro kontextu, v němž budete používat je v CS50 pravděpodobně nezajímá že data jsou řazeny. Takže hash tabulka je kombinací ze dvou odlišných kusů s nimiž jsme obeznámeni. Prvním z nich je funkce, která obvykle nazýváme hash funkce. A to hash funkce se chystá vrátit nějaké nezáporné celé číslo, které obvykle zavolat hodnotu hash, OK? Druhá část je pole, což je schopný ukládání dat typu my umístit do datové struktury. Budeme odložit na spojový seznam prvku teď a jen začít se základy hash tabulky, aby si hlavu kolem něj, a pak budeme možná foukat vaše mysl trochu, když jsme kombinují pole a propojení seznamů dohromady. Základní myšlenka ačkoli je bereme některá data. Provozujeme data prostřednictvím funkce hash. A tak se data zpracována a to vyplivne číslo, OK? A pak se s tímto číslem my jen ukládání dat chceme uložit do Pole na tomto místě. Tak například máme možná Tento hash tabulky řetězců. Je tu 10 prvků v něm, tak můžeme vejde 10 řetězce v něm. Řekněme, že chceme, aby hash Johna. Tak jako Jan dat chceme vložit Do této tabulky hash někde. Kam dát? No typicky S array zatím jsme asi by se dát do lokalitě pole 0. Ale teď máme tuto novou funkci hash. A řekněme, že běžíme Johna Pomocí této funkce hash a to vyplivne 4. No, to je místo, kde jsme bude chtít dát Johna. Chceme dát Johnovi v místě pole 4, protože pokud bychom hash Johna again-- řekněme, že později jsme chcete vyhledat a zobrazit pokud John existuje v tomto hash table-- vše, co potřebujete udělat, je provozován přes stejné hash funkce, dostanete číslo 4 out, a musí být schopen najít John ihned v naší datové struktuře. To je docela dobrý. Řekněme, že teď to udělat Znovu chceme hash Paul. Chceme přidat Paul Do této tabulky hash. Řekněme, že jsme tentokrát spuštění Paul pomocí funkce hash, hashCode, který je generován je 6. No teď můžeme dát Paul v místě pole 6. A pokud budeme muset podívat do zda Paul je v této tabulce hash, vše, co potřebujeme udělat, je spustit Paul pomocí hash funkce znovu a budeme se dostat 6 zase ven. A pak jsme se jen podívat v místě pole 6. Je tam Paul? Pokud ano, je to v tabulce hash. Není Paul ne? On není v tabulce hash. Je to docela jednoduché. Nyní, jak si definovat hash funkce? No tam je opravdu žádný limit na počet možných funkcí hash. Ve skutečnosti existuje celá řada opravdu, Opravdu dobří na internetu. K dispozici je celá řada opravdu, Opravdu špatné ty na internetu. Je to také docela snadné napsat špatný jeden. Takže to, co tvoří dobrý hash funkce, že jo? No dobrá hashovací funkce by použít pouze se hashed data, a všechna data jsou hash. Takže nechceme používat anything-- nemáme nic začlenit jiný než data. A chceme používat všechna data. Nechceme, aby stačí použít kus z toho, chceme použít všechno. Funkce hash by měl být také deterministické. Co to znamená? No to znamená, že pokaždé, když projít přesně stejný kus dat do funkce hash vždy získat stejný hodnotu hash ven. Kdybych projít Johna do hash funkce se dostanu ven 4. Měl bych být schopen to udělat 10.000 časy a já budu vždy 4. Takže žádné náhodná čísla účinně se mohou zapojit do naší hash tables-- v našich hašovacích funkcích. Funkce hash by také rovnoměrně distribuci dat. Pokud by každý spuštění dat prostřednictvím hash funkce dostanete hodnotu hash 0, že to asi není tak velký, že jo? Pravděpodobně budete chtít, aby velký řada hash kódů. Také věci mohou být rozloženy v průběhu celého stolu. A také, že by bylo skvělé, kdyby opravdu podobné údaje, jako jsou John a Jonathan, Možná byly rozprostřeny vážit různá umístění v tabulce hash. To by bylo hezký výhoda. Zde je příklad funkce hash. Napsal jsem tenhle přivstat. Není to zvlášť dobrá funkce hash z důvodů, které nemají ve skutečnosti medvěd jít do teď. Ale vidíte, co se tu děje? Vypadá to, že jsme deklarování proměnné volal součet a nastavení rovno 0. A pak prý dělám něco tak dlouho, jak strstr [j] není rovno na zpětná lomítka 0. Co já jsem tam dělal? To je v podstatě jen další způsob provádění [? strl?] a detekci, když jsem dostal na konec řetězce. Takže nemám skutečně vypočítat délku řetězce, Já jsem jen pomocí, když jsem hit zpětné lomítko 0 postava vím Já jsem došel na konec řetězce. A pak budu držet iterace tohoto řetězce, přidávání strstr [j] sečíst, a pak na konci dne vracet částky mod HASH_MAX. V podstatě vše hash Funkce je dělá, je sčítání všechny hodnoty ASCII můj řetězec, a pak je to navracení hodnotu hash modded by HASH_MAX. Je to asi o velikosti mé pole, ne? Nechci se dostat hash kódy, pokud jsou moje pole je velikosti 10, Nechci být získání out hash kódy 11, 12, 13, nemohu dát věci do Tato místa z pole, že by bylo nezákonné. Já bych trpět chybu segmentace. Nyní je zde další rychlý stranou. Obecně budete pravděpodobně nebude Chcete napsat vlastní hash funkce. Je to vlastně trochu umění, není věda. A je tu hodně, že jde do nich. Internet, jak jsem řekl, je plný opravdu dobrých hašovacích funkcí, a vy byste měli používat internet k najít hash funkce, protože je to opravdu jen tak zbytečným ztráta času vytvořit si vlastní. Můžete napsat ty jednoduché pro účely testování. Ale když jste vlastně se chystáte spustit zatřiďování data a ukládá je do hash tabulky, kterou jste pravděpodobně bude chtít použít nějakou funkci, která byla generována pro tebe, který existuje na internetu. Pokud si prostě být jisti, citovat své zdroje. Neexistuje žádný důvod, aby napodobit něco tady. Počítač vědy komunita je rozhodně roste, a opravdu hodnoty open source, a je to opravdu důležité, citovat své zdroje tak, aby lidé mohou získat autorství dílo, které jsou dělá ve prospěch komunity. Takže vždy sure-- a to nejen pro hash funkce, ale obecně, když vás použít kód z vnějšího zdroje, vždy uveďte svůj zdroj. Dát úvěr na osoby, která ji některé práce, takže si nemusíte. OK, takže pojďme to znovu hash tabulky na vteřinu. To je místo, kde jsme opustili off poté, co jsme vkládají John a Paul do tohoto hash tabulky. Vidíte tu problém? Můžete vidět dva. Ale zejména, že ne viz tento možný problém? Co když hash Ringo, a to Ukazuje se, že po zpracování že údaje prostřednictvím funkce hash Ringo také generovány na hodnotu hash 6. Už mám data hashcode-- umístění pole 6. Takže to asi bude trochu problému teď pro mě, že jo? Říkáme tomu kolize. A dochází ke kolizi, když dva objemy dat, procházejí stejným datovým funkce dávají stejnou hodnotu hash. Pravděpodobně stále chceme získat oba kusy dat do tabulky hash, jinak bychom být spuštěn Ringo libovolně pomocí hash funkce. Pravděpodobně Chceme se dostat Ringo do tohoto pole. Jak to děláme i když, kdyby se a Paul oba výnos hashCode 6? Nechceme, aby přepsat Paula, Chceme Paul, aby se tam taky. Proto musíme najít způsob, jak dostat prvky do tabulky hash, který stále zachovává rychlém vkládání a rychlý pohled vzhůru. A jeden způsob, jak se s tím vypořádat, je dělat něco, co nazývá lineární sondování. Pomocí této metody, pokud máme kolize, no, co budeme dělat? No nemůžeme ho v místě pole 6, nebo cokoliv hashCode byl vytvořen, pojďme ho na hashCode plus 1. A pokud to plná pojďme dal ho do hashCode plus 2. Výhodou této bytosti, pokud je to Není přesně tam, kde si myslíme, že je, a my musíme začít hledat, Možná nemusíme jít příliš daleko. Možná, že nemáme hledat všechny n prvky tabulky hash. Možná, že budeme muset hledat několik z nich. A tak jsme stále vedou k že průměrný případ je blízko k 1 vs v blízkosti n, takže možná to bude fungovat. Takže pojďme se podívat, jak to by mohlo fungovat v praxi. A uvidíme, jestli bychom možná dokáže detekovat problém, že zde může dojít. Řekněme, že jsme hashovat Barta. Takže teď budeme provozovat nový soubor řetězců přes hash funkce, a my běh Barta přes hash funkce, dostaneme hodnotu hash 6. Jsme se podívat, vidíme, 6 prázdné, takže můžeme dát tam Barta. Nyní jsme hash Lisu a že také generuje hodnotu hash 6. Tak teď, když jsme pomocí tohoto lineární sondování metodu začneme 6, vidíme, že 6 je plná. Nemůžeme dát Lisu v 6. Tak kam půjdeme? Pojďme až 7. 7 je prázdná, tak to funguje. Takže pojďme dát Lisa tam. Nyní jsme hash Homera a dostaneme 7. OK dobře víme, že 7 je plný Nyní, takže nemůžeme dát tam Homer. Tak pojďme na 8. Je k dispozici 8? Jo, v blízkosti 8 k 7, takže pokud musíme začít hledat jsme nebude muset jít příliš daleko. A tak se pojďme dát Homerovi v 8. Nyní jsme hash Maggie a 3 se vrací, díky bohu jsme schopni jen dát Maggie tam. Nemusíme dělat jakýkoli druh sondování za to. Teď jsme hash Marge, a Marge také vrací 6. No 6 je plná, 7 je plná, 8 je plná, 9, v pořádku díky Bohu, 9 je prázdný. Můžu dát Marge na 9. Už můžeme vidět, že my teď začínáme aby tento problém, kde teď jsme začíná natáhnout věci druh daleko od svých hash kódy. A to theta 1, že průměrný Případ je konstantní čas, začíná být trochu more-- začíná o něco větší tendenci směrem k theta n. Začínáme ztrácet, že Výhodou stoly mřížky. Tento problém, který jsme právě viděli je něco, co nazývá shlukování. A co je opravdu špatného na tom, clustering je, že jakmile vás teď mají dva prvky, které jsou vedle stranu to dělá to ještě pravděpodobnější, Máte dvojnásobek šance, že budete mít další kolize clusteru s tím, a cluster poroste o jedno. A budete neustále rostou a roste Váš pravděpodobnost mít kolizi. A nakonec je to stejně špatné tak, že třídění dat vůbec. Dalším problémem však je, že jsme stále, a tak daleko, až do tohoto bodu, právě jsme byli tak nějak pochopení toho, co hash tabulka je, máme stále jen prostor pro 10 řetězců. Pokud chceme, aby i nadále hash občané Springfieldu, můžeme jen získat 10 z nich tam. A když se budeme snažit a přidejte 11. nebo 12., nemáme místo, aby je dal. Mohli bychom se točí kolem kruhy se snaží najít prázdné místo, a my jsme možná uvíznou v nekonečné smyčce. Takže tento druh půjčuje myšlenku něco volal řetězení. A to je místo, kde budeme přinášet spojové seznamy zpět do obrazu. Co když místo uložení právě samotná data v poli, každý prvek matice mohla držet více částí dat? No, to nedává smysl, že jo? Víme jen to, že pole může hold-- každého prvku pole může mít pouze jeden kus údajů tohoto typu dat. Ale co když ten typ dat je propojený seznam, ne? Takže co kdyby každý prvek pole byla ukazatel na hlavě propojeného seznamu? A pak bychom mohli stavět ty spojové seznamy a růst je libovolně, proto, že spojové seznamy umožňují náš růst a zmenšit mnohem více pružněji než pole dělá. A co když budeme nyní používat, jsme využít to, že jo? Máme začít pěstovat tyto řetězy z těchto míst pole. Nyní jsme se vejde nekonečným množství dat, nebo není nekonečná, libovolná částka Údaje, do našeho hash tabulky aniž by se běh do problém kolize. Také jsme eliminovat shlukování tím, že dělá to. A dobře víme, že když jsme se vložit do propojeného seznamu, pokud si vzpomínáte z našeho videa na provázané seznamy, jednotlivě propojené seznamy a dvojnásobně spojové seznamy, je to neustálý doba provozu. Jsme jen přidat na frontu. A Look Up, dobře víme, které vypadají v propojeném seznamu může být problém, že jo? Musíme prohledávat je od začátku až do konce. Není náhodné připojení k internetu v Google seznamu. Avšak v případě, místo toho, aby se jeden z propojených Seznam kde by vyhledávání být O n, nyní máme 10 provázané seznamy, nebo 1000 propojené seznamy, teď je to ó n děleno 10, nebo O n děleno 1,000. A když jsme mluvili teoreticky o složitosti Pomineme konstanty, v skutečný svět tyto věci skutečně záleží, v pořádku? Vlastně jsme si všimnete , že se to stane běžet 10 krát rychleji, nebo 1000 krát rychlejší, proto, že jsme rozdělení jedné dlouhé řetěz přes 1000 menších řetězcích. A tak pokaždé, když se musíme hledat prostřednictvím jednoho z těchto řetězců je v našich silách ignorovat 999 řetězců nás nezajímá o, a jen hledat, že jeden. Což je v průměru být 1000x kratší. A tak jsme pořád jsou tak nějak směřující k tomuto průměrný případ z toho, že konstantním čase, ale jen proto, že jsme se pákového efektu dělení nějakým velkým konstantním faktorem. Podívejme se, jak by to mohlo ve skutečnosti vypadají ačkoli. Tak tohle byla tabulka hash jsme měli Než jsme deklarovali hash tabulku, která byl schopen ukládat 10 řetězců. Nebudeme dělat, že už ne. My už víme, že Omezení této metody. Nyní náš hash tabulky to bude řada 10 uzlů, ukazatele vedoucím spojových seznamů. A právě teď je to null. Každý z těch 10 ukazatelů je null. Na tom není nic v Our hash tabulky právě teď. Nyní pojďme začít, aby některé věci do tohoto hash tabulky. A podívejme se, jak je tato metoda bude nám prospěch trochu. Pojďme se teď hashovat Joey. Budeme se spustí řetězec Joey prostřednictvím funkce hash a vracíme se 6. Tak co budeme dělat teď? Tak nyní pracuje s propojenými seznamy, nejsme práci s poli. A když pracujeme s propojenými seznamy my víte, musíme začít dynamicky přidělování prostoru a stavební řetězy. To je druh how-- ty jsou jádrem prvky budování propojeného seznamu. Takže pojďme dynamicky přidělit prostor pro Joey, a pak dodejme ho řetězu. Takže teď se podívejte, co jsme udělali. Když jsme hash Joey jsme dostali hodnotu hash 6. Nyní je ukazatel v místě pole 6 poukazuje na čele seznamu Google, a teď je to jediná prvek propojeného seznamu. A uzel se tím, že spojový seznam je Joey. Takže pokud budeme muset podívat do Joey později, právě jsme hash Joey znovu, dostaneme 6 znovu, protože naše hash funkce je deterministický. A pak začneme v čele propojeného seznamu poukázal se podle umístění pole 6, a můžeme iteraci přes který se snaží najít Joey. A pokud budeme budovat naši účinně hash tabulky, a naše hash funkce efektivně distribuovat dat dobře, v průměru každá z těch, které souvisejí seznamy na každém místě pole bude 1/10 velikost kdybychom prostě musel to jak jeden obrovský spojový seznam se vším, co v něm. Pokud budeme distribuovat, že obrovské spojené Seznam přes 10 spojových seznamů každý seznam bude desetin velikost. A tedy 10 krát rychlejší prohledávat. Takže pojďme to udělat znovu. Pojďme se teď hashovat Ross. A řekněme, že Ross, když budeme dělat, že hash kód se vrátíme je 2. Tak teď jsme dynamicky přidělit nový uzel, dáme Ross v tomto uzlu, a říkáme, nyní umístění array 2, místo toho, směřující na null, poukazuje na hlavu spojené Seznam jejichž jediným uzel je Ross. A můžeme to udělat ještě jeden čas, my mohou hash Rachel a získat hodnotu hash 4. malloc nový uzel, dal Rachel v uzel, a říkají, umístění pole 4 nyní ukazuje na hlavě propojeného seznamu, jehož Jediným prvkem se stane být Rachel. OK, ale co se stane, když máme kolizi? Podívejme se, jak nakládáme s kolizí pomocí samostatného metody zřetězení. Pojďme hash Phoebe. Dostaneme hodnotu hash 6. V našem předchozím příkladu jsme byli jen uložení řetězců v poli. To byl problém. Nechceme, aby nandat Joey, a už jsme vidět, že můžeme získat nějaké clustering problémy, pokud se snažíme krok až do konce a sonda. Ale co když jsme právě druh zacházet to stejně, ne? Je to jako přidání prvku na hlavu propojeného seznamu. Pojďme se jen malloc prostor pro Phoebe. Řekneme další ukazatele bodů Phoebe na staré hlavě Google seznamu, a poté na 6 jen poukazuje na nový šéf Google seznamu. A teď se podívej, že jsme změnili Phoebe v. Nyní můžeme uložit dva prvky s hashCode 6, a my nemáme žádné problémy. To je skoro všechny tam je řetězení. A řetězení je určitě Metoda, která je bude nejefektivnější pro vás, pokud jste ukládání dat do tabulky hash. Ale tato kombinace pole a spojové seznamy spolu tvořit hash tabulku opravdu výrazně zlepšuje vaši schopnost pro ukládání velkých objemů dat, a velmi rychle a efektivně vyhledávat prostřednictvím tohoto data. Je tu ještě jeden struktura tam údaje to by mohlo být i trochu lepší, pokud jde o zajištění že naše vkládání, mazání, a Vyhledá časy jsou ještě rychlejší. A uvidíme, že ve videu na pokusech. Jsem Doug Lloyd, je to CS50.