Taula hash

De Viquipèdia
Jump to navigation Jump to search
Fig.1 Exemple de taula hash : agenda de telèfons

Taula hash, en ciències de la computació, és una estructura de dades que implementa un tipus abstracte de dades que és un array associatiu, una estructura que mapeja claus a valors. Una taula de hash empra una funció hash per a calcular un índex que apunta a un array o taula, a partir de la qual es pot obtenir el valor buscat.

Idealment, la funció hash assignarà a cada clau a un únic índex, però la majoria de taules hash empren una funció hash imperfecta, que poden causar col.lisions on la funció hash genera el mateix índex per a més d'una clau (cal gestionar aquesta excepció).[1][2][3]

Funcionament[modifica]

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

Inserció[modifica]

Per a inserir un valor a la taula cal calcular el valor o índex mitjançant la clau i la funció hash. Aquest valor s'emmagatzema a la taula on indica l'índex. Si a la posició ja hi havia una dada vol dir que s'ha produït una col.lisió, i aquest problema es pot solucionar associant una llista a cada posició de la taula.

Recerca[modifica]

Es calcula l'índex amb la clau i la funció hash, llavors amb aquest índex s'obté la dada de la taula.

Resolució de col.lisions[modifica]

Fig.2 Exemple de col.lisió de les funcions hash : hi ha dues claus amb un mateis índex 873. En aquest cas se soluciona amb Hashing obert.

Si dues claus generen un hash apuntant el mateix índex, els registres corresponents no es poden emmagatzemar a la mateixa posició. En aquests casos, cal trobar una altra ubicació on es guardi el nou registre.

Tècniques més populars de resolució de col.lisions :

Hashing obert[modifica]

En cas de col.lisió s'omple una llista de valors en conflicte (vegeu Fig.2)

Hashing tancat[modifica]

Fig.3 Exemple de col.lisió de les funcions hash : hi ha dues claus amb un mateis índex 873. En aquest cas se soluciona amb Hashing tancat.

En cas de col.lisió s'omple una posició de la taula que sigui buida (vegeu Fig.3)

Referències[modifica]

  1. «Basics of Hash Tables Tutorials & Notes | Data Structures | HackerEarth» (en anglès). https://www.hackerearth.com.+[Consulta: 2 desembre 2017].
  2. Wayne, Robert Sedgewick and Kevin. «Hash Tables» (en anglès). https://algs4.cs.princeton.edu.+[Consulta: 2 desembre 2017].
  3. «SparkNotes: Hash Tables: What is a Hash Table?» (en anglès). http://www.sparknotes.com.+[Consulta: 2 desembre 2017].