Las Tablas Hash

Uno de los principales retos que deben afrontar los sistemas informáticos que manejan grandes cantidades de información es el almacenamiento, búsqueda y eliminación de datos, ya que cuando se manejan grandes cantidades de información ya que se requieren constantes consultas por múltiples usuarios al mismo tiempo. Una solución para esto son las tablas hash, la cuáles ofrecen búsquedas rápidas y en tiempo real, pero ¿Son las tablas hash la solución más conveniente para esto?

Las tablas hash ofrecen grandes ventajas puesto que ayudan al almacenamiento de la información y con ellas se puede realizar consultas en tiempo real. Los diccionarios electrónicos, correctores ortográficos y compiladores de código utilizan tablas hash, puesto que necesitan realizar una consulta de datos rápida y al instante; las tablas hash sí son una solución para ese reto que afrontan muchos sistemas informáticos.

Para tener una aseveración más acertada acerca de la eficiencia de las tablas hash hay que empezar por definir qué son. Una tabla hash es una estructura de datos  que se utiliza para almacenar grandes cantidades de datos que necesitan operaciones de búsqueda y de inserción muy eficientes. Una tabla hash almacena dos objetos, una clave y un valor. La clave tiene que ser única para cada elemento de la tabla y el valor es el dato almacenado.

La diferencia entre las tablas hash y cualquier otro tipo de almacenamiento de datos con id’s, es que se busca que el número de casillas de la tabla no sea muy grande, de manera que al momento de que se realicen varias búsquedas estas sean lo más rápidas posibles. Esto se logra ya que no se tiene que batallar con Id’s muy grandes.

Funciones Hash

La función hash es la que se encarga de asignarle a un elemento (al dato a almacenar) una casilla  a partir de una clave.

Una función hash H(x) debe cumplir con las siguientes características:

1.    La función H(x) se puede aplicar a un bloque de daos de cualquier tamaño.

2.    La función H(x) arroja un valor de amaño fijo.

3.    La función H(x) debe ser fácil de calcular para cualquier software

4.    La función hash tiene la propiedad de ser unidireccional, es decir, dado un valor h a partir de una función H(x), resulta imposible calcular la variable independiente de la función, en este caso “x”

5.    La función debe poseer la propiedad de resistencia débil a la colisión, es decir que a partir de un valor y es imposible calcular H(x).

La función hash debe calcular la columna a partir de la clave en tiempo constante y distribuir de forma uniforme los objetos a lo largo de la tabla.

Para calcular las casillas en las que debe ir cada uno de los elementos a almacenar, la función hash suele utilizar la operación módulo, de esta manera no importa que tan grande sea la clave, con la operación módulo se asegura que el valor arrojado esté dentro de los límites de un array en el que se almacenan los datos.  En la función hash se le aplica a un módulo del tamaño del array a un valor que se saca a partir de una clave y de una serie de operaciones matemáticas.

Es importante que la función hash esté diseñada correctamente, ya que dentro de las tablas hash ocurre un problema denominado colisiones. Las colisiones se producen cuando dos o más datos diferentes que van a ser almacenados reciben el mismo valor de entrada (La misma casilla).

Es importante que la tabla hash tenga un tamaño relativamente grande, ya que de esta manera se evitan las colisiones. Si la tabla es de un tamaño muy reducido, la probabilidad de que exista un gran número de colisiones es muy alta.

Formas de resolver colisiones

Existen diferentes maneras de resolver las colisiones producidas por un mal diseño e la función hash, ya sea por exploración lineal, exploración cuadrática o por encadenamiento enlazado.

Exploración lineal: Cuando se produce una colisión, se busca otra posición libre en la tabla para almacenar el dato, se visita la siguiente casilla a partir de donde se produjo la colisión. Si esta está ocupada. Se busca en la siguiente y así sucesivamente hasta que se encuentre una vacía en la que se pueda almacenar el dato.

