[REPRODUCCIÓ DE MÚSICA] DOUG LLOYD: A hores d'ara ja saber molt sobre les matrius, i vostè sap molt sobre llistes enllaçades. I hem discutir la pros i contres, hem discutit que unia les llistes pot aconseguir més gran i més petit, però ocupen més grandària. Les matrius són molt més fàcils de utilitzen, però són restrictius en la mesura ja que hem d'ajustar la mida de la matriu des del principi i després ens peguen amb ella. 

Però això és, tenim més o menys esgotat tots els nostres temes sobre llistes enllaçades i matrius. O tenim? Potser puguem fer alguna cosa encara més creatiu. I aquest tipus de prestació la idea d'una taula hash. 

Així que en una taula hash que tractarem combinar una matriu amb una llista enllaçada. Anem a prendre les avantatges de la matriu, com d'accés aleatori, ser capaç d'anar a la matriu element 4 o matriu element agost sense haver de recórrer a través. Això és bastant ràpid, oi? 

Però també volem tenir les nostres dades estructura de poder créixer i encongir-se. No necessitem, no ho fem volen ser restringit. I nosaltres volem ser capaços per afegir i treure coses molt fàcilment, el que si vostè recorda, és molt complex amb una matriu. I podem cridar a això El nou una taula hash. 

I si s'aplica correctament, estem espècie de prendre els avantatges d'ambdós dades estructures que ja has vist, matrius i llistes enllaçades. La inserció pot començar a tendir cap a theta d'1. Theta no hem discutit realment, però theta és només el cas mitjana, el que en realitat va a succeir. No sempre vas a tenir el pitjor dels casos, i no sempre tindràs el millor dels casos, així que quina és l'escenari mitjana? 

Bé una inserció mitjana en una taula hash pot començar a acostar-se a la constant de temps. I eliminació pot aconseguir prop de constant de temps. I les operacions de recerca pot obtenir prop de constant de temps. Això és-- no tenim una dada estructura fins ara que pot fer això, pel que aquest ja sona com un molt gran cosa. Realment hem mitigat els desavantatges de cada un pel seu compte. 

Per obtenir aquest rendiment actualitzar però, ens necessitat de repensar com afegim les dades en l'estructura. Específicament volem que el sí les dades que ens digui on ha d'anar en l'estructura. I si després hem de veure si està en l'estructura, si hem de trobar-lo, volem mirar les dades de nou i ser capaç d'eficàcia, utilitzant les dades, accedir aleatòriament ella. Només mirant a la dades que hem de tenir una idea d'on exactament estem anar a trobar-lo en la taula hash. 

Ara el desavantatge d'un hash taula és que són realment bastant malament en ordenar o classificar les dades. I de fet, si s'inicia utilitzar-los per demanar o ordenar les dades es perd tota la avantatges prèviament tingut en termes d'inserció i eliminació. El temps es converteix en més a prop de theta de n, i hem bàsicament retrocedit en una llista enllaçada. I pel que només volem utilitzar de hash taules si no importen si les dades s'ordena. Per al context en el qual que farem servir en CS50 és probable que no importa que les dades es classifiquen. 

Així que una taula hash és una combinació de dues peces diferents amb la qual estem familiaritzats. La primera és una funció, la qual que se sol anomenar una funció hash. I aquesta funció hash va tornar algun enter no negatiu, que que se sol anomenar un codi hash, OK? La segona peça és una matriu, que és capaç d'emmagatzemar dades del tipus que que voleu posar en l'estructura de dades. Anem a mantenir-se a distància de la vinculat llista d'elements de moment i acaba de començar amb els fonaments d'un hash de taula per aconseguir el seu cap al voltant d'ella, i després anem a aquest bufem la teva ment una mica quan ens combinar les matrius i llistes d'enllaços junts. 

La idea bàsica encara és que prenem algunes dades. Correm que les dades a través de la funció hash. I així es processen les dades i escup un nombre, d'acord? I després amb aquest nombre només emmagatzemem les dades volem emmagatzemar a la array en aquesta ubicació. Així per exemple tenim potser aquesta taula hash de cadenes. Té 10 elements en ell, així podem encaixar 10 cordes al mateix. 

