[Predvaja glasba] Doug LLOYD: Do sedaj ste vedo veliko o nizi, in veste veliko o povezanih seznamih. In smo razpravljali prednosti in slabosti, ki smo jih razpravljali, da povezana sezname lahko dobite večji in manjši, vendar pa lahko zasedejo več velikosti. Polja so veliko bolj enostavne za uporabo, ampak oni so omejevalni toliko saj moramo določiti velikost array na samem začetku in potem smo obtičali z njim. 

Ampak to je, ki smo jih precej izčrpane vse naše teme o povezanih seznamih in nizi. Ali imamo? Mogoče lahko naredimo nekaj še bolj ustvarjalni. In to nekako daje ideja o hash tabele. 

Torej v hash tabele bomo poskušali združiti niz s povezani seznam. Bomo vzeli prednosti matrike, kot bralno, da lahko samo pojdi na paleto element 4 ali matrika element 8 ne da bi čez Ponovil. To je zelo hitro, kajne? 

Vendar pa smo tudi želeli, da imajo naše podatke struktura lahko rastejo in psihiater. Mi ne potrebujemo, ne bomo želijo biti omejeni. In želimo, da bi lahko dodati in odstraniti stvari zelo enostavno, ki bodo, če se spomnite, je zelo zapleten s paleto. In lahko rečemo to nova stvar hash tabele. 

In če se izvaja pravilno, smo nekako ob prednosti obeh podatkov strukture, ki ste jih že videli, nizi in povezani seznam. Vstavljanje lahko začnete nagibajo k theta od 1. Theta smo res ne razpravlja, vendar theta je le povprečna primeru kaj se dejansko dogaja, da se zgodi. Vi ne vedno dogaja, da imajo najslabši možni scenarij, in ne boš vedno dogaja, da imajo najboljši scenarij, kaj je povprečna scenarij? 

Dobro povprečno vstavljanje v hash tabelo Lahko začnete priti blizu stalnim časom. In izbris lahko dobite zapreti do konstantne časa. In lookup lahko dobite zapreti do konstantne časa. That's-- ne bomo imeli podatkov struktura še, da lahko to storite, in tako to že sliši kot zelo velika stvar. Smo v resnici ublažilo slabosti vsaka sama. 

Da bi dobili ta zmogljivost nadgradnjo pa smo je treba premisliti, kako bomo dodali Podatki v strukturi. Posebej želimo, Sam podatek, da nam pove kjer naj gre v strukturi. In če bomo potem morali videti, če je to v struktura, če bomo potrebovali, da ga najdejo, želimo gledati podatkov znova in biti sposoben učinkovito, uporabo podatkov, naključno dostop do nje. Samo jih je videti na Podatki bi morali imeti ideja o tem, kje točno smo dogaja, da ga najdejo v hash tabele. 

Zdaj je negativna zgoščene Miza je, da si res Precej slabo naročanju ali razvrščanje podatkov. In v resnici, če začnete jih uporabiti, da odredijo ali vrsta Podatki, ki ste izgubili vse prej ste prednosti imel v smislu vstavljanja in brisanja. Čas postane bližje theta n, in smo v bistvu nazadovala v povezanem seznamu. In tako smo le želeli uporabiti hash mize, če ne skrbijo ali se podatki razporejene. Za kontekst, v katerem jih boste uporabili v CS50 ti verjetno ne skrbi da se podatki razporejene. 

Torej hash tabela je kombinacija iz dveh ločenih delov s katerimi smo seznanjeni. Prva je funkcija, ki smo običajno imenujemo funkcijo razpršitve. In to funkcijo razpršitve se dogaja, da vrne neko nenegativno celo število, ki je smo ponavadi klic hashcode, OK? Drugi del je matrika, ki je sposoben shranjevanja podatkov o vrsti mi želijo postaviti v strukturo podatkov. Bomo držite off na povezani seznam element za zdaj in šele začeti z osnovami hash tabele, da bi dobili svojo glavo okoli njega, in potem bomo morda razstrelil tvoj um malo, ko smo združujejo nize in sezname povezavo skupaj. 

Osnovna ideja je, čeprav je vzamemo nekaj podatkov. Vodimo te podatke prek funkcija hash. In tako se podatki obdelujejo in ga izpljune številko, OK? In potem s to številko smo pravkar shranjevanje podatkov želimo shraniti v Niz na tej lokaciji. Tako na primer imamo morda to hash tabela nizov. Ima 10 elementov v njej, tako da bomo lahko fit 10 strune v njem. 

