Taula hash

Taula hash

Una taula hash, matriu associativa, hashing, mapa hash, taula de dispersió o taula fragmentada és una estructura de senyes que implementa el tipo de senya abstracta cridat diccionari (tipo de senya abstracta). Esta associa claus o claus en valors. L'operació principal que soporta de manera eficient és la busca: permet l'accés als elements (teléfon i direcció, per eixemple) almagasenats a partir d'una clau generada (usant el nom o número, per eixemple). Funciona transformant la clau en una funció hash en un hash, un número que identifica la posició (casella o cubeta) a on la taula hash localisa el valor desijat.

Les taules hash se solen implementar sobre vectores d'una dimensió, encara que es poden fer implementacions multi-dimensionals basades en vàries claus. Com en el cas dels arrays, les taules hash proveïxen temps constant de busca promig O(1), sense importar el número d'elements en la taula. No obstant, en casos particularment mals el temps de busca pot aplegar a O(n), és dir, en funció del número d'elements.

Comparada en atres estructures de arrays associades, les taules hash són més útils quan s'almagasenen grans cantitats d'informació.

Les taules hash almagasenen l'informació en posicions pseudo-aleatòries, aixina que l'accés ordenat al seu contingut és prou llent. Atres estructures com arbres binarios auto-balanceables tenen un temps promig de busca major (temps de busca O(log n)), pero l'informació està ordenada en tot moment.

Funcionament

Les operacions bàsiques implementades en les taules hash són:

Inserció

La forma d'implementar en funció esta operació és demanant la clau i el valor, per a en estos poder fer l'inserció de la senya.

1. Per a almagasenar un element en la taula hash s'ha de convertir la seua clau a un número. Açò es conseguix aplicant la funció resumixen (hash) a la clau de l'element.
2. El resultat de la funció resumixen ha de mapearse a l'espai de direccions del vector que s'ampra com a soport, la qual cosa es conseguix en la funció mòdul. Despuix d'este pas s'obté un índex vàlit per a la taula.
3. L'element s'almagasena en la posició de la taula obtingut en el pas anterior.
   • Si en la posició de la taula ya hi havia un atre element, s'ha produït una colisió. Este problema es pot solucionar associant una llista a cada posició de la taula, aplicant una atra funció o buscant el següent element lliure. Estes possibilitats han de considerar-se a l'hora de recuperar les senyes.

Busca

La forma d'implementar en funció esta operació és demanant la clau i en esta tornar el valor.

1. Per a recuperar les senyes, és necessari únicament conéixer la clau de l'element, a la qual se li aplica la funció resumixen.
2. El valor obtingut es mapea a l'espai de direccions de la taula.
3. Si l'element existent en la posició indicada en el pas anterior té la mateixa clau que l'empleada en la busca, llavors és el desijat. Si la clau és distinta, s'ha de buscar l'element segons la tècnica empleada per a resoldre el problema de les colisions en almagasenar l'element.

La majoria de les implementacions també inclouen la funció de borrar a la qual se li envia una clau que deurà eliminar. També es poden oferir funcions com iteración en la taula, creiximent i buidat. Algunes taules hash permeten almagasenar múltiples valors baix la mateixa clau.

Per a usar una taula hash es necessita:

1. Una estructura d'accés directe (normalment un array).
2. Una estructura de senyes en una clau
3. Una funció resumixen (hash) el domini de la qual siga l'espai de claus i la seua image (o ranc) els número natural.

Pràctiques recomanades per a les funcions hash

Una bona funció hash és essencial per al bon rendiment d'una taula hash. Les colisions són generalment resoltes per algun tipo de busca llineal, aixina que si la funció tendix a generar valors similars, les busques resultants es tornen llentes.

En una funció hash ideal, el canvi d'un simple bit en la clau (incloent el fer la clau més llarga o més curta) deuria canviar la mitat dels bits del hash, i este canvi deuria ser independent dels canvis provocats per atres bits de la clau. Com una funció hash pot ser difícil de dissenyar, o computacionalment cara d'eixecució, s'han invertit molts esforços en el desenroll d'estratègies per a la resolució de colisions que mitiguen el mal rendiment del hasheo. No obstant, cap d'estes estratègies és tan efectiva com el desenroll d'una bona funció hash de principi.

És desijable utilisar la mateixa funció hash per a arrays de qualsevol tamany concebible. Per a açò, l'índex de la seua ubicació en el array de la taula hash es calcula generalment en dos passos:

1. Un valor hash genèric és calculat, omplint un sancer natural de màquina.
2. Este valor és reduït a un índex vàlit en el vector trobant el seu mòdul sobre el tamany del array.

El tamany del vector de les taules hash és en freqüència un número primo. Açò es fa en l'objectiu d'evitar la tendència de que els hash de sancers grans tinguen divisores comuns en el tamany de la taula hash, lo que provocaria colisions despuix del càlcul del mòdul. No obstant, l'us d'una taula de tamany primer no és un substitut a una bona funció hash.

Un problema prou comú que ocorre en les funcions hash és el aglomeramiento. El aglomeramiento ocorre quan l'estructura de la funció hash provoca que claus usades comunament tendixquen a caure molt prop unixques d'unes atres o inclús consecutivament en la taula hash. Açò pot degradar el rendiment de manera significativa, quan la taula s'ompli usant certes estratègies de resolució de colisions, com el sondeig llineal.

Quan es depura el maneig de les colisions en una taula hash, sol ser útil usar una funció hash que torne sempre un valor constant, com 1, que cause colisió en cada inserció.

Funcions hash més usades:

1. Hash de divisió: Donat un diccionari D, es fixa un número m >= |D| (m major o igual al tamany del diccionari) i que siga primer no propenc a potència de 2 o de 10. Sent k la clau a buscar i h(k) la funció hash, es té h(k)=k%m (Restant de la divisió k/m).
2. Hash de multiplicació: Si per alguna raó, es necessita una taula hash en tants elements o punters com una potència de 2 o de 10, serà millor usar una funció hash de multiplicació, independent del tamany de la taula. Es tria un tamany de taula m >= |D| (m major o igual al tamany del diccionari) i un cert número irracional φ (normalment s'usa 1+5^(1/2)/2 o 1-5^(1/2)/2). D'esta manera es definix h(k)= Sol(m*Part fraccionaria(k*φ))