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