Recimo, da želimo, da hash John. Torej Janeza kot podatkih želimo vstaviti v ta hash tabelo nekje. Kje smo ga dal? No, po navadi s Niz doslej smo verjetno bi ga dal v matrično mestu 0. Toda zdaj imamo to novo funkcijo razpršitve. 

In recimo, da tečemo po Janezu skozi to funkcijo razpršitve in to je izpljune 4. No, to je, če smo dogaja, da želijo dati John. Želimo postaviti John v matriki lokacijo 4, ker če smo izbrskali John again-- recimo kasneje smo želite iskati in videti če John obstaja v tem hash table-- vse moramo storiti se jo vodijo skozi isti hash Funkcija, dobili številko 4, in biti sposobni najti Johna takoj v našo strukturo podatkov. To je zelo dobro. 

Recimo, da imamo sedaj to storiti še enkrat, želimo hash Paul. Želimo, da dodate Paul v ta hash tabelo. Recimo, da smo tokrat teči Paul skozi funkcije razpršitve, hashcode da se ustvari je 6. No, zdaj bomo lahko dal Pavlu na lokaciji matrike 6. In če moramo pogledati, ali Paul je v tem hash tabeli vse, kar morate storiti je, teči Paul s pomočjo funkcije razpršitve spet in bomo dobili 6 spet ven. 

In potem smo samo pogled na matrično lokaciji 6. Paul tam? Če je tako, da je v hash tabele. Paul ni tam? On ni v hash tabele. To je precej preprosta. 

Zdaj kako definirate funkcijo razpršitve? No, tam je res ni omejitev na število možnih funkcij hash. V bistvu je število res, res dobri na internetu. Obstaja nekaj res, res slabe na internetu. Prav tako je zelo enostavno napisati slabega. 

Torej, kaj naredi gor dober hash funkcijo, kajne? No dobra funkcija hash smeli uporabljajte samo so zgoščene podatke, in vse podatke, ki zgoščen. Torej ne želimo uporabiti anything-- ne vključujejo ničesar drug razen podatkov. In želimo uporabiti vse podatke. Nočemo, da samo uporabite kos od tega, želimo uporabiti vse. Funkcija hash smeli tudi deterministična. Kaj to pomeni? No, to pomeni, da vsakič, ko smo opraviti natančno isto podatek v funkcijo razpršitve smo vedno dobil isto hashcode ven. Če sem mimo Johna Into The hash funkcija pridem ven 4. Moral bi biti sposoben narediti, da je 10.000 krat in bom vedno dobili 4. Torej ni naključnih števil učinkovito lahko sodelujejo v našem hash tables-- v naših hash funkcij. 

Funkcija hash naj bi tudi enakomerno porazdeli podatke. Če vsakič, ko zaženete podatkov prek hash funkcija dobiš hashcode 0, da je to verjetno ni tako veliko, kajne? Boste verjetno želeli, da velik vrsta hash kode. Prav tako se stvari lahko širijo v celotnem tabeli. In prav bi bilo super, če res podobne podatke, kot so John in Jonatanom, Mogoče so bili razporejeni za tehtanje različne lokacije v hash tabele. To bi bilo lepo prednost. 

Tukaj je primer funkcije razpršitve. Sem napisal tole gor prej. To ni posebej dobra funkcija razpršitve iz razlogov, ki v resnici ne nosi dogaja v tem trenutku. Ampak vidite, kaj se dogaja tukaj? Zdi se, kot da smo razglasitvi spremenljivko imenovano vsoto in jo nastavite enaka 0. In potem očitno delam nekaj dokler strstr [j] ni enako da poševnica nazaj 0. Kaj počnem tukaj? 

To je v bistvu samo še en način izvajanja [? STRL?] in odkrivanje, ko ste prišli do konca niza. Torej, jaz ne bi bilo treba dejansko izračunati dolžino niza, Jaz sem samo s pomočjo, ko sem udaril poševnica nazaj 0 značaj vem Sem dosegel konec niza. In potem grem naprej ponavljanjem skozi ta niz, dodajanje strstr [J], da povzamem, in nato na konec dneva bomo vrnili znesek mod HASH_MAX. 

V bistvu vse to hash funkcija počne se sešteva vse vrednosti ASCII moj niz, nato pa je vračanje nekaj hashcode modded jih HASH_MAX. Verjetno je velikost moje array, kajne? Nočem, da bi dobili hash Kode če moj array je velikosti 10, Ne želim, da bi dobili od hash kode 11, 12, 13, ne morem postaviti stvari v tiste lokacije matrike, da bi bilo nezakonito. Sem trpel napako segmentacije. 

