[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.