Diguem que volem per discutir Joan. Així que Joan com les dades que volem inserir en aquesta taula hash en algun lloc. On el posem? Bé típicament amb un gamma fins ara és probable ho posaria en un lloc matriu 0. Però ara tenim aquesta nova funció hash. 

I diguem que correm John a través d'aquesta funció hash i es escup 4. Bé, això és on som voldrà posar John. Volem posar a en Pep a lloc array 4, perquè si hash John nou-- diguem més tard voleu cercar i veure si John existeix en aquest hash table-- tot el que necessitem fer s'executa a través de el mateix hash funció, obtenir el número 4, i ser capaç de trobar John immediatament en la nostra estructura de dades. Això és bastant bo. 

Diguem que ara fem de nou, volem hash de Pablo. Volem afegir Paul en aquesta taula hash. Diguem que en aquesta ocasió es corre Paul a través de la funció hash, el codi hash que es genera és 6. Bé, ara podem posar Paul en la ubicació matriu juny. I si hem de mirar cap amunt si Paul és en aquesta taula hash, tot el que necessitem fer és executar Paul a través de la funció hash de nou i anem a aconseguir 6 de nou. 

I llavors només mirem en la localització matriu juny. És Paul allà? Si és així, està a la taula hash. És Pau no existeix? No està en la taula hash. És bastant senzill. 

Ara com es defineix una funció hash? Bé realment no hi ha límit a la nombre de possibles funcions de hash. De fet hi ha un nombre de realitat, realment bons a l'Internet. Hi ha una sèrie de realitat, els realment dolents a l'Internet. També és bastant fàcil escriure una dolenta. 

Llavors, què fa que una bona funció hash, oi? Bé una bona funció hash ha de utilitzen només les dades que es hash, i totes les dades que s'estan hash. Així que no volem utilitzar anything-- no incorporem res més a part de les dades. I volem utilitzar totes les dades. No volem utilitzar només una peça de la mateixa, volem utilitzar tot. Una funció hash ha de també ser determinista. Què vol dir això? Bé, significa que cada vegada que passar la mateixa peça exacta de les dades en la funció hash sempre obtenir el mateix codi hash a terme. Si pas John al funció hash de sortir 4. Jo hauria de ser capaç de fer això 10000 vegades i sempre obtindrà 4. Així que no hi ha números aleatoris eficaçment poden participar en el nostre picada tables-- en les nostres funcions hash. 

Una funció hash ha també distribuir uniformement dades. Si cada vegada que executi dades a través del funció hash a obtenir el codi hash 0, que probablement no és tan gran, no? Vostè probablement voldrà gran una sèrie de codis hash. També les coses es poden propagar al llarg de la taula. I també seria genial si realment dades similars, com John i Jonathan, potser es van estendre a sospesar diferents ubicacions a la taula hash. Això seria un bon avantatge. 

Heus aquí un exemple d'una funció hash. Vaig escriure aquest un abans. No és un particular bona funció hash per raons que realment no suportar entrar en aquest moment. Però, ¿veus el que està passant aquí? Sembla com que estem declarant una variable anomenada suma i s'estableix igual a 0. I després aparentment estic fent alguna cosa sempre que strstr [j] no és igual a 0 barra invertida. Què estic fent allà? 

Això és bàsicament només un altre forma d'implementar [? STRL?] i detectar quan has arribat al final de la cadena. Així que no tinc que realment calcular la longitud de la cadena, Només estic fent servir quan pols el barra invertida 0 caràcters sé He arribat al final de la cadena. I llavors jo seguiré iteració a través d'aquesta cadena, afegint strstr [j] per resumir, i després a la final del dia va a tornar suma mod HASH_MAX. 

Bàsicament tot aquest hash funció està fent és sumar tots els valors ASCII de la meva corda, i llavors és tornar algun codi hash MODDED per HASH_MAX. És probablement la mida de la meva sèrie, no? No vull estar rebent de hash codis si el meu arsenal és de grandària 10, Jo no vull ser aconseguir codis hash fora 11, 12, 13, no puc posar les coses en aquests llocs de la matriu, això seria il·legal. Jo pateixo un error de segmentació. 

