[Glazbom] Doug LLOYD: Do sada ste znam puno o polja, i znate puno o povezanim popisima. A mi smo razgovarali o prednosti i mane, da smo objašnjeno da povezane liste može dobiti veći i manji, ali oni zauzimaju više veličina. Nizovi su mnogo više neposredan koristiti, ali oni su restriktivni u koliko kao što smo postaviti veličinu Niz na samom početku a onda smo zapeli s njim. Ali to je, mi smo prilično mnogo iscrpljene sve naše teme o povezanim popisima i polja. Ili smo? Možda možemo nešto učiniti još kreativniji. I to vrsta posuđuje ideja hash tablici. Tako je u hash tablici ćemo pokušati kombinirati niz s popisa povezane. Idemo uzeti prednosti od polja, kao što slučajnim pristupom, biti u mogućnosti samo ići niz Element 4 ili niz elementa 8 bez ponoviti preko. To je prilično brzo, zar ne? Ali, mi također žele imati svoje podatke Struktura moći rasti i smanjivati. Mi ne trebamo, mi ne želim biti ograničen. A mi želimo biti u mogućnosti dodati i ukloniti stvari vrlo jednostavno, što ako se sjetiti, vrlo je složen s nizom. I možemo zvati Nova stvar hash tablicu. A ako se provodi ispravno, Mi smo vrsta uzimanja Prednosti i podatke Strukture koje ste već vidjeli, polja i povezane liste. Ubacivanje može početi skloni theta od 1. Theta nismo stvarno razgovarali, ali teta je samo prosječan slučaj, što se zapravo će se dogoditi. Nećeš uvijek će imaju najgori mogući scenarij, i niste uvijek će imati najboljem slučaju, tako što je prosječan scenarij? Pa u prosjeku za umetanje u hash tablici možete početi da se u neposrednoj blizini konstantnom vremenu. I brisanje može dobiti zatvoriti stalnom vrijeme. I pretraživanje može dobiti zatvoriti stalnom vrijeme. That's-- mi nemamo podatke Struktura gostiju koji može učiniti, i tako to već zvuči kao prilično velika stvar. Mi stvarno sam ublažila nedostaci svaki na svoju vlastitu. Da biste dobili ovaj nastup nadograditi ipak, mi potrebno promisliti kako ćemo dodati podataka u strukturi. Naime želimo Sama podaci nam reći gdje je trebao ići u strukturi. I ako onda treba vidjeti je li to u struktura, ako moramo pronaći, želimo pogledajte podataka opet moći učinkovito, korištenja podataka, slučajno mu pristupiti. Samo gledanjem na Podaci bi trebali imati ideja gdje točno smo će ga pronaći u hash tablici. Sada je downside skraćenog stol je da su oni zapravo prilično loše na naređivanje ili sortiranja podataka. A u stvari, ako počnete koristiti ih naručiti ili sortiranje Podaci izgubite sve od Prednosti ste prethodno imao u pogledu umetanja i brisanja. Vrijeme postaje bliži theta n, a mi smo zapravo regresiju u popisu povezane. I tako smo se samo želite koristiti hash tablice, ako mi ne stalo je li se podaci razvrstani. Za kontekst u kojem ćete ih koristiti u CS50 vjerojatno ne briga da se podaci razvrstani. Tako hash tablica kombinacija dva različita komada s kojima smo upoznati. Prva je funkcija, koje mi obično nazivamo hash funkcije. I to hash funkcija će vratiti neke ne-negativni cijeli broj, koji mi obično nazivamo Hash broj, u redu? Drugi dio je niz, što je sposoban za pohranu podataka tipa mi žele staviti u strukturu podataka. Mi ćemo odlagati na povezani s popisa elementa za sada i samo početi s Osnove hash tablicu dobiti svoju glavu oko njega, a onda ćemo možda odsvirati vaš um malo kad smo kombinirati polja i link popise zajedno. Osnovna ideja ipak je uzmemo neke podatke. Mi smo mali da podatke putem hash funkcija. I tako se podaci obrađuju i to ispljune broj, u redu? A onda s tim brojem samo mi pohranu podataka želimo pohraniti u niz na tom mjestu. Tako na primjer, imamo možda hash tablica žice. To je dobio 10 elemenata u njemu, tako da možemo stati 10 žice u njemu. Recimo da želimo hash Ivan. Dakle, Ivana kao podatke želimo umetnuti u ovom hash tablicu negdje. Gdje ćemo ga staviti? Pa obično Sa Niz dosad vjerojatno će ga staviti u polja položaj 0. No, sada imamo ovu novu funkciju hash. I recimo da smo pokrenuti Ivan kroz ovaj hash funkcije i to ispljune 4. Pa to je gdje smo će htjeti staviti Johna. Želimo staviti Ivanu u array mjestu 4, jer ako smo razmotrili Ivan again-- recimo kasnije smo želite pretraživati ​​i vidjeti ako je John postoji u ovom hash table-- sve što trebate učiniti je trčanje kroz isti hash funkcija, dobiti broj 4 out, i biti u mogućnosti pronaći Ivanu Odmah u našem strukture podataka. To je vrlo dobro. Recimo mi sada to opet, želimo hash Pavla. Želimo dodati Pavla u ovom hash tablicu. Recimo da je ovaj put smo pokrenuti Pavao kroz hash funkcija, Hash koji se generira 6. Pa sad možemo staviti Pavla u polja lokaciji 6. A ako moramo pogledati je li Pavao je u ovoj hash tablicu, sve što trebate učiniti je pokrenuti Pavao kroz hash funkcije ponovno a mi ćemo dobiti 6 opet. A onda smo samo pogledajte na polja lokaciji 6. Paul tamo? Ako je tako, on je u hash tablici. Je Pavao ne postoji? On nije u hash tablici. To je prilično jednostavan. Sad kako ti definirati hash funkcije? Pa da stvarno nema ograničenja na Broj mogućih hash funkcija. U stvari postoji nekoliko stvarno, stvarno dobre one na internetu. Postoji nekoliko jako, stvarno loši na internetu. To je također prilično jednostavan napisati lošu jedan. Dakle, ono što čini dobar hash funkcija, zar ne? Pa dobro funkcija raspršivanja trebao koristiti samo podatke koji se raspršen, i sve podatke koji se raspršen. Dakle, mi ne želimo koristiti anything-- ne sadrže ništa drugo osim podataka. I želimo iskoristiti sve podatke. Mi ne želimo samo koristiti komad nje, želimo iskoristiti sve to. Hash funkcija trebala također biti deterministička. Što to znači? Pa to znači da svaki put smo prolaze isti komad podataka u hash funkcije uvijek dobiti isti Hash broj van. Ako prođem Ivan Into the hash funkcija izađem 4. Ja bi trebao biti u mogućnosti to učiniti 10.000 puta i uvijek ću 4. Tako da nema slučajnih brojeva učinkovito mogu biti uključeni u našoj hash tables-- u našim hash funkcija. Hash funkcija također trebao ravnomjerno distribuirati podatke. Ako svaki put kada pokrenete podatke preko hash funkcija ste dobili Hash broj 0, to vjerojatno nije tako velika, zar ne? Vi vjerojatno želite veliki raspon hash kodova. Također se stvari mogu širiti po cijeloj tablici. I to bi bilo sjajno, ako stvarno slični podaci, kao što su Ivana i Jonatana, možda su se proširile na vaganje različita mjesta u hash tablici. To bi bilo lijepo prednost. Evo primjer hash funkcije. Napisao sam ovo gore ranije. To nije osobito dobro funkcioniraju mljeveno meso iz razloga koji ne stvarno nose ide u upravo sada. Ali vidiš što se ovdje događa? Čini se kao da smo progla varijablu zove suma i postavljanje ga jednaka 0. A onda je očito da radim nešto tako dugo dok strstr [j] nije jednak za kose crtice 0. Što ja radim ovdje? To je u osnovi samo još jedan način provedbe [? strl?] i otkrivanje kada ste stigao kraj niza. Dakle, nemam zapravo izračunati duljinu niza, Ja sam samo pomoću kada sam pogodio backslash 0 karakter znam Ja sam stigao do kraja niza. A onda ću zadržati iterating kroz taj niz, dodajući strstr [J] da zaključimo, a zatim na kraj dana će se vratiti zbroj mod HASH_MAX. Uglavnom sve je to mljeveno meso Funkcija radi se zbroje sve ASCII vrijednosti moj string, a zatim je povratka neke Hash broj modded by HASH_MAX. To je vjerojatno veličina moje polje, zar ne? Ne želim biti uzimajući hašiš Kodovi ako mi niz je veličine 10, Ne želim biti sve van hash oznake 11, 12, 13, ne mogu staviti stvari u one lokacije polja, to bi bilo protuzakonito. Ja bih pate grešku segmentiranja. Sada ovdje je još jedan brz stranu. Općenito vjerojatno nećeš želite napisati svoje hash funkcije. To je zapravo malo umjetnost, a ne znanost. I tu je mnogo toga što ide u njih. Internet, kao što sam rekao, puna stvarno dobar hash funkcija, i trebali koristiti internet za naći hash funkcija, jer to je stvarno samo vrsta nepotreban gubljenje vremena za napraviti svoj vlastiti. Možete napisati jednostavne one za svrhe testiranja. Ali kada su zapravo ide početi raspršivanja podataka i spremanje u hash tablici koju Vjerojatno će htjeti koristiti neke funkcije koje je generirana za vas, koji postoji na internetu. Ako samo nemojte biti sigurni citirati svoje izvore. Nema razloga da se plagirati ništa ovdje. Računalo znanost zajednica definitivno raste, a realno vrijednosti open source, i to je stvarno važno navesti svoje izvore, tako da ljudi mogu dobiti atribucije za rad koji oni radi na dobrobit zajednice. Dakle, uvijek biti sure-- a ne samo za mljeveno meso funkcije, ali općenito kad vas koristiti kod iz vanjskog izvora, uvijek navode svoj izvor. Dati kredit osobi koja je učinio Neki od posla, tako da ne morate. U redu, tako ćemo ponovno ovu hash tablicu na sekundu. To je mjesto gdje smo ostavili off nakon što umetnuta Ivan i Pavao u ovom hash tablicu. Vidite li problem ovdje? Možda ćete vidjeti dva. No posebno, zar ne pogledajte ovaj mogući problem? Što ako hash Ringo, i to Ispada da je nakon obrade te podatke kroz hash funkcije Ringo također generirao Hash broj 6. Već sam dobio podatke hashcode-- niz lokacija 6. Pa vjerojatno će biti malo problem za mene, zar ne? Mi to nazivamo sudara. A sudara nastaje kada dva komadići podataka izvoditi kroz isti hash Funkcija dati istu Hash broj. Vjerojatno još uvijek žele dobiti i komadići podataka u hash tablici, inače ne bismo se prikazivati ​​Ringo samovoljno kroz hash funkcije. Mi vjerojatno želite dobiti Ringo u taj niz. Kako ćemo to učiniti, iako, ako on i Paul i prinos Hash broj 6? Mi ne želite prebrisati Pavla, želimo Pavao biti tamo. Dakle, moramo naći način da se elemente u hash tablici koja još uvijek čuva našeg brzog umetanje i brzi pogled gore. A jedan od načina da se nositi s time je učiniti nešto što se zove linearni sondiranja. Koristeći ovu metodu, ako imamo sudara, dobro, što nam je činiti? Pa ne možemo ga staviti u array mjestu 6, ili što god Hash broj je generiran, neka ga stavi na Hash broj plus 1. A ako je to pun neka je stavite ga u Hash broj plus 2. Korist od ovog bića je li Ne točno gdje mi mislimo da je, a mi moramo početi tražiti, Možda ne moramo ići predaleko. Možda nemamo za pretraživanje sve n elementi hash tablici. Možda ćemo morati tražiti par njih. I tako smo još uvijek teži ka da prosječni slučaj bude blizu 1 vs u neposrednoj blizini n, pa možda da će raditi. Tako ćemo vidjeti kako se to možda rade u stvarnosti. I neka je vidjeti ako možda možemo otkriti problem koji se može dogoditi ovdje. Recimo da hash Bart. Dakle, sada ćemo pokrenuti novi set žice kroz hash funkcija, i mi pokrenuti Bart kroz hash funkcija, dobili smo Hash broj 6. Mi pogledamo, vidimo 6 prazna, tako da možemo staviti Bart tamo. Sada smo razmotrili Lisa i da Također generira Hash broj 6. Pa sad da smo koristeći ovaj Linearni sondiranje način možemo početi u 6, vidimo da 6 je pun. Ne možemo staviti Lisu u 6. Pa gdje idemo? Idemo do 7. 7 je prazna, tako da se radi. Tako ćemo staviti Lisa postoji. Sada smo razmotrili Homera i dobili smo 7. OK dobro znamo da 7 je pun sada, pa ne možemo staviti Homera postoji. Dakle, idemo do 8. Je li 8 dostupan? Da, i 8 bliski do 7, tako da ako moramo početi u potrazi smo neće morati ići predaleko. I tako ćemo staviti Homera u 8. Sada smo razmotrili Maggie i vraća 3, hvala Bogu smo mogli samo staviti Maggie postoji. Ne morate učiniti bilo vrsta sondiranje za to. Sada smo razmotrili Marge i Marge se vraća 6. Pa 6 pun, 7 je pun, 8 je pun, 9, u redu hvala Bogu, 9 je prazna. Ja mogu staviti Marge na 9. Već možemo vidjeti da smo početkom da imaju ovaj problem, gdje sada smo počinju se protežu stvari vrsta od daleko od svojih hash kodova. I to theta od 1, da prosječna Slučaj se vremenska konstanta, počinje se malo more-- počinju obično malo više prema theta n. Mi smo počeli gubiti da Prednost hash tablica. Ovaj problem koji smo upravo vidjeli nešto što se zove klastera. A što je stvarno loše grupiranje je da nakon što se sada imaju dva elementa koji su rame uz stranu to ga čini još vjerojatnije, imate dvostruko šanse, da idete imati još jedan sudar s tim klastera, a klaster će rasti po jedan. A vi ćete zadržati raste i raste Vaš vjerojatnost da sudar. I na kraju to je jednako loše kako ne sortiranja podataka na sve. Drugi problem je ipak ćemo dalje, i sada do ove točke, upravo smo bili vrsta razumijevanje što je hash tablica, još samo mjesta za 10 žice. Ako želimo nastaviti hash građani Springfield, možemo dobiti samo 10 od njih tamo. A ako ćemo pokušati dodati 11. ili 12., nemamo mjesta da ih stavi. Mi smo samo mogli biti vrti oko u krugovi pokušavaju pronaći prazno mjesto, i mi možda zapeti u beskonačnu petlju. Dakle, ova vrsta posuđuje ideje nešto naziva ulančavanje. I ovo je mjesto gdje ćemo donijeti povezani popisi natrag u sliku. Što ako, umjesto pohranjivanja jednostavno sama podataka u nizu, svaki element polja mogla držite više komada podataka? Pa to nema smisla, zar ne? Znamo da niz može samo hold-- svaki element niza mogu držati samo jedan komad podataka te vrste podataka. Ali što ako je tip podataka je popis povezani, zar ne? Pa što ako svaki element polja je pointer na čelu liste povezane? A onda smo mogli izgraditi oni povezani popisi i rastu im proizvoljno, jer povezani popisi omogućuju da rastemo i smanjiti mnogo više fleksibilno nego niz radi. Pa što ako smo sada koristite, smo iskoristiti ovu, zar ne? Mi početi rasti ove lance iz tih array mjestima. Sada možemo stati beskonačna Količina podataka, ili nije beskonačna, proizvoljna količina podataka, u našu hash tablicu bez trčanje u problem sudara. Također smo eliminirani grupiranje po to. A dobro znamo da kad smo umetnuti u popisu povezani, ako sjetiti iz naše video na povezanim popisima, pojedinačno povezani popisi i dvostruko vezane liste, to je konstanta vrijeme operacije. Mi samo dodao da je ispred. A za pogledati, ali znamo kako gledate na popisu povezan može biti problem, zar ne? Moramo pretraživanje je od početka do kraja. Nema slučajnih Pristup na popisu povezane. Ali ako umjesto jednog povezani Lista gdje pretraživanja će biti O n, sada imamo 10 povezane liste, ili 1.000 povezani popisi, sada je O n podijeljena 10, ili O n podijeljen 1000. I dok smo razgovarali teoretski o složenosti možemo zanemariti konstante u pravi Svijet te stvari zapravo smeta, zar ne? Zapravo ćemo primijetiti da se to događa pokrenuti 10 puta brže, ili 1.000 puta brže, jer mi smo distribuciju jednu dugu lanac preko 1.000 manjih lanaca. I tako svaki put moramo tražiti kroz jedan od onih lanaca možemo ignorirati 999 lance ne brinu o, i samo traži da je jedan. Što je u prosjeku za biti 1000 puta kraće. I tako smo još uvijek su vrsta naginjanje prema ovom prosječnom slučaju bude konstantan vremena, ali samo zato što se utjecati dijeljenjem nekim ogromnim konstantnim faktorom. Pogledajmo kako bi to moglo zapravo izgleda ipak. Dakle, to je hash tablicu smo imali prije nego što smo proglašen hash tablicu koja bio je sposoban za pohranu 10 žice. Nećemo to učiniti više. Mi već znamo ograničenja tog postupka. Sada naša hash tablicu će biti niz od 10 čvorova, upućuje na glavama povezanim popisima. A sada je null. Svaki od tih 10 upućuje je null. Nema ništa u našem hash tablicu odmah. Sada krenimo staviti neke stvari u ovom hash tablicu. I neka je vidjeti kako ova metoda će nam koristiti malo. Idemo sada hash Joey. Mi ćemo će se izvoditi niz Joey kroz hash funkcija i vraćamo 6. Pa što ćemo sad? Pa sad radi s povezanim popisima, mi ne radimo s polja. I kad radimo s povezanim popisima smo Znaš moramo početi dinamički dodjeljivanje prostora i izgradnju lanaca. To je vrsta how-- oni su srž elementi izgradnje popis povezani. Toliko je neka dinamički izdvojiti prostor za Joey, a onda ćemo ga dodati na lancu. Pa sad vidi što smo učinili. Kad smo razmotrili Joey dobili smo Hash broj 6. Sada se kazaljka na polja lokaciji 6 ukazuje na čelu popisa povezane, a sada je to jedina element popisa povezane. A čvor u koji povezani popis je Joey. Dakle, ako moramo pogledati Joey kasnije, samo smo razmotrili Joey opet, dobili smo 6 opet jer je naš hash funkcija je deterministička. A onda smo počeli na glavu popisa povezane istaknuo na koju array mjestu 6, i mi možemo ponoviti preko koje pokušava pronaći Joey. A ako gradimo naš hash tablicu učinkovito, a naš hash funkcija učinkovito distribuirati podatke i, u prosjeku je svaki od njih povezan lista na svakom mjestu poljem će biti 1/10 veličine ako samo ga je imao kao jedan veliki povezani popis sa svime u njemu. Ako smo distribuirati da ogroman povezan Lista preko 10 povezanih liste svaki popis će biti 1/10 veličine. I tako 10 puta brže za pretraživanje. Tako ćemo to učiniti opet. Idemo sada hash Ross. I recimo Ross, kad smo to hash kod se vratimo 2. Pa sad smo dinamički dodijeliti novi čvor, stavili smo Ross u tom čvoru, i mi sada reći niz lokacija 2, umjesto da ukazuje na null, ukazuje na glavu povezan Popis čiji je jedini čvor je Ross. A mi možemo učiniti još jednom, mi može hash Rachel i dobiti Hash broj 4. malloc novi čvor, stavite Rachel u čvor, i reći lokacije array 4. ukazuje na glavi od povezanog popisa čije Jedini element koji se događa da se Rachel. U redu, ali što će se dogoditi ako imamo sudar? Da vidimo kako možemo nositi sudara koristite zasebnu metodu ulančavanje. Idemo hash Phoebe. Mi smo dobili Hash broj 6. U našem prethodnom primjeru smo bili samo pohranjivanje konce u nizu. To je bio problem. Mi ne želimo clobber Joey, a mi smo već vidjeti da možemo dobiti neki klastera Problemi ako ćemo pokušati i korak kroz i probe. Ali što ako smo samo vrsta tretirati na isti način, zar ne? To je baš kao i dodavanje element na glavu popisa povezane. Ajmo malloc prostor za Phoebe. Mi ćemo reći Phoebe je sljedeće pokazivač bodova na staru glavu na popisu povezane, a onda 6 samo ukazuje na Novi šef popisa povezane. A sada pogledajte, promijenili smo Phoebe u. Sada možete pohraniti dva elementi s Hash broj 6, i nemamo nikakvih problema. To je ljepušan velik dio sve tu je ulančavanje. I ulančavanje je definitivno metoda koja je će biti najučinkovitiji za vas ako vi ste pohranjivanje podataka u hash tablici. No, ova kombinacija polja i povezane liste zajedno tvore hash tablice stvarno dramatično poboljšava vaše sposobnosti za pohranu velike količine podataka, te vrlo brzo i učinkovito traženje kroz te podatke. Postoji još jedan struktura podataka vani to bi čak moglo biti malo bolje u smislu jamčenja da je naš umetanje, brisanje i gledate vremena su čak i brže. I vidjet ćemo da je u video na pokušaja. Ja sam Doug Lloyd, ovo je CS50.