Zdaj tukaj je še en hiter stran. Na splošno ste verjetno ne bo želite napisati svoje hash funkcije. Dejansko je malo umetnost, ne znanost. In tam je veliko, da gre v njih. Internet, kot sem rekel, je polno zares dobrih hash funkcije, in morate uporabljati internet, da bi našli hash funkcije, ker to je res le nekako nepotrebno zapravljanje časa, da ustvarite svojo. 

Lahko napišete preproste tiste za testiranje. Toda, ko ste dejansko se dogaja, da začetek razpršitev podatkov in shranjevanje v hash tabelo ste ga Verjetno boš želel Za uporabo nekatere funkcije, ki je ustvarjen za vas, da obstaja na internetu. Če vam samo se prepričajte, citirati svoje vire. Ni razloga, da bi plagiarize ničesar tukaj. 

Računalnik znanstvena skupnost je definitivno raste, in res vrednote open source, in to je res pomembno citirati svoje vire, da se ljudje lahko dobite pripis za delo, da oni delaš v korist skupnosti. Torej vedno sure-- in ne samo za hash funkcije, ampak na splošno, ko vas uporabo kode iz zunanjega vira, Vedno navajajo svoj vir. Dati kredit, da osebe, ki je nekaj dela, tako da ne bi bilo treba. 

OK, tako da je ponovno to hash tabela za sekundo. To je, kjer se nam z leve off ko smo vstavi John in Paul v tem hash tabelo. Ali vidiš problem tukaj? Morda boste videli dva. Ampak predvsem, kajne glej to možno težavo? 

Kaj pa, če sem hash Ringo, in Izkazalo se je, da je po predelavi da so podatki prek funkcije razpršitve Ringo ustvarila tudi hashcode 6. Sem že dobil podatke na hashcode-- lokacija matrika 6. Tako da je verjetno, da bo malo problem zame, kajne? 

Pravimo to trčenje. In pride do trčenja, ko dva deli podatkov teče skozi isti hash Funkcija dobimo enako hashcode. Verjetno bomo še vedno želijo, da bi dobili tako koščki podatkov v hash tabele, drugače mi ne bi bilo tekmovanje v teku Ringo poljubno skozi funkcije razpršitve. Bomo verjetno želeli, da bi dobili Ringo v tem polju. 

Kako to storiti, čeprav, če je in Paul sta donos hashcode 6? Mi ne želite prepisati Pavla, želimo Paul biti tam. Zato moramo najti način, da bi dobili elementi v hash tabele, ki še vedno ohranja Naš hiter vstavljanje in hiter pogled navzgor. In eden od načinov za spopadanje s tem je, da storiti nekaj, kar ti linearni sondiranje. 

Z uporabo te metode, če imamo trčenje, no, kaj naj naredimo? No, ne moremo ga dal v matriki lokacijo 6, ali karkoli hashcode je bil ustvarjen, dajmo mu ga na hashcode plus 1. In če je to v celoti Oglejmo ga dal v hashcode plus 2. Korist od tega bitja, če je on ne točno tam, kjer mislimo, da je, in moramo začeti iskati, Mogoče mi ne bi bilo treba iti predaleč. Morda ne bi bilo treba iskati vseh n elementi hash tabele. Morda bomo morali iskati Nekaj ​​od njih. 

In tako smo še vedno težijo k da v povprečju velja, da so blizu 1 vs blizu do n, tako da morda, da bo delovalo. Torej, da vidimo, kako to lahko izšlo v resnici. In poglejmo, če morda lahko zazna problem, da lahko pride do tu. 

Recimo, da smo izbrskali Bart. Torej, zdaj gremo teči nov niz nizov s pomočjo funkcije razpršitve, in tečemo Bart skozi hash Funkcija, smo dobili hashcode 6. Mi si oglejte, vidimo 6 je prazna, tako da bomo lahko dal Bart tam. 

Zdaj smo hash Liso in da Prav tako ustvarja hashcode 6. No sedaj, da smo s pomočjo tega Linearni sondiranje metodo začnemo na 6, vidimo, da je 6 polni. Ne moremo dati Liso v 6. Torej, kam gremo? Pojdimo do 7. 7 je prazna, tako da deluje. Torej, kaj je dal Lisa tam. 

Zdaj smo hash Homerja in smo dobili 7. OK, dobro vemo, da je 7 je poln zdaj, zato ne moremo dati Homer tam. Torej, pojdimo do 8. 8 na voljo? Ja, in 8 je blizu 7, tako da, če moramo začeti iskati smo ne bo treba iti predaleč. In tako da je dal Homer ob 8. 

