[MUSIC JOC] DOUG LLOYD: Până acum știu foarte multe despre matrice, și știți multe despre liste legate. Și am discuta argumente pro și contra, am discutat că legat liste pot obține mai mari și mai mici, dar ele ocupă mai mult dimensiune. Matrice sunt mult mai ușor de folosesc, dar sunt restrictive în măsura în ca avem de a seta dimensiunea de matrice de la bun început și apoi suntem blocați cu ea. Dar asta e, am destul de mult epuizat toate subiectele noastre de despre liste legate și matrice. Sau avem? Poate putem face ceva chiar mai creativ. Și la fel de bine împrumută ideea unui tabel hash. Deci, într-un tabel hash vom încerca combină un tablou cu o listă legată. Vom lua avantajele de matrice, cum ar fi acces aleator, fiind capabil de a merge doar la matrice Element 4 sau matrice element de 8 fără a fi nevoie de a repeta peste. Asta e destul de repede, nu? Dar noi, de asemenea, doresc să aibă datele noastre structură putea să crească și reduce. Nu avem nevoie de, noi nu doresc să fie limitat. Și vrem să fie în măsură pentru a adăuga și elimina lucruri foarte usor, care, dacă vă amintiți, este foarte complex, cu o serie. Și putem apela acest lucru nou un tabel hash. Și dacă implementat corect, suntem un fel de a lua avantajele ambelor date structuri le-ați văzut deja, tablouri si liste legate. Inserare poate începe să tind spre teta de 1. Theta nu am discutat într-adevăr, dar teta este doar cazul medie, ce de fapt se va întâmpla. Nu te întotdeauna o să au cel mai rău caz, și nu sunteți întotdeauna va avea cel mai bun caz, asa ca ce-i scenariul mediu? Ei bine, o inserție medie într-un tabel hash poate începe să se apropie de timp constant. Și ștergerea pot obține aproape de constanta de timp. Și de căutare pot obține aproape de constanta de timp. That's-- nu avem un date structură dar care pot face acest lucru, și așa mai departe acest lucru sună deja ca un lucru destul de mare. Am atenuat într-adevăr dezavantajele fiecărei pe cont propriu. Pentru a obține această performanță de upgrade, deși, am Trebuie să regândim modul în care adăugăm date în structura. Mai exact vrem Datele în sine pentru a ne spune în cazul în care ar trebui să meargă în structura. Și dacă am nevoie pentru a vedea apoi dacă se află într- structura, dacă avem nevoie să-l găsească, vrem să se uite la datele din nou și să fie capabil de a în mod eficient, folosind datele, acesta avea acces aleatoriu. Doar uitandu-se la date ar trebui să avem o idee de unde suntem gând să-l găsiți în tabelul hash. Acum dezavantaj de un hash Tabelul este că sunt foarte destul de rău la comanda sau de sortare a datelor. Și, de fapt, dacă începeți să le folosească pentru a comanda sau de sortare datele pe care le pierde cele de mai avantajele pe care le anterior a avut în ceea ce privește inserarea și ștergerea. Timpul devine mai aproape de teta de n, și ne-am practic regresat într-o listă legată. Și așa ne-o dorim doar să utilizați hash tabele, dacă nu le pasă dacă datele sunt sortate. Pentru contextul în care vei le folosească în CS50 probabil că nu-mi pasă că datele sunt sortate. Deci, un tabel hash este o combinație din două piese distincte cu care suntem familiarizați. Primul este o funcție, care De obicei apela o funcție hash. Și că funcție hash este de gând să reveni unele întreg non-negativ, care numim, de obicei, un hashCode, OK? Cea de a doua piesa este o matrice, care este capabil de a stoca date de tip WE doriți să plasați în structura de date. Vom dețină în afara pe de legat Element lista de acum și doar începe cu elementele de bază ale unei hash tabel pentru a obține capul în jurul valorii de ea, și apoi vom sufla poate mintea ta un pic atunci când am combina tablouri si liste de link împreună. Ideea de bază, deși este luăm unele date. Vom rula ca date prin funcția hash. Și astfel datele sunt procesate și scuipa un număr, OK? Și apoi cu acel număr ne-am stoca datele vrem să magazin din matrice la acea locație. Deci, de exemplu, avem poate acest tabel hash de siruri de caractere. Are 10 elemente în ea, astfel încât putem potrivi 10 siruri de caractere în ea. Să presupunem că vrem să hash John. Deci Ioan ca datele pe care le doriți să introduceți în acest tabel hash undeva. În cazul în care nu ne-am pus-o? Ei bine, de obicei, cu o matrice până acum ne-am, probabil, l-ar pune în matrice locație 0. Dar acum avem această nouă funcție hash. Și să spunem că vom rula Ioan prin această funcție hash și se scuipă 4. Ei bine, asta e în cazul în care suntem O să vrea să pună John. Vrem să pună Ioan în locație matrice 4, pentru că dacă ne-am hash John again-- să spunem mai târziu ne-am doriți să căutați și să vedem dacă John există în acest hash table-- tot ce trebuie să facem se rula prin același hash funcția, obține numărul 4, și să fie capabil de a găsi John imediat în structura noastra de date. Asta e destul de bun. Să presupunem că acum facem acest lucru din nou, vrem să hash Paul. Vrem să adăugați Paul în acest tabel hash. Să spunem că de data aceasta vom rula Paul prin funcția hash, hashCode care este generat este 6. Ei bine, acum putem pune Paul în locația matrice 6. Și dacă avem nevoie să se uite în sus dacă Paul este în acest tabel hash, tot ce trebuie să faceți este să rulați Paul prin funcția hash din nou și vom obține 6 din nou. Și apoi ne uităm doar la matrice locație 6. Paul acolo? Dacă este așa, e în tabelul hash. Paul nu-i așa? Nu e în tabel hash. E destul de simplu. Acum, cum ai defini o funcție hash? Ei bine, nu e chiar nici o limită la Numărul de posibile funcții hash. De fapt, există un număr de adevărat, cele foarte bine pe internet. Există o serie de adevărat, cele foarte rău pe internet. Este, de asemenea, destul de ușor pentru a scrie un rău. Deci, ceea ce face o bună funcție hash, nu? Ei bine, o funcție hash bun ar trebui să utilizați numai datele fiind distribuit, și toate datele fiind distribuit. Așa că nu doriți să utilizați anything-- noi nu includ nimic altceva, altele decât datele. Și vrem să folosească toate datele. Noi nu doriți să utilizați doar o bucată de ea, vrem sa folosim toate. O funcție hash ar trebui fi, de asemenea determinist. Ce înseamnă asta? Ei bine, aceasta înseamnă că de fiecare dată ne trece exact aceeași bucată de date în funcție hash mereu am obține același hashCode afară. Dacă trec Ioan în funcție hash ies 4. Ar trebui să fiu în stare să fac asta 10.000 ori și voi avea întotdeauna 4. Deci, nu numere aleatoare în mod eficient pot fi implicate în hash nostru tables-- în funcțiile noastre hash. O funcție hash ar trebui, de asemenea, distribuie uniform de date. Dacă de fiecare dată când executați date prin funcție hash veți obține hashCode 0, care, probabil, nu e atât de mare, nu? Probabil că doriți să mare o serie de coduri hash. De asemenea lucruri pot fi răspândite pe toată masa. Și, de asemenea, ar fi grozav dacă într-adevăr date similare, cum ar fi John și Ionatan, Poate s-au întins să cântărească diferite locații din tabelul hash. Asta ar fi un avantaj frumos. Iată un exemplu de o funcție hash. Am scris asta mai devreme. Nu este o deosebit de funcție hash bun pentru motive care nu prea suportă intra în chiar acum. Dar vezi ce se întâmplă aici? Se pare că suntem de declarare a unei variabile numit sumă și stabilirea-l egal cu 0. Și apoi se pare că fac ceva atât timp cât strstr [j] nu este egal la backslash 0. Ce fac acolo? Aceasta este de fapt doar un alt mod de punere în aplicare [? strl?] și detectarea când ați ajuns la sfârșitul șirului. Așa că nu trebuie să de fapt, calcula lungimea șirului, Sunt doar folosind când am lovit backslash 0 caracter știu Am ajuns la capătul șirului. Și apoi am de gând să păstreze iterarea prin care șir, adăugând strstr [j] pentru a rezuma, iar apoi la sfârșitul zilei de gând să se întoarcă sumă mod HASH_MAX. Practic toate acest hash Funcția este de a face este însumarea toate valorile ASCII ale șir meu, și apoi este revenind unele hashCode modded de HASH_MAX. Este, probabil, dimensiunea de matrice meu, nu? Nu vreau să fi obtinerea hash coduri dacă gama meu este de mărime 10, Nu vreau să fie obtinerea Codurile din hash 11, 12, 13, nu pot pune lucrurile în acele locații de matrice, că ar fi ilegal. Aș suferi o eroare de segmentare. Acum, aici este un alt rapid deoparte. În general, esti, probabil, nu va doresc pentru a scrie funcțiile propriile hash. Acesta este de fapt un pic de o artă, nu o știință. Și există o mulțime care merge în ele. Internetul, cum am spus, este plin de funcții foarte bun hash, și ar trebui să utilizeze internetul pentru a găsi funcții hash, deoarece este într-adevăr doar un fel de inutil pierdere de timp pentru a crea propriul. Puteți scrie cele simple în scop de testare. Dar atunci când, de fapt de gând să începe hashing date și stocarea acestuia într-un tabel hash esti probabil, va dori pentru a utiliza o funcție care a fost generat pentru tine, care există pe internet. Dacă nu doar să fie sigur pentru a cita sursele. Nu e nici un motiv să plagia nimic aici. Comunitatea informatică este cu siguranta in crestere, și într-adevăr valori open source, și este foarte important pentru a cita sursele, astfel încât oamenii pot obține atribuire pentru lucrarea pe care acestea sunt face în beneficiul comunității. Astfel încât să fie întotdeauna sure-- și nu doar pentru distribuire funcții, dar în general, atunci când folosi codul de la o sursă din afara, citează întotdeauna sursa. Da credit pentru persoana care a facut o parte din munca, astfel încât să nu trebuie să. OK Să reexamineze acest tabel hash pentru un al doilea. Acest lucru este în cazul în care am plecat off după ce am introdus Ioan și Pavel în acest tabel hash. Vedeți o problemă aici? S-ar putea vedea două. Dar, în special, nu vezi această problemă posibil? Ce se întâmplă dacă hash Ringo, și se dovedește că, după prelucrare că date prin funcția hash Ringo a generat, de asemenea, hashCode 6. Am deja date la hashcode-- matrice locație 6. Deci, este, probabil, va fi un pic de o problemă pentru mine acum, nu? Noi numim acest lucru o coliziune. Și coliziune are loc atunci când două piese de date rula prin același hash Funcția se obține aceeași hashCode. Probabil tot doriți să obțineți atât piese de date în tabel hash, altfel nu ne-ar fi difuzate Ringo arbitrar prin intermediul funcției hash. Ne probabil doriți să obțineți Ringo în această matrice. Cum o facem, deși, în cazul în care și Paul atât randament hashCode 6? Noi nu vrem să suprascrie Paul, vrem Pavel să fie acolo. Deci, trebuie să găsim o modalitate de a obține elemente în tabelul hash care încă păstrează rapid nostru inserție și scurtă privire în sus. Și o modalitate de a face cu ea este de a face ceva numit liniar sondare. Folosind această metodă, dacă avem o coliziune, ei bine, ce facem? Ei bine, nu-l pot pune în locație matrice 6, sau orice hashCode a fost generat, Să-l punem la hashCode plus 1. Și dacă asta e plin Să l-au pus în hashCode plus 2. Avantajul acestei ființe dacă e Nu exact unde credem noi că este, și trebuie să începem căutarea, Poate că nu trebuie să mergem prea departe. Poate că nu trebuie să căutați toate n elemente ale tabelului hash. Poate că trebuie să căutați câteva dintre ele. Și așa suntem încă tinde spre acest caz medie fiind de aproape de 1 vs aproape de n, astfel poate că va funcționa. Deci, hai sa vedem cum acest ar putea să funcționeze în realitate. Și să vedem dacă poate putem detecta problema care ar putea apărea aici. Să spunem că hash Bart. Deci, acum vom rula un nou set de siruri de caractere prin intermediul funcției hash, si vom rula Bart prin hash funcție, ne hashCode 6. Ne ia o privire, vom vedea 6 este gol, astfel încât să putem pune Bart acolo. Acum ne hash Lisa și că generează, de asemenea, hashCode 6. Ei bine, acum că suntem folosind acest liniar metodă de a începe de la 6 palpare, vom vedea că 6 este plin. Nu putem pune Lisa în 6. Deci, unde mergem? Să mergem la 7. 7 lui gol, astfel încât funcționează. Deci să punem Lisa acolo. Acum ne hash Homer și ajungem 7. OK bine știm că 7 e plin acum, așa că nu se poate pune Homer acolo. Așa că hai să mergem la 8. Este de 8 disponibil? Da, și 8, aproape de 7, deci, dacă trebuie să începem căutarea suntem nu va trebui să meargă prea departe. Și astfel să punem la Homer 8. Acum ne hash Maggie și întoarce 3, slavă Domnului suntem în măsură să pună doar Maggie acolo. Noi nu trebuie să facem nici un un fel de sondare pentru asta. Acum ne hash Marge, și Marge întoarce, de asemenea, 6. Ei bine, 6 este plin, 7 este plin, 8 este plin, 9, mulțumesc lui Dumnezeu în regulă, 9 este gol. Pot pune Marge la 9. Deja putem vedea că suntem incepand de a avea această problemă în cazul în care acum suntem Încep să se întindă lucruri fel de departe de codurile lor de dispersie. Și că teta de 1, care medie caz de a fi timp constant, începe pentru a obține un pic more-- incepand de la tendința de un pic mai mult spre teta de n. Suntem început să-și piardă că avantaj de tabele de dispersie. Această problemă pe care tocmai am văzut este ceva numit grupare. Si ceea ce este cu adevărat rău despre clustering este că, odată ce acum au două elemente care sunt una lângă alta se face chiar mai probabil, aveți dubla șansă, că ai de gând de a avea un alt coliziune cu cluster, și clusterul va crește cu unul. Și veți continua sa creasca si in crestere probabilitatea de a avea o coliziune. Și, eventual, e la fel de rău ca nu sortarea datelor de la toate. O altă problemă, deși este ne încă, și până în prezent până la acest moment, doar am fost un fel de intelegerea a ceea ce un tabel hash este, avem încă doar camerei timp de 10 siruri de caractere. Dacă dorim să continuăm să hash cetățenii Springfield, putem obține doar 10 dintre ele acolo. Și dacă vom încerca și adaugă un 11 sau 12, nu avem un loc pentru a le-a pus. Tocmai am putea fi în jurul valorii de filare în cercuri încercarea de a găsi un loc gol, si ne poate mă blochez într-o buclă infinită. Deci, acest tip de împrumută ideea de ceva numit înlănțuire. Și acest lucru este în cazul în care vom aduce liste legate înapoi în imagine. Ce se întâmplă dacă în loc de a stoca doar datele în sine în matrice, fiecare element de matrice ar putea deține mai multe bucăți de date? Ei bine, asta nu are nici un sens, nu? Știm că o serie poate doar hold-- fiecare element al unui tablou poate deține doar o singură bucată de date de acest tip de date. Dar ce se întâmplă dacă acel tip de date este o listă legată, nu? Deci, ce dacă fiecare Element de matrice a fost un pointer la cap de o listă legată? Și apoi am putea construi aceste liste legate de și să crească în mod arbitrar, deoarece liste legate permite ne să crească și reduce mult mai mult flexibil decât un tablou nu. Și ce dacă vom folosi acum, am parghie asta, nu? Vom începe să crească aceste lanturi din aceste locații matrice. Acum putem potrivi o infinit cantitatea de date, sau nu infinit, o cantitate arbitrară de date, în masa noastră hash fără să fie difuzate în problema de coliziune. De asemenea, Am eliminat clustering de a face acest lucru. Și bine știm că, atunci când vom introduce într-o listă legată, dacă vă amintiți din videoclipul nostru pe liste legate, individual liste legate și liste dublu legate, e o operațiune constantă de timp. Noi doar adăugarea în față. Și pentru look-up și știm care căuta într-o listă legată poate fi o problemă, nu? Trebuie să căutați prin l de la început până la sfârșit. Nu e nici o întâmplare acces într-o listă legată. Dar dacă în loc de a avea o legătură Lista în cazul în care o căutare ar fi O N, acum avem 10 de liste legate, sau 1.000 de liste legate, acum e O n împărțit la 10, sau O din n împărțit la 1,000. Și în timp ce noi vorbeam teoretic despre complexitate ignorăm constante, în real lumea aceste lucruri contează de fapt, dreapta? Noi de fapt, va observa că acest lucru se întâmplă pentru a rula 10 ori mai rapid, sau de 1.000 de ori mai rapid, pentru că suntem distribuirea unul lung lanț peste 1.000 de lanțuri mai mici. Și așa de fiecare dată când avem de a căuta prin una din acele lanțuri putem ignora 999 lanturile noi nu le pasa despre, si cauta doar ca unul. Care este, în medie, la fi de 1.000 de ori mai scurtă. Și așa că încă mai sunt un fel de tinde spre acest caz mediu de a fi constantă de timp, dar doar pentru că suntem pârghie împărțirea de un factor imens constant. Să vedem cum acest lucru ar putea de fapt uite totuși. Deci aceasta a fost tabel hash am avut înainte de a ne declara un tabel hash care a fost capabil de a stoca 10 siruri de caractere. Noi nu vom mai face asta. Știm deja limitări ale acestei metode. Acum, masa noastră hash va fi o serie de 10 noduri, indicii șefilor de liste legate. Iar acum e nul. Fiecare dintre cele 10 indicii este nulă. Nu e nimic în nostru hash masă acum. Acum să începem să pună unele lucrurile în acest tabel hash. Și să vedem cum această metodă este O să ne beneficia un pic. Să acum hash Joey. Vom va rula șir Joey prin o funcție hash și ne întoarcem 6. Ei bine, ce facem acum? Ei bine, acum de lucru cu liste legate, nu suntem de lucru cu tablouri. Și când lucrăm cu liste legate noi că avem nevoie pentru a începe dinamic alocarea de spațiu și de construcții lanțuri. Asta e un fel de how-- acestea sunt de bază elemente de a construi o listă legată. Deci, haideți să dinamic aloca spațiu pentru Joey, și apoi să-l adăugați la lanțul. Deci, uite acum ce am făcut. Când ne-am hash Joey am primit hashCode 6. Acum, indicatorul de la matrice locație 6 subliniază capul unei liste legate, iar acum este singurul element al unei liste legate. Și nodul în care Lista de legat este Joey. Deci, dacă trebuie să privim în sus Joey mai târziu, ne-am hash Joey din nou, ajungem 6 din nou, deoarece nostru funcție hash este determinist. Și apoi vom începe de la cap listei de legătura subliniat a de locație matrice 6, și putem repeta peste care încearcă să găsească Joey. Și dacă vom construi nostru hash masă în mod eficient, și funcția noastră hash eficient de a distribui date bine, în medie, fiecare dintre cele legate liste la fiecare locație matrice va fi 1/10 din mărimea dacă la fel a avut ca un singur imens Lista legată de tot ceea ce în ea. Dacă vom distribui că imens legat Lista peste 10 liste legate fiecare listă va fi 1/10 dimensiunea. Și astfel de 10 ori mai repede pentru a căuta prin. Deci, hai sa facem asta din nou. Să acum hash Ross. Și să spunem Ross, atunci când facem asta codul de distribuire ne intoarcem este 2. Ei bine, acum ne-am aloca dinamic un nod nou, am pus Ross în acel nod, și spunem acum locație matrice 2, în loc de arătând spre nul, punctele de la cap de legat Lista a căror numai nod este Ross. Și putem face asta de mai mult timp, ne-am poate hash Rachel și de a lua hashCode 4. malloc un nou nod, a pus în Rachel nodul, și spune o locație matrice 4. atrage atenția asupra capului a unei liste a cărui legat singurul element se întâmplă să fie Rachel. OK, dar ce se întâmplă dacă avem o coliziune? Să vedem cum ne ocupam de coliziuni folosind metoda înlănțuirii separat. Să hash Phoebe. Vom obține hashCode 6. În exemplul nostru anterior am fost doar stocarea siruri de caractere în matrice. Aceasta a fost o problemă. Noi nu vrem să rescrie Joey și am deja văzut că putem obține unele clustering probleme dacă am încerca și pas prin și sonda. Dar dacă am doar un fel de trata acest fel, nu? E la fel ca adăugarea unui element la capul unei liste legate. Să spațiu doar malloc pentru Phoebe. Vom spune următoarele indicatorul lui Phoebe la vechiul cap al listei de legătura, și apoi 6 puncte doar la noul șef al listei legate. Și acum uite, ne-am schimbat Phoebe in. Putem stoca acum două elemente cu hashCode 6, și nu avem nici o problemă. Asta e destul de mult tot este de înlănțuire. Și înlănțuirea este cu siguranta metoda care este va fi cel mai eficient pentru tine, dacă sunteți stocarea datelor într-un tabel hash. Dar această combinație de tablouri si liste legate împreună pentru a forma un tabel hash într-adevăr îmbunătățește dramatic capacitatea de pentru a stoca cantități mari de date, și căutare foarte rapid și eficient prin care datele. Există încă o mai structură de date acolo care ar putea fi chiar un pic mai bine în ceea ce privește garantarea că ne inserție, ștergere, și privi în sus ori sunt chiar mai repede. Și vom vedea că într-un film pe incercari. Sunt Doug Lloyd, aceasta este CS50.