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