Tablas hash

Introducción 

"Hashing es el proceso de asociar pares de claves y valores usando arreglos mediante operaciónes aritméticas, las cuales transforman las claves e indican los indices de dicho arreglo"  (López, 2013) 

Las tablas hash tienen el propósito de almacenar, de forma segura y controlada por el programador, datos que necesiten recuperarse posteriormente y que no puedan ser interceptados o capturados por intrusos o usuarios ajenos al control del sistema.

Un ejemplo de un programa con uso de tabla hash podría ser aquel en el que, a través de una cámara, realize un reconocimiento facial de cualquier persona que se le analice y almacene este rostro junto con el nombre del sujeto, para hacer esto posible es necesario crear una tabla vacía de rostros, que, cada vez que se analice uno, esta busque si el rostro ya esta almacenado en la misma tabla junto con un nombre asociado a él, y si no, guardar ambos datos, los cuales son el rostro junto con su respectivo nombre.

Tablas hash

Se le llama tabla hash a un contenedor de datos en el cual se puede almacenar información y tener un buen manejo de ella, donde a cada dato le corresponde un espacio en dicha tabla y para acceder a dicha posición es necesario conocer su clave y realizar una función hash sobre el dato, esta ultima, es la encargada de transformar la clave en un índice del arreglo o tabla,

Las funciones hash deben de distribuir las claves asociadas a cada dato (o mejor dicho, a cada celda asignada a un dato en especifico), de la forma m ás aleatoria posible de forma que no existan accesos indebidos e incorrectos a un dato. Ademas, estas funciones deben de ser fáciles de calcular y deben de distribuir las claves de forma uniforme.

Para diseñar una función hash existen varios métodos, por ejemplo:

• Método de multiplicación: Se trata de multiplicar el vector de almacenamiento por un valor aleatorio y conservar los bits del dato convertido en binario.
• Método de división: Consiste en calcular la función módulo del vector de almacenamiento a la clave que se va a utilizar.
• Método de multiplicación y división: Se combinan ambos métodos anteriores.

Si dos claves iguales conducen a un mismo valor, se dice que existe una colisión, lo cual significa una pérdida de eficiencia que debe de ser corregida lo más pronto posible mediante un encadenamiento separado o un direccionamiento abierto. 

• Encadenamiento separado: Se almacenan las colisiones en una lista, teniendo así, un vector de listas con cada celda asignada a una clave, de esta forma, calculando un factor de carga máximo, la tabla se reestructura si se supera el tamaño limite de la tabla, haciendo imposible la probabilidad de que no se puedan crear nuevos registros dentro de la tabla.
• Direccionamiento abierto: Se utiliza un vector como representación y cuando se produzca una colisión se le asigna otro valor hash hasta que se encuentre una celda vacía dentro de la tabla, es decir, se prueban distintas combinaciones para la función hash hasta que se encuentre un lugar distinto para cada valor involucrado en dicha colisión.

Existen varios tipos de clave, entre ellos están:

• Enteros positivos
• Número en punto flotante
• Cadenas
• La combinación de las anteriores

Lo más adecuado respecto al funcionamiento de las tablas hash es que cada dato posea únicamente un espacio asignado, una función hash y una clave exclusiva, de tal forma que no exista redundancia en la organización de la información.

Los límites en la memoria destinada al almacenamiento de estos datos condiciona el tamaño de la tabla, mientras que un límite en el tiempo requerido de procesamiento restringe la capacidad de utilizar un arreglo desordenado para realizar las búsquedas de manera secuencial, ya que esto requeriría de una mayor exigencia del sistema

La estrategia de dispersión perfecta consiste en encontrar un conjunto de funciones hash, que al ser aplicadas a un conjunto de datos, no se produzca ninguna colisión entre ellos, lo cual nos indicaría que hemos creado la tabla hash de forma perfecta y que no existirán problemas en procesos posteriores.

Conclusión

Las tablas hash son de gran utilidad a la hora de almacenar datos e información sin la necesidad de una base de datos, aunque si se analizan correctamente, podemos darnos cuenta de que estas son muy parecidas al proceso de normalización de una base de datos común y corriente, con la diferencia de que la tabla hash también se encarga de proteger los datos mediante claves y funciones que solamente el programador de la tabla conoce, pero ambas tienen la función de mantener un correcto orden y organización en los datos con el propósito de evitar la redundancia en los datos, lo cual es un aspecto fundamental para el correcto y eficiente funcionamiento de un programa destinado al almacenamiento de grandes cantidades de datos, por lo que el uso de tablas hash es una opción altamente considerable a la hora de crear un sistema con las anteriores características.

Bibliografía 

Departamento de Informática de la Universidad de Valladolid. (10 de Septiembre de 2011). Esturcturas de Datos y Algoritmos: Tablas de Dispersión. Obtenido de https://www.infor.uva.es/~cvaca/asigs/doceda/tema5.pdf

López, F. J. (7 de Agosto de 2013). Estructura de Datos Avanzadas (Tablas Hash). Obtenido de http://www.cimat.mx/~fcoj23/CURSO_ProgAvanzada/sesiones/sesion7_TablasHash.pdf

Pardo, A. (30 de Enero de 2006). Arquitectura de Sistemas. Obtenido de http://ocw.uc3m.es/ingenieria-telematica/arquitectura-de-sistemas-2013/material-de-teoria/logo-ch07.html.pdf/at_download/file

UTEM. (28 de Juilio de 2011). Introducción a las tablas hash. Obtenido de http://informatica.utem.cl/~mcast/ESDATOS/20112/Varios/tablasHash.pdf