TABLAS DE DISPERSION (HASH)

Las tablas hashing constituyen un TAD especialmente indicado para la manipulación y almacenamiento de la información en memoria secundaria. La idea básica consiste en transformar las claves en direcciones de memoria mediante una función de transformación. Estas direcciones pueden hacer referencia a memoria primaria, en cuyo caso tendríamos un array, pero en general las tablas de dispersión aprovechan su potencial para la implementación en memoria secundaria.

Es común al crear estructuras de datos y luego trabajar sobre las mismas, tener la necesidad de realizar búsquedas  en forma más frecuente que la necesidad de realizar inserciones. Por ejemplo si tenemos una lista de personas podríamos querer saber si cierta persona está ingresada, o saber información acerca de la misma. Para estos casos en que queremos realizar consultas sobre la estructura de datos puede ser útil trabajar con una estructura de datos que permita realizar búsquedas rápidas (de orden pequeño).

La estructura que vamos a ver es la Tabla de dispersión o Hash, la cual nos permite acceder a una posición dentro de la misma en orden 1, (O(1) caso promedio), realizando una cantidad fija de operaciones. De esta forma nos aseguramos de llegar a donde deberíamos encontrar la información en forma rápida sin importar la cantidad de elementos que tengamos en la estructura.

Un Hash no es más que un arreglo, en el cual podemos usar dos técnicas de ordenamiento interno. Este ordenamiento define donde colocar un elemento al insertar, pudiendo utilizarse dispersion abierta o dispersión cerrada.

Supongamos que tenemos el siguiente Hash:

En principio no es mas que un arreglo, pero crearemos un puntero en cada celda, de forma que podamos tener cualquier tipo de información guardad dentro de las mismas.

typedef struct tablahash{
int totalDisp;
nodoHash* hash[LARGOHASH+1];
};

Dijimos que el hash nos permite acceder en forma rápida a una de las posiciones dentro del mismo, esto se realiza mediante una función de dispersión que dada cierta entrada o valor, nos devuelve el valor dentro del hash donde debemos buscar la información que nos interesa.

Por ejemplo, si tenemos la lista de personas ingresadas por cédula, y le pasamos el numero de cédula 123456789 la función de dispersión nos devolverá la posición X dentro del hash donde debemos buscar la información de esa persona. Una función de dispersión básica pero útil suele ser sumar los valores ASCII de los caracteres y obtener el resto de dividir entre el largo del Hash, ya que no podemos obtener posiciones fuera del Hash mismo.
Un ejemplo de funcìón de dispersión sería el siguiente:

int calcularClaveInsertar(char const* id) {
int i, disp, length;
disp = 0;
length = strlen(id);
for(i=0; i<length; i++)
disp += id[i];
disp = disp % LARGOHASH;
return disp;
}

Esta función recibe un string y nos devuelve la posición correspondiente al mismo dentro del Hash de largo LARGOHASH.

En el caso de la dispersión abierta lo que haremos al tener una colisión será simplemente tener una lista encadenada en cada nodo, por lo que iremos ampliando la lista a medida que tenemos colisiones. Si por ejemplo tenemo el hash de largo 10, e insertamos las cadenas  ”hola” (104+111+108+97 % 10 = 0), “que” (113+117+101 % 10 = 1), “tal” (116+97+108 % 10 = 1), “hash” (104+97+115+104 % 10 = 0) tendríamos un resultado como el siguiente:

En las posiciones 0 y 1 tuvimos colisiones por lo que tenemos dos listas de dos elementos en cada una. Estos nos lleva a ver que en el peor caso de un hash de dispersión abierta tendremos una única lista de elementos en una sola posición, con lo que nuestro hash será simplemente una lista y no nos será de mucha utilidad.

Por esta razón debemos tomar algunas precauciones al utilizar esta estructura de datos, debemos utilizar una función de dispersión adecuada, es decir que nos devuelva valores lo más distribuidos posibles, debemos utilizar un tamaño de hash mayor a la cantidad de elementos que tendremos o que suponemos llegaremos a tener, y es una buena práctica utilizar un número primo en el largo del hash de forma que nos tengamos muchas colisiones al dividir sobre el largo del hash.

El segundo caso, la dispersión cerrada, no permite la creación de listas, pudiendo haber un solo elemento por cada nodo del hash. Para resolver las colisiones se utilizan funciones de redispersión que permiten buscar otra posición dipsonible para el elemento.

Para las funciones de redispersión tenemos la posibilidad de realizar una función lineal, que al encontrar una colisión sume 1 a la posición encontrada, tratando de encontrar una celda libre a continuación. Por ejemplo si tuviéramos el caso anterior, lo que haríamos hubiera sido insertar la palabra “hola” en la posición 0, luego “que” en la posición 1, cuando vamos a insertar “tal” nos encontramos con la posición 1 ya ocupada, por lo que sumamos 1 y lo insertamos en la posición 2. Cuando vamos a insertar “hash” encontramos la posición 0 ocupada, pasamos a la 1 y lo mismo, sumamos 1 nuevamente y la 2 también esta ocupada por lo que pasamos a la 3 que sí esta libre e insertamos ahí. 

Cuando vamos a buscar un elemento al hash caculamos la función de dispersión, por ejemplo para la palabra “tal”, obtenemos el valor 1, vamos a esa posición y no lo encontramos. Entonces vamos sumando 1 hasta encontrarlo o que la celda sea vacía.

El problema sucede cuando eliminamos un elemento y “cortamos” esta cadena, de forma que no podemos seguir este procedimiento.

-Pseudocodigo

registro par { llave, valor }
 var vector de pares casilla[0..numcasillas-1]
 
 function buscacasilla(llave) {
     i := hash(llave) módulo de numcasillas
     loop {
         if casilla[i] esta libre or casilla[i].llave = llave
             return i
         i := (i + 1) módulo de numcasillas
     }
 }
 
 function busqueda(llave)
     i := buscacasilla(llave)
     if casilla[i] está ocupada   // llave en la tabla
         return casilla[i].valor
     else                     // llave es está en la tabla
         return no encontrada   
 
 function asignar(llave, valor) {
     i := buscacasilla(llave)
     if casilla[i] está ocupada
         casilla[i].valor := valor
     else {
         if tabla casi llena {
             hacer tabla más grande (nota 1)
             i := buscacasilla(llave)
         }
         casilla[i].llave := llave
         casilla[i].valor := valor
     }
 }

 -Bibliografia
 http://www.wanderingbit.com/2008/12/27/hash-tablas-de-dispersion/
http://es.wikipedia.org/wiki/Tabla_hash (Pseudocodigo)