Ara aquí és una altra ràpida a un costat. En general, vostè està probablement no va a vol escriure les seves pròpies funcions hash. En realitat, és una mica de un art, no una ciència. I hi ha molt que va en ells. L'Internet, com he dit, és plena de molt bones funcions hash, i vostè ha d'utilitzar l'Internet per trobar funcions hash perquè és realment només una mica d'una innecessària pèrdua de temps per crear el seu propi. 

Vostè pot escriure els simples per a propòsits de prova. Però quan realment es va a iniciar hashing de dades i el seu emmagatzematge en una taula hash estàs probablement voldrà utilitzar alguna funció que s'ha generat per a vostè, el que hi ha a Internet. Si només vos per citar les seves fonts. No hi ha raó per plagiar res aquí. 

La comunitat de la informàtica és sens dubte creixent, i realment els valors de codi obert, i és molt important per citar les seves fonts perquè la gent pot obtenir l'atribució de el treball que estan fent en benefici de la comunitat. Així que sempre sure-- i no només per haixix funcions, però generalment quan utilitzar el codi d'una font externa, sempre citar la seva font. Donar crèdit a la persona que ho va fer alguns dels treballs de manera que no han de. 

OK, així que anem a revisar aquest taula hash per a un segon. Aquí és on ens vam anar després inserim John i Paul en aquesta taula hash. ¿Veu vostè algun problema? És possible que vegi dues. Però, en particular, oi veure a aquest possible problema? 

Què faig si hash Ringo, i Resulta que després de processar que les dades a través de la funció hash Ringo també ha generat el codi hash juny. Ja tinc les dades a ubicació matriu hashcode-- juny. Així que probablement va a ser una mica d'un problema per a mi, no? 

D'això en diem una col·lisió. I la col·lisió es produeix quan dues peces de dades passen pel mateix hash funció va donar el mateix codi hash. És de suposar que encara volem aconseguir tant peces de dades en la taula hash, en cas contrari no estaríem corrent Ringo arbitràriament a través de la funció hash. Presumiblement Volem arribar Ringo en aquesta matriu. 

Com ho fem però, si i Paul tant el rendiment codi hash juny? No volem sobreescriure Pau, volem Pau a ser-hi també. Així que hem de trobar una manera d'aconseguir elements en la taula hash que encara conserva la nostra ràpida inserció i ràpida mirada cap amunt. I una manera de tractar amb ell és fer una cosa anomenada sondeig lineal. 

Usant aquest mètode si tenim una col·lisió, bé, ¿què fem? Bé, no el podem posar a la localització matriu 6, o el que sigui codi hash es va generar, anem a posar-lo en codi hash més 1. I si això és let està ple el va posar en codi hash més 2. El benefici d'aquest ésser, si ell és no exactament on creiem que ell és, i hem de començar a buscar, potser no hem d'anar molt lluny. Potser no hem de buscar tots els n elements de la taula hash. Potser hem de buscar un parell d'ells. 

I així seguim tendint cap aquest cas mitjana és de prop d'1 vs a prop de n, de manera que potser això funcionarà. Així que anem a veure com això podria funcionar en la realitat. I veurem si tal vegada puguem detectar el problema que pugui passar aquí. 

Diguem que hash Bart. Així que ara anem a córrer un nou conjunt de cadenes a través de la funció hash, i correm Bart mitjançant el hash funció, obtenim codi hash juny. Fem una ullada, veiem 6 és buit, perquè puguem posar Bart allà. 

Ara HASH Lisa i que també genera codi hash juny. Bé, ara que estem utilitzant aquest lineal mètode comencem a les 6 de sondeig, veiem que 6 és completa. No podem posar Lisa en 6. Llavors, on anem? Anem a 7. 7 de buit, així que funciona. Així que posarem Lisa allà. 

Ara HASH Homer i obtenim 7. OK, així que sabem que el 7 de plena Ara, el que no podem posar Homer allà. Així que anirem a 8. És agost disponibles? Sí, i de 8 prop de 7, així que si hem de començar a buscar som No va a haver d'anar massa lluny. I així anem a posar Homer a les 8. 

Ara HASH Maggie i retorna 3, gràcies a Déu som capaços de simplement posar Maggie allà. No hem de fer cap espècie de sondeig per això. Ara HASH Marge, i Marge també retorna juny. 