Zdaj smo hash Maggie in vrne 3, hvala bogu smo sposobni samo dal Maggie tam. Mi ne bi bilo treba storiti vse nekako sondiranje za to. Zdaj smo hash Marge, in Marge tudi vrne 6. 

No 6 polna, 7 je poln, 8 je polna, 9, v redu hvala bogu, 9 je prazna. Jaz lahko postavite Marge ob 9. Že vidimo, da začenjamo da ima ta problem, kjer smo zdaj začenja se raztezajo stvari nekako od daleč od svojih hash kode. In da theta po 1, da je povprečna V primeru da je konstantna čas, se začenja, da bi dobili malo more-- začenja ponavadi malo bolj slabo theta n. Mi smo začeli izgubljati da Prednost hash tabel. 

Ta problem, ki smo ga pravkar videli je nekaj, kar se imenuje grozdenje. In kaj je res slabo o grozdenje je, da ko vas zdaj ima dva elementa, ki so drug ob drugo pa je še bolj verjetno, imate dvakrat več priložnost, da greste da imajo še eno trčenje s tem grozdu, in grozd bo rasla po enega. In si bomo še naprej raste in raste vaša verjetnost ob trčenju. In na koncu, da je ravno tako slabo saj ni sortiranje podatkov na vseh. 

Druga težava, čeprav je, da smo pri miru in doslej do te točke, pravkar smo bili nekako razumevanje, kaj je hash tabela, imamo še vedno le prostor za 10 nizov. Če želimo, da še naprej hash državljani Springfield, bomo lahko dobili le 10 od njih tam. In če bomo poskušali dodati 11. ali 12., nimamo mesto da bi jih dal. Lahko bi se samo vrti okoli v krogi poskušajo najti prazno mesto, in smo dobili morda zaljubljen v neskončni zanki. 

Tako da je ta vrsta primerna za idejo nečesa imenovano veriženje. In to je, kam gremo, da bi povezani seznami nazaj v sliko. Kaj če bi namesto shranjevanja samo Sam podatek v matriki, vsak element matrike lahko držite več kosov podatkov? No, da nima smisla, kajne? Vemo, da lahko le niz hold-- vsak element matrike lahko ima samo en kos podatkov te vrste podatkov. 

Toda kaj, če ta vrsta podatkov je povezani seznam, kajne? Pa kaj, če vsak element matrike je kazalec na čelu povezani seznam? In potem lahko gradimo ti povezani seznami in jim rastejo poljubno, ker povezani seznami omogočajo nas, da raste in psihiater veliko več fleksibilno kot array počne. Pa kaj, če smo zdaj uporabljajo, smo vzvod to, kajne? Začetek smo gojili te verige od teh nizov lokacijah. 

Sedaj lahko fit neskončno količina podatkov, ali ni neskončna, poljubna količina podatkov, v našem hash tabelo ne da bi kdaj teče v problem trka. Prav tako smo jih odpraviti grozdenje s tem. In dobro vemo, da ko smo vstavite v povezani seznam, če se spomnite iz naše video na povezanih seznamov, posamezno povezani seznami in dvojno povezani seznam, to je konstantna operacija čas. Mi smo samo tako, da je spredaj. 

In poglej gor, dobro vemo, da pogledate v povezanem seznamu je lahko problem, kajne? Moramo iskati prek je od začetka do konca. Ni naključno dostop v povezanem seznamu. Toda, če namesto da eno povezano seznam, kjer bi bilo iskanje O n, imamo zdaj 10 povezanih seznamov, ali 1.000 povezani seznami, zdaj je O n deljeno z 10, ali O n, deljeno s 1.000. 

In medtem, ko smo govorili teoretično o kompleksnosti odmislimo konstante, v realnem svet te stvari dejansko pomembno, prav? Pravzaprav bomo opazili da se to zgodi teči 10-krat hitreje, ali 1.000-krat hitreje, ker smo distribucijo eno dolgo veriga poda 1.000 manjših verig. In tako vsakič, ko imamo za iskanje skozi eno od teh verig moremo prezreti 999 verig nam ni mar o, in samo iskanje, da je eden. 

Ki je v povprečju 1.000-krat krajši. In tako smo še nekako težijo k temu povprečnega primera , da so stalno časa, vendar samo zato, ker smo vplivno delimo z neko ogromno konstantnim faktorjem. Poglejmo, kako bi to lahko dejansko videti, čeprav. Torej je bil to hash tabelo smo imeli preden smo razglasili za razpršene tabele, ki je lahko shrani 10 nizov. Ne bomo storiti več. Smo že vedeli omejitve te metode. Sedaj naš hash tabele, se dogaja, da niz 10 vozlišč, kazalci vodjem povezanih seznamov. 