Exploración cuadrática: En la exploración cuadrática, cuando se produce una colisión se busca la casilla con la posición cuadrada de en la que se produjo la colisión, si esta esta se encuentra vacía, el dato a almacenar es guardado ahí, de lo contrario se vuelve a buscar en la casilla con el número de posición cuadrado de la casilla previa en la que se produjo la colisión.

Encadenamiento enlazado: Esta es la forma más utilizada para resolver colisiones: Cuando se produce una colisión en una posición de la tabla, se crea una sub lista o lista enlazada, en la cual se van insertando los datos a los cuales la función hash les otorgó la misma posición a partir de su clave. Para esto se utiliza un vector de listas enlazadas.

En las tablas hash existe algo denominado factor de carga, el cual se calcula dividiendo el número de elementos almacenados entre la capacidad de la tabla, es decir el número de casillas que tiene. Si el factor de carga es alto (Aproximadamente mayor al 75%), esto indica que el número de colisiones puede aumentar significativamente. Una solución para esto es aumentar el tamaño de la tabla para reducir el número de colisiones.

Desventajas de las tablas hash

Las tablas hash cuentan con la desventaja de que forzosamente el tamaño de estas tiene que ser mayor al número de elementos que van a ser almacenados.

Las colisiones son muy frecuentes en las tablas hash, por lo que muchas veces deben ser resueltas por medio de exploración lineal, cuadrática o encadenamiento enlazado, y cuando el número de colisiones es muy elevado, la taba hash pierde su eficiencia, ya que su tamaño tiene que ser aumentado en gran medida y puede que muchas de sus casillas no se ocupen.

Para su correcto funcionamiento la función utilizada para calcular la posición en la que se almacenará un dato, debe ser elegida con mucha cautela.

Cuando el número de listas entrelazadas es grande, se presentan dificultades para recorrer todos los elementos.

Las tablas hash suelen desaprovechar mucha memoria, puesto que si se reserva espacio para muchos posibles elementos, se consume más memoria de la necesaria.

Conclusión:

En conclusión las tabas hash ayudan a los sistemas informáticos a afrontar el reto de realizar búsquedas, inserciones y eliminaciones de datos en tiempo real y de manera constante, sin embargo estas presentan demasiadas desventajas ya que si el factor de carga es muy elevado, se presentan muchas colisiones, y si debido a las colisiones se realizan muchas listas entrelazadas o se aumenta el tamaño de la tabla, llegará un punto en el que ya no sea tan eficiente el uso de una tabla hash puesto que se complica más buscar los elementos almacenados y se hace más lento el sistema.

La manera correcta de utilizar tablas hash es diseñando una función hash adecuada, es decir, que a partir de la clave que se registra para almacenar un dato, cuando se arroje la posición en la que el dato será almacenado, la función evite que se produzcan muchas colisiones, esto para que la funcionalidad de la tabla pueda ser aprovechada de mejor forma.

Si se pretenden utilizar tablas hash hay que tener en consideración el número de elementos que serán almacenados, el tamaño de la tabla, la función que se va a implementar, las posibles colisiones que se generarán y sus soluciones, el factor de carga y si en realidad conviene utilizar una tabla hash para un determinado sistema informático que trabaje con muchos datos. De lo contrario, la tabla hash traerá muchas desventajas.

Referencias:

William Stallings;(2004); Fundamentos de Seguridad en Redes, Aplicaciones y Estándares; 2 ^aedición; Editorial Pearson educación; Madrid, España; Páginas 61-62

Departamento de ingeniería telemática;( 2011); Tablas hash; Universidad Carlos III de Madrid Recuperado en: http://www.it.uc3m.es/abel/as/MMC/M2/HashTable_es.html 

Sergio Sama Vilanueva;( 2014); DataStructures Tool; México, DF Recuperado en: http://www.hci.uniovi.es/Products/DSTool/hash/hash-queSon.html