Bé 6 és completa, 7 és completa, 8 és completa, 9, gràcies bé Déu, 9 està buida. Puc posar Marge a les 9. Ja podem veure que estem començant tenir aquest problema pel qual ara estem començant a estirar coses tipus de lluny dels seus codis hash. I això theta d'1, aquesta mitjana cas de ser constant de temps, està començant a aconseguir una mica més-- començant a cuidar una mica més cap theta de n. Estem començant a perdre aquest avantatge de taules hash. 

Aquest problema que acabem de veure és una cosa que es diu l'agrupació. I el que és realment malament per agrupació és que una vegada que ara tenir dos elements que estan costat a costat que fa que sigui encara més probable, vostè té el doble de la oportunitat, que et vas tenir una altra col·lisió amb aquest grup, i el grup creixerà a un. I seguiràs creixent i creixent seva probabilitat de tenir una col·lisió. I, finalment, és tan dolent com no classificar les dades en absolut. 

L'altre problema però és que Encara, i fins ara fins a aquest punt, només hem estat una mena de comprensió del que és una taula hash, encara només tenim espai per a 10 cordes. Si volem seguir per discutir els ciutadans de Springfield, només podem obtenir 10 d'ells en aquest país. I si ho intentem i afegim un 11 o 12, no tenim un lloc per posar-les. Podríem simplement estar girant al voltant de cercles tractant de trobar un lloc buit, i que potser estanquem en un bucle infinit. 

Així que aquest tipus de presta a la idea d'una cosa anomenada encadenament. I aquí és on anem a portar llistes enllaçades de nou a la imatge. ¿I si en lloc d'emmagatzemar només les dades en si en la matriu, cada element de la matriu podria mantenir múltiples peces de dades? Bé, això no té sentit, oi? Sabem que una matriu només pot hold-- cada element d'una matriu només pot contenir una sola peça de dades d'aquest tipus de dades. 

Però i si aquest tipus de dades és una llista enllaçada, oi? ¿I què si tots els element de la matriu era un punter al capdavant d'una llista enllaçada? I llavors podríem construir aquestes llistes enllaçades i créixer arbitràriament, perquè llistes enllaçades permeten a créixer i encongir molt més flexible que una matriu fa. ¿I què si ara fem servir, aprofitem això, oi? Comencem a conrear aquestes cadenes fora d'aquests llocs de matriu. 

Ara podem encaixar un infinit quantitat de dades, o no infinit, una quantitat arbitrària de dades, en la nostra taula hash sense topar-se el problema de la col·lisió. També hem eliminat agrupament per fer això. I bé sabem que quan inserim en una llista enllaçada, si recordes del nostre vídeo en llistes enllaçades, per separat llistes enllaçades i llistes doblement enllaçades, que és una operació de temps constant. Estem afegint a la part davantera. 

I per la mirada cap amunt, així que sabem aquesta mirada en una llista enllaçada pot ser un problema, oi? Hem de buscar a través de de principi a fi. No hi ha atzar l'accés en una llista enllaçada. Però si en lloc de tenir un vinculat llista on una recerca seria O de n, ara tenim 10 llistes enllaçades, o 1.000 llistes enllaçades, ara és el O de n dividit per 10, o O de n dividit per 1.000. 

I mentre parlàvem teòricament sobre la complexitat deixem de banda les constants, en la realitat món aquestes coses realment importen, Oi? En realitat ens adonarem que això succeeix per executar 10 vegades més ràpid, o 1.000 vegades més ràpid, perquè estem distribuint una llarga cadena a través de 1.000 cadenes més petites. I així, cada vegada que hem de buscar a través d'una d'aquestes cadenes que puguem ignorar les cadenes 999 no importen aproximadament, i simplement buscar que un. 

La qual cosa és de mitjana de ser 1.000 vegades més curt. I pel que encara estem mena de tendint cap a aquest cas la mitjana de ser constant de temps, però només perquè estem aprofitant dividint per un enorme factor constant. Anem a veure com això podria realment es veuen però. Així que aquesta era la taula hash que teníem abans que declarem una taula hash que era capaç d'emmagatzemar 10 cordes. No farem això. Ja sabem que el limitacions d'aquest mètode. Ara la nostra taula hash serà un conjunt de 10 nodes, punters als caps de les llistes enllaçades. 

