JASON KU: Bun venit la a patra prelegere din 6.006. Astăzi vom vorbi despre hashing. Ultima prelegere, marți, profesorul Solomon a vorbit despre structurile de date stabilite, stocarea lucrurilor astfel încât să puteți interoga elementele după dreptul lor cheie, după ceea ce sunt ele în mod intrinsec -- față de ceea ce vorbea profesorul Demaine săptămâna trecută, care era structurile de date secvențe. , unde impunem o comandă externă acestor articole și dorim să le mențineți. Nu susțin operațiuni în care caut lucruri în funcție de ceea ce sunt. Pentru asta este interfața setată. Așa că vom vorbi un pic mai mult despre interfața setată astăzi. Marți, ați văzut două moduri de implementare a interfeței set-- una folosind doar o matrice nesortată-- doar, am aruncat aceste lucruri într-o matrice și am putut face o scanare liniară a articolelor mele pentru a suporta practic oricare dintre aceste operațiuni. Este un mic exercițiu prin care poți trece. Cred că ți-o arată în notele de recitare, dar dacă vrei să o implementezi pentru tine, e în regulă. Și apoi am văzut o structură de date puțin mai bună, cel puțin pentru operațiunile de căutare. Pot să caut ceva , dacă această cheie se află în interfața setată? Putem face asta mai repede. Putem face asta în log n time cu un build overhead care este de aproximativ n log n, pentru că v-am arătat trei moduri de sortare. Două dintre ele au fost la pătrat. Unul dintre ele a fost n log n, ceea ce este la fel de bun precum v-am arătat cum să faceți ieri. Deci întrebarea devine, pot construi acea structură de date mai rapid? Acesta va fi subiectul prelegerii de joi de săptămâna viitoare. Dar săptămâna aceasta ne vom concentra asupra acestei descoperiri statice. avem log n, care este o îmbunătățire exponențială față de dreapta liniară, dar întrebarea devine acum, pot face mai repede decât log n timp? Și ceea ce vom face în prima parte a acestei prelegeri este să vă arătăm că, nu, tu... PUBLIC: [INAUDIBIL] JASON KU: Ce e? Nu? OK-- că nu poți face mai repede decât log n timp, cu avertismentul că ne aflăm într-un model de calcul puțin mai restrâns decât am fost-- decât ceea ce ți-am prezentat acum câteva săptămâni. Și atunci, dacă nu ne aflăm în acel model de calcul mai restrâns, putem de fapt să facem mai repede. Log n este deja destul de bun. Log n nu va fi mai mare decât 30 pentru orice problemă despre care veți vorbi în lumea reală pe computere reale, dar un factor de 30 este încă rău. Aș prefera să mă descurc mai repede cu acei factori constanți, când pot. Nu este un factor constant. Este un factor logaritmic, dar înțelegi ceea ce spun. OK, deci ceea ce vom face este mai întâi să dovedim că nu poți face mai repede pentru-- înțeleg toată lumea-- îți amintești ce înseamnă găsirea cheii? Am o cheie, am o grămadă de articole care au chei asociate și vreau să văd dacă unul dintre articolele pe care le stochez conține o cheie care este aceeași cu cea pe care am căutat-o. Articolul poate conține și alte lucruri, dar în special are o cheie de căutare pe care o mențin, astfel încât să accepte operațiuni de căutare, operațiuni de căutare bazate pe acea cheie rapid. Are sens? Deci, există găsirea pe care vrem să-l îmbunătățim și, de asemenea, vrem să îmbunătățim această ștergere a inserției. Vrem să fim... să facem aceste date dinamice structurale, pentru că s- ar putea să facem acele operațiuni destul de mult. Și astfel, această prelegere este despre optimizarea acestor trei lucruri. OK, așa că mai întâi, am să vă arăt că nu putem face mai repede decât log n pentru găsire, ceea ce este puțin ciudat. OK, modelul de calcul pe care voi demonstra această limită inferioară-- cum voi aborda aceasta este, voi spune că în orice mod în care voi stoca acestea-- articolele pe care le stochez în această structură de date - pentru că oricum am văzut aceste lucruri, orice algoritm de acest anumit tip va necesita cel puțin timp logaritmic. Asta vom încerca să dovedim. Și modelul de calcul care este mai slab decât ceea ce am vorbit anterior este ceea ce voi numi model de comparație. Iar un model de comparație înseamnă... este că articolele, obiectele pe care le stochez... le pot considera ca niște cutii negre. Nu apuc să ating aceste lucruri, doar că singurul mod în care pot distinge între ele este să spun, având în vedere o cheie și un articol, sau două elemente, pot face o comparație cu acele chei. Aceste chei sunt aceleași? Cheia asta este mai mare decât aceasta? Este mai mic decât acesta? Acestea sunt singurele operațiuni pe care le fac cu ele. Spune, dacă cheile sunt numere, nu pot să mă uit la ce număr este acesta. Am doar să iau două chei și să le compar. Și de fapt, toți algoritmii de căutare pe care i-am văzut marți suntem algoritmi de sortare de comparație. Ceea ce ai făcut a fost trecut prin program. La un moment dat, ai ajuns la o ramură și te-ai uitat la două chei și te-ai ramificat în funcție de faptul dacă o cheie era mai mare decât alta. Asta a fost o comparație. Și apoi muți niște lucruri, dar asta era paradigma generală. Cele trei operațiuni de sortare au trăit în acest model de comparație. Aveți operații de comparație, cum ar fi sunt egale, mai mici decât, mai mari decât, poate mai mari decât sau egale, mai mici decât sau egale? În general, aveți toate aceste operațiuni pe care le puteți face... poate nu sunt egale. Dar lucrul cheie aici este că există doar două rezultate posibile pentru fiecare dintre acești comparatori. Există un singur lucru asupra căruia mă pot ramifica. Se va ramifica în două linii diferite. Fie este adevărat și fac un alt calcul, fie este fals și voi face un alt set de calcule. Are sens? Deci, ceea ce voi face este să vă ofer o comparație -- un algoritm în modelul de comparație ca ceea ce îmi place să numesc un arbore de decizie. Deci, dacă îți specific un algoritm, primul lucru pe care îl va face -- dacă nu compar deloc articolele, sunt oarecum înnebunit, pentru că nu voi putea spune niciodată dacă cheile mele sunt acolo sau nu. Așa că trebuie să fac niște comparații. Așa că voi face niște calcule. Poate aflu lungimea matricei și fac niște chestii în timp constant , dar, la un moment dat, voi face o comparație și voi ramifica. Voi ajunge la acest nod, iar dacă comparația-- poate mai puțin decât-- dacă este adevărată, voi merge în acest sens în calculul meu, iar dacă este falsă, voi merge în acest sens. calculul meu. Și voi continua să fac asta cu diverse comparații -- sigur-- până voi ajunge aici la vreo frunză în care nu mă ramific. Nodurile interne de aici reprezintă comparații, dar frunzele reprezintă... Mi-am oprit calculul. scot ceva. Are sens, ceea ce încerc să fac? Îmi schimb algoritmul pentru a fi pus într-un astfel de mod grafic, unde ramific ceea ce programul meu ar putea face pe baza comparațiilor pe care le fac. De fapt, nu număr restul muncii pe care le face programul. Chiar mă uit doar la comparații, pentru că știu că trebuie să compar unele lucruri până la urmă pentru a-mi da seama care sunt articolele mele. Și dacă doar așa pot distinge elementele, atunci trebuie să fac acele comparații pentru a afla. Are sens? În regulă, ceea ce am este un arbore binar care reprezintă comparațiile făcute de algoritm. BINE. Deci începe de la o comparație și apoi se ramifică. Câte frunze trebuie să am în copac? Ce înseamnă această întrebare, în ceea ce privește programul? PUBLIC: [INAUDIBIL] JASON KU: Ce se întâmplă? PUBLIC: Numărul de comparații-- JASON KU: Numărul de comparații-- nu, acesta este numărul de noduri interne pe care le am în algoritm. Și de fapt, numărul de comparații pe care le fac într-o execuție a algoritmului este doar de-a lungul unei căi de aici până la... până la o frunză. Deci, ce reprezintă de fapt frunzele? Acestea reprezintă ieșiri. Voi scoate ceva aici. Da? PUBLIC: [INAUDIBIL] JASON KU: Numărul de... OK. Deci, care este rezultatul algoritmului meu de căutare? Poate că este... un index al unui articol care conține această cheie. Sau poate returnez articolul este rezultatul - articolul obiectului pe care îl stochez. Și stochez n lucruri, așa că am nevoie de cel puțin n ieșiri, pentru că trebuie să pot returna oricare dintre elementele pe care le stochez pe baza unui parametru de căutare diferit, dacă va fi corect. De fapt, am nevoie de încă o ieșire. De ce am nevoie de încă o ieșire? Dacă nu este acolo -- deci orice algoritm de căutare a unei comparații corecte -- Fac niște comparații pentru a găsi acest lucru -- trebuie să aibă cel puțin n plus 1 frunze. Altfel, nu poate fi corect, pentru că l-aș putea căuta pe cel pe care nu îl returnez în acel set și nu ar putea niciodată să returneze acea valoare. Are sens? Da? PUBLIC: [INAUDIBIL] JASON KU: Ce este n? Pentru o structură de date, n este numărul de lucruri stocate în acea structură de date la acel moment, deci numărul de elemente din structura de date. Asta înseamnă în toate aceste tabele. Alte intrebari? OK, așa că acum ajungem la partea distractivă. Câte comparații trebuie să facă acest algoritm? Da, acolo sus... PUBLIC: [INAUDIBIL] JASON KU: Ce e? În regulă, colegul tău trece în față pentru o secundă, dar într-adevăr, trebuie să fac atâtea comparații în cel mai rău caz cât cea mai lungă cale de la rădăcină la frunză din acest arbore -- pentru că, pe măsură ce execut acest algoritm, am Voi coborî chestia asta, ramificându-mă mereu în jos și, la un moment dat, voi ajunge la o frunză. Și în cel mai rău caz, dacă se întâmplă să trebuiască să returnez această ieșire specială, atunci va trebui să merg pe cel mai lung lucru, doar pe calea cea mai lungă . Deci, cea mai lungă cale este aceeași cu înălțimea copacului, deci întrebarea devine, care este înălțimea minimă a oricărui arbore binar care are cel puțin n plus 1 frunze? Toată lumea înțelege de ce punem această întrebare? Da? PUBLIC: Ai putea din nou de ce are nevoie de n plus 1 frunze? JASON KU: De ce are nevoie de n plus 1 frunze -- dacă este un algoritm corect, trebuie să revină -- trebuie să poată returna oricare dintre cele n articole pe care le stochez sau să spună că cheia pe care o am Caut nu este acolo - mare întrebare. OK, deci care este înălțimea minimă a oricărui arbore binar care are n plus 1 - cel puțin n plus 1 frunze? De fapt, puteți afirma o recurență pentru asta și puteți rezolva asta. O să faci asta în recitarea ta. Dar este jurnalul n. Cel mai bun lucru pe care îl puteți face este dacă acesta este un arbore binar echilibrat. Deci, înălțimea minimă va fi de cel puțin log n înălțime. Sau înălțimea minimă este logaritmică, deci este de fapt theta chiar aici. Dar dacă aș spune doar înălțimea aici, aș limita mai jos înălțimea. Aș putea avea o înălțime liniară, dacă aș schimba comparațiile una câte una, dacă aș face o căutare liniară, de exemplu. Bine, deci asta înseamnă că, dacă mă limitez doar la comparații, trebuie să petrec cel puțin timp logaritmic pentru a putea afla dacă această cheie este în setul meu. Dar nu vreau timp logaritmic. vreau mai repede. Deci cum pot face asta? PUBLIC: [INAUDIBIL] JASON KU: Am o operație în modelul meu de calcul pe care l-am prezentat acum câteva săptămâni, care îmi permite să fac mai rapid, ceea ce îmi permite să fac ceva mai puternic decât comparațiile. Comparațiile au un factor de ramificare constant. În special, pot... dacă fac această operație... această operațiune în timp constant... mă pot ramifica în două locații diferite. Este ca o situație dacă... dacă, sau altfel. Și, de fapt, dacă aș avea un factor de ramificare constant pentru orice constantă aici - dacă aș avea trei sau patru, dacă ar fi mărginit de o constantă, înălțimea acestui arbore ar fi totuși delimitată de o bază logică, constanta acelui număr de frunze. Așa că am nevoie, într-un anumit sens, să pot ramifica o sumă neconstantă. Deci, cum pot ramifica o sumă neconstantă? Acest lucru este puțin complicat. Am avut această operațiune cu adevărat îngrijită în mașina cu acces aleatoriu pe care am putea merge aleatoriu în orice loc din memorie în timp constant, pe baza unui număr. A fost un lucru super puternic, pentru că într-o singură operațiune în timp constant, puteam să merg în orice spațiu din memorie. Acesta este potențial mult mai mare decât factorul de ramificare liniară, în funcție de dimensiunea modelului meu și de dimensiunea mașinii mele. Deci este o operațiune foarte puternică. Putem folosi asta pentru a găsi mai repede? Are cineva idei? Sigur. PUBLIC: [INAUDIBIL] JASON KU: Vom ajunge la hashing într-o secundă, dar acesta este un concept mai simplu decât hashing-- ceva cu care probabil ești deja familiarizat. Am cam folosit-o implicit în unele dintre lucrurile noastre cu structura de date secvențe. Ceea ce vom face este că, dacă am un articol care are cheia 10, voi păstra o matrice și voi stoca acel element la 10 spații distanță de partea din față a matricei, chiar la indexul 9 sau al 10-lea index. . Are sens? Dacă stochez acel articol în acea locație în memorie, pot folosi acest acces aleatoriu la acea locație și pot vedea dacă există ceva acolo. Dacă există ceva acolo, returnez acel articol. Are sens? Aceasta este ceea ce eu numesc o matrice de acces direct. Nu este cu adevărat diferit de matricele despre care am vorbit mai devreme în clasă. Avem o matrice și dacă am un articol aici cu cheia este egală cu 10, îl voi păstra aici pe locul 10. Acum, pot stoca doar un articol cu ​​cheia 10 în treaba mea și aceasta este una dintre prevederile pe care le aveam asupra structurilor noastre de date setate. Dacă am încercat să introducem ceva cu aceeași cheie ca ceva deja stocat acolo, vom înlocui elementul. Asta a fost semantica interfeței noastre setate. Dar este in regula. Acest lucru satisface condițiile interfeței noastre setate. Deci, dacă îl păstrăm acolo, este fantastic. Cât durează să găsim, dacă avem un articol cu ​​cheia 10? Este nevoie de timp constant, cel mai rău caz... grozav. Ce zici de inserarea sau ștergerea ceva? PUBLIC: [INAUDIBIL] JASON KU: Ce este asta? PUBLIC: [INAUDIBIL] JASON KU: Din nou, timp constant-- ne-am rezolvat toate problemele. Acest lucru este uimitor. BINE. Ce nu este uimitor la asta? De ce nu facem asta tot timpul? Da? PUBLIC: Nu știi cât de sus urcă cifrele. JASON KU: Nu știu cât de sus ajung cifrele. Deci, să presupunem că stochez, nu știu, un număr asociat cu acesta, cei 300 sau 400 dintre voi care sunteți în această clasă. Dar îți stochez ID-urile MIT. Cât de mari sunt acele numere? Sunt ca numere din nouă cifre, numere destul de lungi. Deci, ce ar trebui să fac... și dacă aș stoca cheile tale ca ID-uri MIT, aș avea nevoie de o matrice care să aibă indici care să acopere spațiul anvelopei de numere de nouă cifre. Este ca 10 la... 10 la 9. Mulțumesc. 10 până la 9 este dimensiunea unui drum de acces direct de construit pentru a putea folosi această tehnică pentru a crea o matrice de acces direct pentru a căuta pe ID-urile tale MIT, când sunteți doar 300 dintre voi aici. Deci 300 sau 400 este un n care este mult mai mic decât dimensiunea numerelor pe care încerc să le stochez. Ceea ce voi folosi ca variabilă pentru a vorbi despre dimensiunea numerelor pe care le stochez -- Voi spune u este dimensiunea maximă a oricărui număr pe care îl stochez. Este dimensiunea universului spațiului de chei pe care îl stochez. Are sens? OK, deci pentru a instanția o matrice de acces direct de acea dimensiune, trebuie să aloc acea cantitate de spațiu. Și deci, dacă este mult mai mare decât n, atunci sunt cam înșurubat, pentru că folosesc mult mai mult spațiu. Și aceste operațiuni de comandă sunt, de asemenea, proaste, pentru că în esență, dacă stochez aceste lucruri necontinuu, trebuie doar să scanez lucrurile pentru a găsi următorul element, de exemplu. OK, care este întrebarea ta? PUBLIC: Este o matrice cu acces direct o structură de date secvențe? JASON KU: O matrice de acces direct este o structură de date setată. De aceea este o interfață setată acolo sus. Colegul tău întreabă dacă poți folosi un accesoriu direct pentru a implementa un set... mă refer la o secvență. Și, de fapt, cred că veți vedea în notele voastre de recitare, aveți un cod care poate prelua o structură de date setată și implementa o structură de date secvență și poate lua structura de date secvență și implementează o structură de date setată . Pur și simplu nu vor avea neapărat un timp de rulare foarte bun. Deci, această semantică a matricei cu acces direct este într-adevăr bună pentru aceste operațiuni specifice de set. Are sens? Da? PUBLIC: Ce ești? JASON KU: u este dimensiunea celei mai mari chei pe care am voie să o stochez. Are sens? Matricea de acces direct acceptă chei de până la u. Are sens? OK, vom merge mai departe pentru o secundă. Asta e problema, nu? Când ai cea mai mare cheie-- presupunem aici numere întregi-- chei întregi-- deci în modelul de comparație, am putea stoca orice obiecte arbitrare care au suportat o comparație. Aici trebuie să avem chei întregi, altfel nu le vom putea folosi ca adrese. Deci facem o presupunere cu privire la intrări că acum pot stoca numai numere întregi. Nu pot stoca obiecte arbitrare - articole cu chei. Și, în special, trebuie, de asemenea, să-- aceasta este o subtilitate care este în cuvântul RAM model-- cum pot fi sigur că aceste chei pot fi căutate în timp constant? Am acest mic procesor. Are un număr de registre pe care poate acționa. Cât de mari sunt acele registre? PUBLIC: [INAUDIBIL] JASON KU: Ce? Momentan, sunt pe 64 de biți, dar, în general, sunt w. Au dimensiunea cuvântului tău pe mașina ta. 2 la w este numărul de rochii pe care le pot accesa. Dacă voi putea folosi acest accesoriu direct, trebuie să mă asigur că u este mai mic de 2 la w, dacă vreau ca aceste operații să ruleze în timp constant. Dacă am copii care sunt mult mai mari decât asta, va trebui să fac altceva, dar aceasta este un fel de presupunere. În această clasă, atunci când vă oferim o matrice de numere întregi, sau o matrice de șiruri de caractere, sau ceva de genul ăsta în problema dvs. sau la un examen, presupunerea este că, cu excepția cazului în care vă dăm limite cu privire la dimensiunea acelor lucruri, cum ar fi numărul de caractere din șirul dvs. sau dimensiunea numărului din-- puteți presupune că acele lucruri se vor încadra într-un cuvânt de memorie. w este dimensiunea cuvântului mașinii dvs., numărul de biți pe care mașina dvs. poate efectua operațiuni în timp constant. Alte intrebari? OK, deci avem această problemă. Folosim mult prea mult spațiu, când avem un univers mare de taste. Deci, cum ocolim această problemă și orice idee? Sigur. PUBLIC: În loc de [INAUDIBIL].. JASON KU: OK, deci ceea ce spune colegul tău-- în loc să stochezi doar o valoare în fiecare loc, poate stoca mai mult de o valoare. Dacă folosim această idee, în care îmi stochez cheia la indexul cheii, asta înseamnă că trebuie să avem chei unice în structura noastră de date. Nu rezolvă această problemă de utilizare a spațiului. Are sens? Vom ajunge să stocăm mai multe lucruri la indici, dar există un alt truc pe care îl caut acum. Avem mult spațiu pe care ar trebui să-l alocăm pentru această structură de date. Care este o alternativă? În loc să alocăm mult spațiu, alocam mai puțin spațiu. Să alocăm mai puțin spațiu. În regulă. Acesta este spațiul nostru de chei, u. Dar, în schimb, vreau să stochez acele lucruri într-o matrice cu acces direct de dimensiunea n, ceva ca ordinea lucrurilor pe care le voi stoca. Mă voi relaxa și voi spune că vom face din aceasta o lungime m care să fie în jur de dimensiunea lucrurilor pe care le depozitez. Și ceea ce voi face este să încerc să cartografiaz acest spațiu de taste - acest spațiu mare de taste, de la 0 la u minus 1 sau ceva de genul -- pentru a aranja acel spațiu de la 0 la m minus 1. Voi dori o funcție-- asta este ceea ce voi numi h-- care mapează acest interval la un interval mai mic. Are sens? Voi avea o funcție care să ia baza aceea mare de taste -- le lipește aici. Și în loc să mă uit la un index al cheii, voi pune cheia prin această funcție, spațiul cheii, într-un spațiu comprimat și o voi stoca în acea locație de index. Are sens? Sigur. PUBLIC: [INAUDIBIL] JASON KU: Colegul tău este... vine cu întrebarea pe care urma să o pun imediat, care era, care este problema aici? Problema este că este potențialul pe care am putea fi... trebuie să stocăm mai mult de un lucru în aceeași locație de index. Dacă am o funcție care se potrivește cu acest spațiu mare până la acest spațiu mic, trebuie să am mai multe dintre aceste lucruri să meargă în aceleași locuri aici, nu? Nu poate fi obiectiv. Dar doar pe baza principiului porumbeilor, am mai multe din aceste lucruri. Cel puțin doi dintre ei trebuie să meargă la ceva aici. De fapt, dacă am, să zicem, u este mai mare decât n pătrat, de exemplu, acolo-- pentru orice funcție pe care ți-o dau care mapează acest spațiu mare până la spațiul mic, n dintre aceste lucruri se vor mapa în același loc. Deci, dacă aleg o funcție proastă aici, atunci va trebui să stochez n lucruri în aceeași locație de index. Și dacă merg acolo, trebuie să verific dacă vreunul dintre acestea sunt lucrurile pe care le caut. Nu am câștigat nimic. Îmi doresc foarte mult o funcție hash care să distribuie uniform cheile în acest spațiu. Are sens? Dar avem o problemă aici. Dacă trebuie să stocăm mai multe lucruri într-o anumită locație în memorie, nu putem face asta. Am un lucru pe care îl pot pune acolo. Așa că am două opțiuni despre cum să rezolv... ceea ce eu numesc coliziuni. Dacă am două elemente aici, cum ar fi a și b, acestea sunt chei diferite în universul meu de spațiu. Dar este posibil ca amândoi să se mapeze la un hash care are aceeași valoare. Dacă mai întâi așez a, iar a este-- pun a acolo, unde pun b? Există două opțiuni. PUBLIC: A doua structură de date este [INAUDIBILĂ] astfel încât să poată stoca [INAUDIBILĂ]? JASON KU: OK, deci ceea ce spune colegul tău -- pot stoca aceasta este o listă conectată și apoi pot doar să insert un tip chiar lângă locul în care a fost? Care este problema acolo? Sunt bune listele legate cu acces direct de către un index? Nu, sunt groaznice cu get_at și set_at Au nevoie de timp liniar acolo. Deci, într-adevăr, scopul direct al acestui tablou este că există o matrice dedesubt și pot face această aritmetică a indexului și să merg la următorul lucru. Deci chiar nu vreau să înlocuiesc o listă legată ca această structură de date. Da? Care-i treaba? PUBLIC: [INAUDIBIL] JASON KU: Putem face asta cu adevărat puțin probabil. Sigur. Nu știu ce înseamnă probabil, pentru că vă ofer o funcție hash-- o funcție hash. Și nu știu care sunt intrările. Da? Daţi-i drumul. PUBLIC: [INAUDIBIL] JASON KU: OK, corect. Deci, există de fapt două soluții aici. Unul este I-- poate, dacă aleg m să fie mai mare decât n, va fi spațiu suplimentar aici. Îl voi lipi în altă parte în matricea existentă. Cum găsesc un spațiu deschis este puțin complicat, dar aceasta este o tehnică numită adresare deschisă, care este mult mai comună decât tehnica despre care vom vorbi astăzi în implementări. Python folosește o schemă de adresare deschisă , care este, în esență, găsirea unui alt loc în matrice pentru a pune această coliziune. Adresarea deschisă este notoriu dificil de analizat, așa că nu vom face asta în această clasă. Există o tehnică mult mai ușoară care-- avem o implementare pentru tine în fișele de recitare. Este ceea ce spunea colegul tău de aici, nu-l găsesc... acolo , în loc să- l stocheze în altă parte în matricea de acces direct existentă aici, pe care o numim de obicei tabelul hash-- în loc de stocând-o altundeva în acel tabel hash, în schimb, la acea cheie, vom stoca un pointer către o altă structură de date, o altă structură de date care poate stoca o grămadă de lucruri - la fel ca orice structură de date secvențe , ca o matrice dinamică , sau lista legată, sau orice altceva în regulă. Tot ce trebuie să fac este să fiu capabil să lipesc o grămadă de lucruri acolo atunci când au loc coliziuni, iar apoi, când mă voi ridica să caut acel lucru, mă voi uita prin toate lucrurile din acea structură de date și voi vedea dacă cheia mea există. Are sens? Acum, vrem să ne asigurăm că acele structuri de date suplimentare , pe care le voi numi lanțuri, vrem să ne asigurăm că acele lanțuri sunt scurte. Nu vreau să fie lungi. Deci ceea ce voi face este că, când voi avea această coliziune aici, în schimb voi avea un indicator către niște -- nu știu -- poate să o fac o matrice dinamică, sau o listă legată sau ceva de genul acea. Și voi pune un aici și voi fi aici. Și apoi mai târziu, când caut cheia K, sau caut a sau b-- hai să căutăm în sus b-- voi merge la această valoare hash aici. Îl voi trece prin funcția hash. Voi merge la acest index. Voi merge la structura de date, lanțul asociat acelui index și mă voi uita la toate aceste elemente. O să fac doar o descoperire liniară. o sa ma uit. Aș putea pune orice structură de date aici, dar mă voi uita la aceasta, să văd dacă este b. Nu este b. Uită-te la asta... este b. revin da. Are sens? Deci aceasta este o idee numită înlănțuire. Pot pune orice vreau acolo. În mod obișnuit, vorbim despre plasarea unei liste legate acolo, dar puteți pune o matrice dinamică acolo. Puteți pune o matrice sortată acolo pentru a fi mai ușor să verificați dacă cheia este acolo. Poti pune orice vrei acolo. Scopul acestei prelegeri va încerca să arate că există o alegere a funcției hash pe care o pot face, care să mă asigur că aceste lanțuri sunt mici, astfel încât să nu conteze cum le-am văzut acolo, pentru că pot doar-- dacă există un număr constant de lucruri stocate acolo, pot doar să le privesc pe toate și să fac ce vreau și să obțin în continuare timp constant. Da? PUBLIC: Deci asta înseamnă că, atunci când aveți [INAUDIBIL], să spunem doar, dintr-un motiv oarecare, numărul de lucruri [INAUDIBILE] este că cele mai multe dintre ele obțin mai multe [INAUDIBILE].. Este doar o structură de date care ține doar un lucru? JASON KU: Da. Deci, ceea ce spune colegul tău este, la inițializare, ce este stocat aici? Inițial, indică o structură de date goală. Am de gând să inițialez toate aceste lucruri pentru a avea... acum, ai niște cheltuieli generale aici. Plătim ceva pentru asta - ceva spațiu suplimentar și avem pointer și altă structură de date pentru toate aceste lucruri. Sau ați putea avea semantica în care, dacă am un singur lucru aici, voi stoca acel lucru în această locație, dar dacă am mai multe, indică o structură de date. Acestea sunt un fel de detalii complicate de implementare, dar obțineți ideea de bază. Dacă am doar o structură de date de dimensiune 0 la toate aceste lucruri, voi avea totuși un factor constant. Încă va fi o structură de date de dimensiune liniară, atâta timp cât m este liniar în n. Are sens? BINE. Deci, cum alegem o funcție hash bună? Ți-am spus deja că orice funcție de hash fixă ​​pe care ți-o ofer va experimenta coliziuni. Și dacă u este mare, atunci există posibilitatea ca I-- pentru o anumită intrare, toate lucrurile din setul meu să meargă direct la aceeași valoare a indicelui hashed. Deci nu e grozav. Să ignorăm asta pentru o secundă. Care este cel mai simplu mod de a coborî din acest spațiu mare de taste la unul mic? Care este cel mai ușor lucru pe care l-ai putea face? Da? PUBLIC: [INAUDIBIL] JASON KU: Modulus-- grozav. Aceasta se numește metoda diviziunii. Și care este funcția sa este, în esență, că va lua o cheie și va spune egal cu K mod m. Am de gând să ocup ceva de un spațiu mare și o să-l modific astfel încât să se înfășoare în jur -- un lucru perfect valabil de făcut. Satisface ceea ce facem într-un tabel hash. Și dacă copiii mei sunt distribuiti complet uniform -- dacă, când folosesc funcția mea hash , toate cheile de aici sunt distribuite uniform pe acest spațiu mai mare, atunci de fapt, acesta nu este un lucru atât de rău. Dar asta înseamnă să impun un fel de cerințe de distribuție asupra tipului de intrări pe care am voie să le folosesc cu această funcție hash pentru ca aceasta să aibă performanțe bune. Dar acest lucru plus un pic de amestecare suplimentară și manipulare a biților este în esență ceea ce face Python. În esență, tot ceea ce face este să amestece cheia pentru o cantitate fixă ​​de amestecuri, apoi să o modifice și să o lipească acolo. Este codificat greu în biblioteca Python, care este această funcție hash și, prin urmare, există câteva secvențe de inserări într-un tabel hash în Python, care vor fi foarte proaste în ceea ce privește performanța, deoarece aceste legături de lanț reprezintă numărul de coliziuni pe care le am Vom ajunge la un singur hash va fi mare. Dar fac asta din alte motive. Ei vor o funcție hash deterministă. Ei vor ceva ca să fac programul din nou -- va face același lucru dedesubt. Dar uneori Python înțelege greșit. Dar dacă datele dvs. pe care le stocați sunt suficient de necorelate cu funcția hash pe care au ales-o -- ceea ce, de obicei, este -- aceasta este o performanță destul de bună. Dar aceasta nu este o clasă practică. Ei bine, este o clasă practică, dar unul dintre lucrurile pe care noi suntem... acesta este accentul acestei clase este să ne asigurăm că putem demonstra că acest lucru este bun și în teorie. Nu vreau să știu că uneori asta va fi bine. Chiar vreau să știu că, dacă aleg -- dacă fac această structură de date și pun niște intrări pe ea, vreau un timp de rulare care să fie independent de ce intrări am decis să folosesc, independent de ce chei am decis să stochez . Are sens? Dar este imposibil pentru mine să aleg o funcție hash fixă ​​care să realizeze acest lucru, pentru că tocmai v- am spus că, dacă u este mare-- acesta este u-- dacă u este mare, atunci există intrări care mapează totul într-un singur loc. Sunt înnebunit, nu? Nu există nicio modalitate de a rezolva această problemă. Este adevărat dacă vreau o funcție hash deterministă - vreau ca lucrul să fie repetabil, să facă același lucru iar și iar pentru orice set de intrări. Ce pot face în schimb? Slăbiți-mi noțiunea despre ce înseamnă timpul constant pentru a face mai bine-- OK, folosiți un non-determinist-- ce înseamnă non-determinist? Înseamnă să nu alegeți o funcție hash din față - alegeți una aleatoriu mai târziu. Așa că utilizatorul -- aleg orice intrări pe care le vor face, iar apoi voi alege o funcție hash la întâmplare. Ei nu știu ce funcție hash voi alege, așa că le este greu să- mi ofere o intrare care este proastă. Voi alege o funcție hash aleatorie. Pot alege o funcție hash din spațiul tuturor funcțiilor hash? Care este spațiul tuturor funcțiilor hash din această formă? Pentru fiecare dintre aceste valori, dau o valoare aici. Pentru fiecare dintre aceste numere aleatoare independent între acest interval, câte astfel de funcții hash există? m la acest număr... sunt multe lucruri. Deci nu pot face asta. Ce pot face este să repar o familie de funcții hash în care, dacă aleg una dintre-- aleatoriu, obțin performanțe bune. Și așadar, funcția hash pe care o voi folosi și pe care o vom petrece restul timpului este ceea ce eu numesc o funcție hash universală. Îndeplinește ceea ce numim o proprietate hash universală - deci funcția hash universală. Și aceasta este o nomenclatură puțin ciudată, pentru că vă definesc aceasta ca funcție hash universală, dar de fapt, universal este un descriptor. Există multe funcții hash universale. Acesta se întâmplă să fie un exemplu al unuia dintre ei. BINE? Deci, iată funcția hash -- nu arată chiar atât de diferit. Doamne binevoitoare-- câte paranteze sunt-- mod p, mod m. BINE. Așa că face același lucru cu ceea ce se întâmplă aici, dar înainte de a modifica cu m, îl înmulțesc cu un număr, adaug un număr, îl iau mod alt număr și apoi sunt ajungând de m. Acest lucru este puțin ciudat. Și nu numai atât, aceasta este încă o funcție hash fixă. Nu vreau asta. Vreau să generalizez aceasta pentru a fi o familie de funcții hash, care sunt acest habk pentru o alegere aleatorie a, b în acest interval mai mare. Bine, aceasta este o mulțime de notații aici. În esență, ceea ce se spune este că am o familie. Este parametrizat de lungimea funcției mele hash și de un prim fix aleatoriu mare care este mai mare decât u. Voi alege un număr prim mare și asta va fi rezolvat când voi face tabelul hash. Și apoi, când instanțiez tabelul hash, voi alege aleatoriu unul dintre aceste lucruri, alegând un a și un b aleatoriu din acest interval. Are sens? PUBLIC: [INAUDIBIL] JASON KU: Acesta nu este egal cu 0. Dacă aș avea 0 aici, pierd informațiile cheie și asta nu este bun. Are vreun sens? Deci, ceea ce face acest lucru este înmulțirea acestei chei cu un număr aleatoriu, adăugarea unui număr aleatoriu, modificarea cu acest prim și apoi modificarea cu dimensiunea lucrurii mele. Așa că face o grămadă de amestecuri și există o oarecare aleatorie implicată aici. Aleg funcția hash alegând aleatoriu un a, b din acest lucru. Așa că, când îmi pornesc programul, voi instanția acest lucru cu niște a și b aleatorii, nu în mod determinist. Utilizatorul, când folosește acest lucru, nu știe ce a și b am ales, așa că este foarte greu pentru ei să-mi dea un exemplu prost. Și această funcție universală de hash-- această familie universală de hash, să spunem-- într-adevăr, aceasta este o familie de funcții, iar eu aleg una aleatoriu în acea familie-- este universală. Și universalitatea spune că... care este proprietatea universalității? Înseamnă că probabilitatea, prin alegerea unei funcții hash din această familie hash, ca o anumită cheie să se ciocnească de o altă cheie este mai mică sau egală cu 1/m pentru toate -- orice două chei diferite din universul meu. Are sens? Practic, acest lucru are proprietatea că, dacă am aleatoriu-- pentru oricare două chei pe care le aleg în spațiul meu univers, dacă aleg aleatoriu o funcție hash, probabilitatea ca aceste lucruri să se ciocnească este mai mică de 1/m. De ce e bine? Aceasta este, într-un anumit sens, o măsură a cât de bine distribuite sunt aceste lucruri. Vreau ca aceste lucruri să se ciocnească cu o probabilitate de 1/m, astfel încât aceste lucruri să nu se ciocnească foarte -- nu este foarte probabil ca aceste lucruri să se ciocnească. Are sens? Deci vrem dovada că această familie de hașiș satisface această proprietate de universalitate. Veți face asta în 046. Dar putem folosi acest rezultat pentru a arăta că, dacă folosim o familie universală-- această familie universală de hash, că lungimea lanțurilor noastre de schimbare-- este de așteptat să fie de lungime constantă. Deci vom folosi această proprietate pentru a demonstra asta. Cum dovedim asta? Vom face o mică probabilitate. Deci cum vom demonstra asta? Voi defini o variabilă aleatoare, o variabilă aleatorie indicator. Își amintește cineva ce este un indicator într-o variabilă? Da, este o variabilă care, cu o anumită probabilitate, este 1 și 1 minus acea probabilitate este 0. Așa că voi defini această variabilă aleatorie indicator xij este o variabilă aleatoare la alegerea mea -- la alegerea unui hash funcția în familia mea. Și ce înseamnă asta? Înseamnă că xij este egal cu 1, dacă hash Ki este egal cu hKj -- aceste lucruri se ciocnesc -- și 0 în caz contrar. Așa că aleg la întâmplare peste această familie de hașiș. Dacă, pentru două chei-- tasta i și și j-- dacă aceste lucruri se ciocnesc, acesta va fi 1. Dacă nu, atunci este 0. OK? Atunci, cum putem scrie o formulă pentru lungimea unui lanț în acest model? Deci dimensiunea unui lanț-- sau să o punem aici-- dimensiunea lanțului la i-- la i în tabelul meu hash-- va fi egală-- Voi numi asta variabila aleatoare xi- - asta va egala suma peste j este egală cu 0 la-- ce este-- peste, cred, u minus 1 de însumare-- sau scuze-- de xij. Deci, practic, dacă repar această locație i, aici merge cheia. Îmi pare rău. Aceasta este dimensiunea lanțului la h de Ki. Îmi pare rău. Așa că mă uit la oriunde merge Ki este hashed și văd câte lucruri se ciocnesc cu el. Însumez toate aceste lucruri, pentru că acesta este 1 dacă există o coliziune și 0 dacă nu există. Are sens? Deci aceasta este dimensiunea lanțului la locația indexului mapată de Ki. Deci iată unde intervine probabilitatea ta. Care este valoarea așteptată a lungimii acestui lanț față de alegerea mea aleatoare? Valoarea așteptată a alegerii unei funcții hash din această familie hash universală de această lungime a lanțului -- pot pune în definiția mea aici. Aceasta este valoarea așteptată a însumării peste j a lui xij. Ce știu despre așteptări și însumări? Dacă aceste variabile sunt independente una de cealaltă... PUBLIC: [INAUDIBIL] JASON KU: Spune ce? PUBLIC: [INAUDIBIL] JASON KU: Linearitatea așteptărilor-- practic, suma așteptărilor acestor variabile aleatoare independente este aceeași cu suma așteptărilor lor. Deci aceasta este egală cu însumarea peste j a așteptărilor acestor persoane individuale. Unul dintre aceste j este același cu i. j face bucle peste toate lucrurile de la 0 la u minus 1. Unul dintre ele este i, deci când xhi este hj, care este valoarea așteptată pentru care se ciocnesc? 1-- deci voi refactoriza acest lucru ca fiind acesta, unde j nu este egal cu i, plus 1. Oamenii sunt de acord cu asta? Pentru că dacă i este egal, dacă j și i sunt egali, cu siguranță se ciocnesc. Sunt aceeași cheie. Așa că sunt de așteptat să am un tip acolo, care era cheia originală, xi. Dar altfel, putem folosi această proprietate universală care spune, dacă nu sunt egali și se ciocnesc -- care este exact acest caz -- probabilitatea ca acest lucru să se întâmple este de 1/m. Și, deoarece este o variabilă aleatorie indicator, așteptarea este că există rezultate înmulțite cu probabilitățile lor - deci de 1 ori acea probabilitate plus 0 ori 1 minus acea probabilitate, care este doar 1/m. Deci acum obținem suma 1/m pentru j nu este egal cu i plus 1. Oh, și asta-- îmi pare rău. Am făcut asta greșit. Acesta nu ești tu. Acesta este n. Stocăm n chei. Bine, deci acum fac o buclă peste j-- asta peste toate aceste lucruri. Câte lucruri sunt? n minus 1 lucruri, nu? Deci, acesta ar trebui să fie egal cu 1 plus n minus 1 peste m. Așa că asta ne oferă universalitatea. Deci, atâta timp cât alegem ca m să fie mai mare decât n, sau cel puțin liniar în n, atunci ne așteptăm ca lungimile lanțului nostru să fie constante, deoarece acest lucru devine o constantă dacă m este cel puțin de ordinul n. Are sens? BINE. Ultimul lucru cu care vă voi lăsa este, cum facem acest lucru dinamic? Dacă creștem numărul de lucruri pe care le stocăm în acest lucru, este posibil ca, pe măsură ce creștem n pentru un m fix, acest lucru să nu mai fie... m să nu mai fie liniar în n, nu? Ei bine, atunci tot ce trebuie să facem este, dacă ajungem prea departe, reconstruim întregul lucru - întregul tabel hash cu noul m, la fel cum am făcut cu o matrice dinamică. Și poți dovedi... nu vom face asta aici, dar poți dovedi că nu vei face acea operație prea des, dacă redimensionezi în mod corect. Și așa doar reconstruiți complet după un anumit număr de operațiuni. OK, deci asta e hashing. Săptămâna viitoare, vom vorbi despre o variantă mai rapidă.