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

Fig.1 Exemple de taula hash: agenda de telèfons

Idealment la funció hash assigna cada clau a un únic índex, però la majoria de taules hash empren una funció hash imperfecta, que pot causar col·lisions quan la funció genera el mateix índex per a més d'una clau. És una situació que cal gestionar específicament.[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 s'ha de calcular l'índex mitjançant la clau i la funció hash. El valor s'emmagatzema a la posició de la taula que indica l'índex. Si en aquesta posició ja hi ha una dada, s'ha produït una col·lisió. 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 mateix índex 873. En aquest cas se soluciona amb Hashing obert.

Si la funció hash genera un mateix índex per a dues claus diferents, els registres corresponents no es poden emmagatzemar a la mateixa posició. En aquests casos cal trobar una altra ubicació on desar 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 mateix índex 873. En aquest cas se soluciona amb Hashing tancat.

En cas de col·lisió s'omple una posició de la taula que estigui 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].