In zdaj je ničen. Vsak od teh 10 kazalcev, je nična. Nič ni v naši hash tabelo zdaj. 

Zdaj pa začnimo postaviti nekatere Stvari v tej hash tabele. In poglejmo, kako se je ta metoda dogaja, da nam koristijo malo. Poglejmo zdaj hash Joey. Bomo bo potekal niz Joey skozi funkcija razpršitve in vrnemo 6. No, kaj pa zdaj? 

No, zdaj delajo s povezanimi seznamov, ne bomo delo z nizi. In ko delamo s povezanimi seznamov smo vedeti moramo, da dinamično začeti dodeljevanja prostora in gradnjo verige. To je nekako how-- ti so jedro elementi izgradnjo povezani seznam. Torej Dovolite dinamično dodeliti prostor za Joeya, nato pa dodajte ga v verige. 

Torej, zdaj poglej, kaj smo naredili. Ko smo hash Joey imamo hashcode 6. Zdaj se kazalec na matrično lokaciji 6 opozarja na glavo povezanega seznama in zdaj je edina element povezani seznam. In s tem, da vozlišče povezani seznam je Joey. 

Torej, če bomo morali pogledati Joey kasneje, smo samo hash Joey spet, smo dobili 6 spet, ker je naša hash funkcija je deterministično. In potem začnemo na čelu od povezanega seznama opozoril jih matrike lokacijo 6, in bomo lahko Ponovil čez, da poskuša najti Joey. In če bomo gradili učinkovito hash tabelo, in naša hash funkcija učinkovito za distribucijo podatkov dobro, v povprečju vsak od tiste, povezane Seznami na vsakem diod lokacijo bo 1/10 velikost, če smo Pravkar ga je imel kot en sam ogromen povezani seznam z vsem v njem. 

Če bomo razdelili, da je velik povezan seznam čez 10 povezanih seznamov vsak seznam bo 1/10 velikost. In s tem 10-krat hitreje iskanje skozi. Torej, kaj je to storiti še enkrat. Poglejmo zdaj hash Ross. 

In recimo, Ross, ko to naredimo hash code bomo dobili nazaj, je 2. No, zdaj smo dinamično dodeli novo vozlišče, smo se Ross v tem vozlišču, in smo rekli, zdaj matrika lokacijo 2, namesto da kaže na ničlo, opozarja na čelu povezani Seznam katerega edino vozlišče je Ross. In bomo lahko to storijo še enkrat, mi lahko hash Rachel in dobili hashcode 4. malloc novo vozlišče, dal Rachel v vozlišče, in pravijo lokacijo niz 4 zdaj opozarja na glavi iz povezanega seznama S Edini element, se zgodi, da bo Rachel. 

OK, ampak kaj se zgodi, če imamo trčenje? Pa poglejmo, kako ravnamo trčenja z ločeno metodo veriženja. Oglejmo hash Phoebe. Smo dobili hashcode 6. V prejšnjem primeru smo pravkar shranjevanje strune v array. To je problem. 

Nočemo, da clobber Joey, in smo jih že razvidno, da bomo lahko dobili nekaj gruč težave, če bomo poskušali in korak skozi in sonda. Toda kaj, če smo le nekako zdravljenje je to na enak način, kajne? To je tako kot dodaja element z glavo povezanega seznama. Naj samo malloc prostor za Phoebe. 

Bomo rekli naslednji kazalec točk Phoebe je s starim glavo povezanem seznamu in nato na 6 samo opozarja na Novi vodja povezanega seznama. In zdaj poglej, smo spremenili Phoebe v. Sedaj lahko shranite dve elementi z hashcode 6, in nimamo nobenih težav. 

To je zal veliko vse tam je veriženje. In veriženje je definitivno metoda, ki je dogaja, da je najbolj učinkovita za vas, če ste shranjevanje podatkov v hash tabele. Toda ta kombinacija nizi in povezani seznami skupaj tvorita razpršene tabele res dramatično izboljša vašo sposobnost za shranjevanje velike količine podatkov, in zelo hitro in učinkovito iskanje preko teh podatkov. 

Tam je še ena več podatkovna struktura tam da je morda celo malce bolje v smislu zagotavljanja da je naša vstavljanje, brisanje in poglej gor časi so še hitreje. In bomo videli, da je v video na poskusih. Sem Doug Lloyd, to je CS50.