Tablas Hash

Una tabla Hash es un contenedor asociativo (tipo Diccionario) que permite un almacenamiento y posterior recuperación eficientes de elementos (denominados valores) a partir de otros objetos, llamados claves.

Las tablas hash son estructuras de datos que se utilizan para almacenar un número elevado de datos sobre los que se necesitan operaciones de búsqueda e inserción muy eficientes. Una tabla hash almacena un conjunto de pares “(clave, valor)”. La clave es única para cada elemento de la tabla y es el dato que se utiliza para buscar un determinado valor.
Un diccionario es un ejemplo de estructura que se puede implementar mediante una tabla hash. Para cada par, la clave es la palabra a buscar, y el valor contiene su significado.
Una tabla hash se construye con tres elementos básicos: Un vector capaz de almacenar “m” elementos Función de dispersión que permita a partir de los Función de dispersión que permita a partir de los datos (llamados clave) obtener el índice donde estará el dato en el arreglo Una función de resolución de colisiones

El tiempo medio de recuperación de información es constante, es decir, no depende del tamaño de la tabla ni del número de elementos almacenados en la misma.


"Una estructura Hash Table en C tiene más o menos la siguiente forma:
typedef struct HashTable {
  int num_elements;       /* Número de elementos que podemos almacenar */
  int buckets_vacios;     /* Número de buckets vacíos */
  int* keys;              /* Aca almacenamos las llaves */
  char** values;          /* Aca almacenamos los valores */
} HashTable_t;
Y el código para insertar un elemento tiene la siguiente forma básica. Con este código podemos empezar a ver un problema que vamos a encontrar con un Hash Table:
int insertar(HashTable_t *hashTableP, int key, char *value)
{
  int index;
  // Aplicar la función hash a la llave
  index = key % hashTableP->num_elements;

  // Si el bucket esta libre, insertamos nuestro valor ahi
  if (hashTableP->values[index] == NULL) {
    hashTableP->keys[index] = key;
    hashTableP->values[index] = strdup(value);
    hashTableP->buckets_vacios --;
  }

  // Si no esta libre, entonces tenemos una colisión.
  else {
    // ¿Y ahora?
  }

  return 0;
} "

Colisiones

Cuando se trabaja con tablas hash es frecuente que se produzcan colisiones. Las colisiones se producen cuando para dos elementos de información distintos, la función de dispersión les asigna la misma clave. Como se puede suponer, esta solución se debe arreglar de alguna forma. Para ello las tablas hash cuentan con una función de resolución de colisiones.
Existen dos tipos de tablas hash, en función de cómo resuelven las colisiones:
  • Encadenamiento separado: Las coliciones se resuelven insertándolas en una lista. De esa forma tendríamos como estructura un vector de listas. Al número medio de claves por lista se le llama factor de carga y habría que intentar que esté próximo a 1.
  • Direccionamiento abierto: Utilizamos un vector como representación y cuando se produzca una colisión la resolvemos reasignándole otro valor hash a la clave hasta que encontremos un hueco.

"Por ejemplo elegir insertar nuestro elemento en Item(2) (porque Item(1) está ya ocupado). Si llegara a suceder que Item(2) también está ocupado, entonces podríamos intentar usar Item(3). En otras palabras se trata de encontrar el siguiente bucket disponible. A esta modalidad de “Open Addressing” se conoce como “Linear Probing”. La función de rehash puede escribirse así:
rh(i) = (i+1) % 100
Observemos que la entrada de la función ya no es la clave original, sino el índice generado al aplicar la función de hash original.
Ya hemos visto que aplicar la función de rehash una vez puede no ser suficiente para encontrar el siguiente bucket disponible. ¿Puedes imaginarte qué otros problemas puede haber con este método?
¿Qué pasaría si ya no hay ningún otro bucket disponible? Una implementación poco cuidadosa del rehashing podría ocasionar un ciclo infinito en nuestro código. Podemos resolver este problema teniendo alguna variable que nos indique si aún es posible encontrar un lugar vacío dentro de la Hash Table.
Aún si la tabla no estuviera llena, es posible caer en un ciclo infinito o en una situación en la que nuestra función de rehash nunca encuentre algún lugar disponible. ¿Puedes imaginar este caso? ¿Que pasaría por ejemplo con una función como rh(i) = (i+2) % 100? Sí, esta función intentaría únicamente utilizar posiciones pares o posiciones impares, dependiendo del valor de i."

Conclusiones:

Las tablas Hash son de gran ayuda para almacenar datos y tener una clave íncica para ellos, asi cmo el que si hay colisiones se puedan resolver por medio de funciones para resolverlas.


Bibliografía APA:

Sergio Sama Villanueva. (2012). Tablas Hash. 21/11/14, de DSTOOL Sitio web: http://www.hci.uniovi.es/Products/DSTool/hash/hash-queSon.html

Universidad Carlos III de Madrid. (2010). Tablas Hash. 24/11/11, de Universidad Carlos III de Madrid Sitio web: http://www.it.uc3m.es/abel/as/MMC/M2/HashTable_es.html

Universidad de Puebla. (2010). Tablas Hash. 24/11/11, de Buap Sitio web: https://www.cs.buap.mx/~iolmos/ada/TablasHashArbolesBinarios.pdf

Ricardo Zavaleta . (2016). Tablas Hash. 11/7/17, de Bit y Byte Sitio web: http://bitybyte.github.io/Hashtables/


Comentarios

Publicar un comentario