Introducción

Una tabla hash es una estructura de datos que permite asociar claves con valores y cuya principal ventaja es una complejidad de inserción y busqueda de O(1) (O(n) en el peor de los casos).

Cuando tenemos la necesidad de almacenar datos en memoria tenemos una serie de opciones (listas enlazadas, arrays, arboles...) cada una de las cuales tienes sus ventajas y sus inconvenientes que normalmente consisten en establecer un compromiso entre espacio en memoria y velocidad.

Una lista enlazada aprovecha completamente el espacio de memoria pero la velocidad de busqueda es lineal, para encontrar un elemento debemos ir recorriendo la lista hasta encontrarlo, en un array reservamos toda la memoria que podríamos por adelantado pero por contra obtenemos un rendimiento de busqueda constante O(1). Los arboles constituyen una variación de las listas enlazadas en las cuales se mejora el rendimiento de busqueda (O(log(n))) a cambio de empeorar el rendimiento de inserción.

Las tablas hash constituyen una forma de obtener un rendimiento (casi) constante controlando la cantidad de memoria que deseamos compromenter, cuanto más pequeña sea la tabla mayor será el impacto sobre el rendimiento de la tabla debido al numero de colisiones.

La función hash

La función hash es la llave principal de una tabla hash, es la función que se encarga de asignar un identificador único a cada uno de los elementos que insertamos en la tabla. Se encarga de trazar un mapeo entre el identeficador del dato y su posición en la tabla.

Obviamente, puesto que el espacio posible de identificadores es potencialmente infinito y el espacio de memoria (el numero de posiciones del array) es, por definición, finito, existe la problemática de que varios elementos pueden 'colisionar' en una misma posición.

El funcionamiento normal de una tabla hash es:

1. Primero se calcula el hash (la posición del array en la que está guardado el elemento) del id proporcionado aplicando la función de hash
2. Una vez obtenida la posición del array se comprueba si hay una colisión (si ya hay un elemento en esa posición del array) y si la hay se resuelve.
3. Finalmente se escribe o se lee el valor en la tabla hash

Funciones de hash

El problema de asignar un numero a un identificador tiene varias soluciones, unas más rápidas que otras. El objetivo fundamental de una buena fución de hash es la aleatoriedad, es decir, que dados dos identificadores parecidos (cuyo cambio consista por ejemplo en el valor de un byte) obtengamos dos valores hash muy distanciados entre si. En gran parte de los casos, parte de la aleatoriedad puede conseguirse eligiendo los numeros a usar cuidadosamente (como por ejemplo en la función de Hash de Bernstain que es tan simple como h = 33 * h + p[i]; (siendo p la cadena que tiene la clave) y sin embargo produce unos buenos resultados de dispersión).

Funcion simple

La forma más simple para obtener el hash de una determinada longitud dado un determinado tamaño consiste sencillamente en obtener un valor numérico del id (si el identificador no es numérico) y despues calcular el resto de la división por el tamaño de la tabla.

El principal problema de esta función de hashing es que es poco aleatoria. Si tomamos el hash de 'aaa' y el hash de 'aba' observaremos que son relativamente cercanos (de hecho son correlativos) lo cual es una cualidad 'mala' en una función de hash ya que, por ejemplo si estamos insertando datos en la tabla den función de ids binarios no encontramos con una alto grado de colisiones ('0001', '0010', '0100' y '1000' por ejemplo tienen el mismo hash).

ELF hash

La función de hash ELF recibe su nombre de su utilización en los archivos objeto de Unix (Excetutable and Linking Format).

Básicamente la función es igual que la anterior pero añadiendo una cierta aleatoriedad en cada iteración del bucle.

Otras funciones de hash

Hay numerosas funciones de hash, yo fundamentalmente he usado la función ELF por ser una función que distribuye muy bien el espacio de claves en el espacio de memoria, con buenos resultados.

En cualquier caso es recomendable, si se observa que por las características del problema que estamos tratando nuestra función de hash produce un alto indice de colisiones es posible que necesitemos cambiarla. En la página The Art of Hashing hay una buena cantidad de funciones de hash (en ingles).

Resolución de colisiones

Como ya hemos dicho, por muy maravillosa que sea nuestra función de hash, puesto que el espacio de claves es potencialmente mucho mayor (como norma general) al espacio de hashing en algún momento nos encontraremos con que dos claves distintas producen el mismo hash. Esto significará que, en un determinado momento, al ir a introducir la información en nuestra tabla puede que ya haya un dato en esa posición o que al ir a recuperarla el dato de la posición que devuelve la tabla hash no tenga la clave correpondiente al elemento que deseamos recuperara. Al igual que existen varios metodos para hayar el hash dada una clave existen también distintos metodos para realizar la resolución de colisiones.

