Tabla Hash en c++

"Hashing" es una técnica que busca realizar las operaciones de inserción, eliminación y búsqueda en tiempo constante. Esa característica es muy importante cuando se traba con almacenamiento secundario en disco, donde el acceso a una determinada dirección es bastante lenta. Algunas aplicaciones que son beneficiadas por el uso de tablas hash son diccionarios y tablas de palabras reservadas de un compilador.
En vez de organizar la tabla según el valor relativo de cada llave en relación a las demás, la tabla hash toma encuenta solamente su valor absoluto, interpretado como un valor numérico.


tabla hash en c++

Si consiguiésemos asociar a cada elemento a ser almacenado un número como en el ejemplo anterior, podremos realizar las operaciones de inserción, eliminación y búsqueda en tiempo constante.
La función que asocia a cada elemento de un conjunto U un número que sirva de índice en una tabla (array) es llamada de función hash.
Una función hash debe satisfacer las siguientes condiciones:
  1.  Ser simple de calcular
  2. Asegurar que elementos distintos posean índices distintos.
  3. Generar una distribución equilibrada para los elementos dentro del array.
Funciones Hash

Crear una función hash satisfaciendo las condiciones anteriores no siempre es una tarea fácil. Existen mucho modelos de creación para funciones hash. A continuación se presentan apenas dos formas de creación de funciones hash. en "Cormen,T.H. Leiserson C.E., Rivest R.L. Introduction to Algorithms" pueden ser encontraod varios ejemplos afines hash.

Una buena función hash es aquella en que toda entrada (slot) del array posee la misma probabilida de ser alcanzado por la función.

Método da División
El método de la división consiste en los siguiente: suponga que los elementos x que deben ser almacenados sean números enteros, una función hash que puede ser utilizada para distribuir tales números en un array (tabla hash) es:
h(x)=x% (tamaño de la tabla)
Implementación
La siguiente función describe la implementación de la función hash descrita anteriormente para el caso de strings.

int Hash(char *a, int stringsize)
{
        int hashval, j;
        hashval = (int) a[0];
       for (j = 1; j < stringsize; j++)
       hashval += (int) a[j];
       return(hashval % tablesize); /* suponiendo que tablesize es global */
 }

Método del Doblado
En este método, las llaves son interpretadas como una secuencia de dígitos escritos en un pedazo de papel. Ello consiste en "doblar" ese papel, de manera que los dígitos se superpongan sin llevar en consideración el "se lleva uno" como se muestra en la siguiente figura.

metodo del boblado hash


El proceso es repetido hasta que los dígitos formen un número menor al del tamaño de la tabla hash.
Es importante resaltar que el metodo de doblar tambien puede ser usado con números binarios. En este caso, en vez de la suma, se debe realizar una operación de "OR exclusivo", pues operaciones de "AND" y de "OR" tienden a producir direcciones-base concentrados al final o al inicio de la tabla.



Colisiones

Por más que se intente encontrar una función hash eficiente, en aplicaciones prácticas es difícil conseguir evitar el problema de colisiones de llaves. Así, se vuelve necesario estudiar alternativas para este problema.
Existen varias formas de resolver el problema de colisiones, dentro de ellas destacamos:
Existen varias formas de resolver el problema de colisiones, dentro de ellas destacamos:
Encadenamiento Separado o Externo (Separate Chaining)
En el encadenamiento separado colocamos los elementos que poseen llaves iguales en una listas encadenada.

coliciones con listas

Utilizando esta estrategia, no es difícil percibir que en el peor de los casos el tiempo para insertar un nuevo elemento en la tabla es de O(1). La búsqueda por un elemento, toma el tiempo proporcional al tamaño de la lista almacenada en cada slot.

Encadenamiento Interno
Encadenamiento interno es un método para resolver problemas de colisiones mediante el empleo de listas encadenadas que comparten el mismo espacio de memoria al de la tabla de distribución.

El encadenamiento interno prevee la división de la tabla T en dos zonas, una de dirección-base, de tamaño p, y otra reservada para colisiones, de tamaño s. Naturalmente, p+s = m, donde m corresponde al tamaño de la tabla hash.


encadenamiento interno
Un problema de esta técnica es que ella puede provocar colisiones secundaria, eso quiere decir, que puede provocar colisiones provenientes de la coincidencia de direcciones para llaves que no son sinónimas. Este fue el caso ocurrido en al figura anterior cuando se intentó insertar el número 02. En la dirección base de este número ya se encontraba el número 14, el cual no es sinónimo de 02.
Otra dificultad de esta técnica se encuentra en la función de eliminación de un elemento. Es necesario tomar cuidado en este procedimiento para que la llamada de búsqueda y eliminación futuras no retornen falsos resultados. ¿Por qué? Cuando estudiamos la técnica de direccionamiento abierto, veremos una solución para este problema.

Implementación

A continuación se tiene la implementación de una estructura hash y las funciones de inserción, búsqueda y eliminación en la tabla.


Ver código