[SOROLL]. Abans de capbussar-se en taules hash, anem a primer revisar els pros i els contres d'alguns estructures de dades més simples, a partir de matrius. Recordem que els arrays ens permeten emmagatzemar elements d'un únic tipus de dades contigua en memòria. Com que cada element està associat amb un índex, o ubicació, tenim accés aleatori a tots els elements d'una matriu. En altres paraules, podem accedir a qualsevol element en un sol pas mitjançant la indexació en la array. Aquest és un gran problema, ja que els algoritmes com binari de recerca dependrà d'atzar accés. Un inconvenient de les matrius és que la seva mida es fixa. Atès que les dades conjuntes de botiga contigua a memòria, ha d'especificar una mida de matriu quan es declara la matriu. Vostè està demanant amb eficàcia el funcionament sistema per reservar la quantitat apropiada de la memòria per als elements de la matriu. No es garanteix que més memòria, adjacent a la matriu, estarà disponible per al seu ús posterior. Així que els arrays no poden créixer fàcilment. Recordem que també vam aprendre sobre vinculats llistes, que poden créixer perquè el seu elements que no són contigus en la memòria. Cada node en una llista enllaçada conté la element que volem emmagatzemar, així com un punter a l'element posterior en la llista. Per desgràcia, el preu que hem pagat per mida dinàmic és l'accés aleatori a elements. Per tal d'accedir a un determinat element, cal travessar tota la llista fins l'element desitjat és assolit. Per tant, si estic buscant per al número 9, que havia seguir els punters de node a node, comprovar si el valor de cada node és igual a 9. Com a tal, en el pitjor dels casos, busca és O (n), que està lluny de ser eficient. Podem fer alguna cosa millor que O (n), mentre que encara permetent que la nostra estructura de dades per créixer amb el temps? Les taules hash ofereixen una solució. S'utilitzen taules hash quan veloç inserció, eliminació, i la recerca de elements és la prioritat. En teoria, la inserció, eliminació i recerca fins i tot es pot aconseguir en constant temps. Llavors, què és una taula hash de totes maneres? Una taula hash és simplement un conjunt acoblat amb una funció, que anomenarem el hash funció. La funció hash pren un tros de dades com a entrada, anem a trucar a aquesta una contrasenya, i dóna sortida a un nombre enter, comunament coneguda com un valor hash. El valor hash assigna la nostra clau per a una en particular l'índex de la taula hash. Vostè hauria d'utilitzar inicialment la funció de hash per determinar en quin lloc de la taula hash per emmagatzemar una clau donada. Més tard, haurà d'utilitzar la mateixa funció hash per determinar on en la taula hash per cercar una clau determinada. Per aquesta raó, és crucial que un hash funció es comporta de manera consistent i sortides el mateix valor hash per claus idèntiques. Has de saber que les taules hash es poden utilitzar per emmagatzemar dades de tots els tipus. No obstant això, per simplificar les coses, ens centrarem en cordes per ara. Heus aquí una funció hash simple per cordes. Aquesta funció hash calcula un hash funció basada en la primera lletra de la clau. "Apple" comença amb la lletra "A", pel que és mapejat en l'índex 0 a la taula hash. De la mateixa manera, "banana" s'assigna a l'índex 1, i "gat" s'assigna a l'índex 2. Si un amic li pregunta si la paraula "gos" està en la taula, anem a l'entrada "gos" a la taula hash funció, que serà un valor hash de sortida de 3. Ja que "gos" no s'emmagatzema en l'índex 3, que es pot dir amb confiança que "gos" no és a la taula, tot i que només hem comprovat una de les hash de 26 índexs de la taula. És hora de llançar una clau en les coses. Què passa si volem emmagatzemar "formiga" al taula així? "Ant" hashes d'índex 0, igual que "la poma" ho va fer. Aquest és un exemple d'una col · lisió, la resultat de dues claus hash a la mateixa índex. Fins i tot si la taula hash és més gran que conjunt de dades, i que han triat una bona funció hash, vostè encara necessita un pla per tractar amb col · lisions, sempre que aquestes es produeixin. Anem a discutir els pros i els contres dels dos mètodes comuns per resoldre les col · lisions: sondeig lineal i encadenament separat. Amb el sondeig lineal, si un hash de clau de el mateix índex que la prèviament emmagatzemada clau, se li assigna la següent disposició ranura a la taula. Per tant, "formiga" s'emmagatzema ara en l'índex 3, ja que índexs 0, 1 i 2 ja estaven en ús. I si tractem d'emmagatzemar una tercera paraula que comença amb la lletra "A", és assignar l'índex 4, ja que els índexs 0, 1, 2, i 3 estan plens. Com es pot veure fins i tot des d'aquest senzill exemple, una vegada que es produeix una col · lisió, es augmentar significativament les possibilitats que altra col · lisió es produirà en el mateix àrea. Això es diu l'agrupació, i és un seriós inconvenient per al sondeig lineal. D'altra banda, en el pitjor dels casos la inserció, supressió, i els temps de cerca s'han transferit a O (n), com la següent ranura disponible podria tenir potencialment estat l'última ranura de la taula. Tal encadenament separat oferirà una més solució convincent. En el model d'encadenament separat, el hash taula és en realitat un conjunt d'indicadors per llistes enllaçades. Quan es produeix una col · lisió, la clau pot ser inserida en un temps constant al capdavant de la llista enllaçada apropiat. El que passa ara, quan busquem "poma" a la taula hash? En el pitjor dels casos, cal travessar el tota llista enllaçada, començant en l'índex 0. El temps de recerca del pitjor cas per a un hash taula que utilitza encadenament separat és per tant, O (n / k), on k és el mida de la taula hash. Espera un segon, k és una constant. Així que O (n / k) és realment només O (n), que era el temps de recerca del pitjor cas per una llista enllaçada. Realment hem passat per tots els problemes d'aprenentatge sobre taules hash només per acabar on comencem? Aquest pot ser el cas d'un teòric perspectiva, però en el món real, O (n / k) podria ser una gran millora pel que fa O (n). Pensa-ho d'aquesta manera: suposem que k és 10 - Què preferiries esperar 100 segons o 100 / k? 10 segons des de Microsoft Word per acabar la correcció ortogràfica del document. Com acabem de veure, la resolució de col · lisions implica una mena de recerca lineal o altre, el que alenteix les coses considerablement. Per tant, vostè voldrà triar un hash funció que minimitza la possibilitat d' col · lisions que ocorren en el primer lloc. Aquestes són algunes de les propietats d'un bon picada funcions a tenir en compte. Una bona funció hash ha de fer ús de tota la informació proporcionada per una clau determinada per tal de maximitzar el nombre de possibles valors hash. Per exemple, si tinguéssim dues cadenes, "gat" i "eruga", que voldria que picada a diferents llocs de la taula. Si una funció hash només va tenir en compte el primer un, dos, o fins i tot tres lletres de les cordes, es produiria una col · lisió, des d'ambdues paraules comencen amb el mateix tres lletres. Els valors hash s'han de repartir uniformement a través de la taula hash. Això reduirà la longitud d'lligat llistes haurien de produir col · lisions. També és un bon senyal si el valor hash és capaç de generar molt diferent valors hash per claus similars, fent col · lisions molt menys probable. El nostre objectiu és una ràpida inserció, supressió, i de consulta. La funció hash juga un paper crucial en la cadascun d'aquests processos i serà anomenat amb molta freqüència. Per tant, assegureu-vos que només empra molt operacions senzilles i ràpides per minimitzar termini temps. Espero que hagis gaudit d'aquesta breu introducció a taules hash. El meu nom és Lauren, i això és CS50.