I en aquest moment és nul. Cada un d'aquests 10 indicadors és nul. No hi ha res en la nostra hash de taula ara mateix. 

Ara anem a començar a posar una mica de les coses en aquesta taula hash. I veurem com aquest mètode és ens va a beneficiar una mica. Ara anem a hash Joey. Anem a executar la cadena de Joey a través una funció hash i tornem juny. Bé, què fem ara? 

Bé, ara es treballa amb llistes enllaçades, no estem treballant amb matrius. I quan estem treballant amb llistes enllaçades que Sabem que hem de començar de forma dinàmica assignar cadenes d'espai i de construcció. Això és una mena de com-- aquests són el nucli elements de la construcció d'una llista enllaçada. Així que anem a dinàmicament assignar espai per Joey, i després anem a afegir-lo a la cadena. 

Així que ara mira el que hem fet. Quan hash Joey ens van donar el codi hash juny. Ara el punter en la ubicació matriu juny apunta al cap d'una llista enllaçada, i en aquest moment és l'única element d'una llista enllaçada. I el node en aquest llista enllaçada és Joey. 

Així que si hem de mirar cap amunt Joey després, vam acabar hash Joey de nou, obtenim 6 altra vegada perquè la nostra funció hash és determinista. I llavors vam començar al capdavant de la llista enllaçada assenyalat que per ubicació array 6, i podem iterar a través d'aquesta tractant de trobar Joey. I si construïm la nostra hash de taula amb eficàcia, i la nostra funció hash amb eficàcia per distribuir bé les dades, de mitjana cada un dels vinculats llistes en cada ubicació de matriu serà 1/10 de la mida de si només tenia com una sola gran llista enllaçada amb tot el seu contingut. 

Si distribuïm aquest enorme vinculats llista en 10 llistes enllaçades cada llista serà un dècim de la mida. I per tant 10 vegades més ràpida per buscar a través d '. Així que anem a fer això una altra vegada. Ara anem a hash de Ross. 

I diguem Ross, quan ho fem el codi hash tornem és 2. Bé, ara ens dinàmicament assignem un nou node, posem Ross en aquest node, i diem ara ubicació array 2, en lloc d'assenyalar a null, apunta al cap d'un lligat llista l'únic node és Ross. I podem fer això un cop més, ens pot hash de Rachel i obtenir codi hash 4. malloc un nou node, ja Raquel en el node, i dir una ubicació array 4 ara apunta al cap d'una llista enllaçada la únic element passa a ser Rachel. 

Bé, però què passa si tenim una col·lisió? Anem a veure com fem servir les col·lisions utilitzant el mètode d'encadenament separat. Anem a hash Phoebe. Obtenim el codi hash juny. En el nostre exemple anterior estàvem emmagatzemar les cadenes a la matriu. Això era un problema. 

No volem donar-li una pallissa Joey, i ja hem vist que podem aconseguir alguna cosa d'agrupació problemes si tractem de pas a través i la sonda. Però, i si només una mica tractar aquest de la mateixa manera, no? És com l'addició d'un element al capdavant d'una llista enllaçada. Anem espai just malloc per Phoebe. 

Direm propers punter de Phoebe l'antic cap de la llista enllaçada, i després 6 simplement apunta a la nou cap de la llista enllaçada. I ara mira, hem canviat en Phoebe. Ara podem emmagatzemar de dos elements amb codi hash 6, i no tenim cap problema. 

Això és més o menys tot cal encadenament. I encadenament és definitivament el mètode que és serà més efectiu per a vostè si està emmagatzemant dades en una taula hash. Però aquesta combinació de matrius i llistes enllaçades entre si per formar una taula hash realment millora dramàticament la seva capacitat per emmagatzemar grans quantitats de dades, i molt ràpida i eficient buscar a través d'aquestes dades. 

Encara hi ha una més estructura de dades per aquí que fins i tot podria ser una mica millor en termes de garantir que la nostra inserció, eliminació i mirar els temps són encara més ràpid. I veurem que en un vídeo en intents. Sóc Doug Lloyd, això és CS50.