Resolución lineal

El metodo de resolución linear se basa en que, si una posición está ocupada, seguimos buscando una posición libre en base a algún desplazamiento (constante o dado por una función). A este tipo de resolución de colisiones se la considera englobada en el esquema abierto de direcciones (open addressing schemes).

La implementación más sencilla de este metodo es, al encontrar una posición ocupada, continuar recorriendo las posiciones siguientes hasta encontrar un hueco vacio.

A la hora de realizar una busqueda el asunto es similar, miramos el primer hash y si no encontramos el elemento que buscamos en la posición avanzamos a la siguiente hasta encontrar el elemento en cuestión o un elemento vacio (fallo en la busqueda).

Cuando borramos un elemento de la lista sin embargo hay que tener cierto cuidado. No podemos sencillamente vaciar la posición que ocupaba el elemento sin más, imaginemos este caso:

• 23 'aba'
• 24 'aab'
• 25 'baa'

En el que todos los elementos hacen hash al 23, si eliminamos el elemento 'aab' y simplemente lo vaciamos

• 23 'aba'
• 24 vacio
• 25 'baa'

De forma que cuando realizamos una busqueda de 'baa' calculamos su hash, miramos el elemento 23 (fallo), pasamos al elemento 24 que está vacio y paramos la busqueda, sin haber encontrado el elemento que buscabamos y que realmente estaba ahí, asi que no podemos sencillamente 'vaciarlo' sino que deberemos introducir algún valor 'especial' que nos permita saber que ante una busqueda no debemos dejar de buscar.

La resolución lineal de colisiones tiene varias ventajas:

• El uso de la tabla es constante, es decir, no se usa más memoria de la que inicialmente se asignó como tamaño inicial de la tabla (al contrario de lo que pasa con el metodo de lista enlazada)
• El mecanismo es relativamente rápido si esperamos tan solo dos o como mucho tres colisiones

aunque en mi opinion tiene en mi opinión más desventajas que ventajas

• El hecho de insertar elementos en posiciones que 'no son suyas' da lugar a que puedan producirse colisiones que no debería producirse.

  Por ejemplo, si insertamos 'abb' y 'bba' que supongamos que corresponden al mismo hash (23) tendremos algo como esto más o menos

  • 23 'abb'
  • 24 'bba'

  y después de ello insertamos el elemento 'bbb' que supongamos que corresponde al hash 24 obtendremos una colisión pese a que ningún otro elemento había obtenido el hash 24.

  • 23 'abb'
  • 24 'baa'
  • 25 'bbb'
• Puesto que el espacio es límitado al encontrar una colisión podemos encontrarnos ante el caso de que la tabla se llene (lo cual no es necesariamente malo pero quizá no es lo que estamos buscando)
• Cuando borramos un objeto de la tabla hay que marcar el hueco con un identificador de forma que cuando estemos haciendo una busqueda podamos reconocerlo y seguir buscando.

Hashing doble

El algoritmo de hashing doble es otro algoritmo de esquema de direcciones abierto que resuelve el problema de colisiones aplicando un segundo hash en caso de colisión. El esquema es relativamente simple:

En el sistema de resolución linea si varias claves hacen hash a un mismo valor seguirán la misma ruta de resolución de colisión (sumando uno). El principio del doble hashing se basa en que es muy poco probable que dos hash distintos sobre distintas claves den el mismo valor para ambas de forma que cuando se produce una colisión en la primera función de hash es altamente probable que no se produzca colisión - con el mismo elemento - al aplicar la segunda función.

Nota: El ejemplo anterior no está teniendo en cuenta el caso de que la tabla este muy (o totalmente) llena lo cual sería malo (si estuviera llena en concreto lo anterior daría un bucle infinito)

Resolución con listas enlazadas

Otro metodo para resolver colisiones consiste en establecer, en cada posición en la que se da una colisión, una lista enlazada con todos los elementos. De esta forma cuando realizamos una inserción, en caso de colisión tan solo debemos insertar al final de la lista correspondiente a la posición y cuando estamos realizando una búsqueda, accedemos a la posición y recorremos la lista.

La ventaja de esta solución es que es muy sencilla de implementar, permite que la tabla crezca de forma dinámica hasta la profunidad deseada (siempre podemos controlar la longitud de cada lista) y si estimamos 2 o 3 colisiones como mucho se comporta adecuadamente en las busquedas. Además no estaremos metiendo elementos en posiciones que no les corresponden, es decir, no estaremos produciendo 'falsas' colisiones.

Una tabla hash completa