Tablas hash

¿Que es una tabla hash?

Una tabla hash  es una estructura de datos que se usan en aplicaciones que manejan una secuencia de elementos, de forma que cada elemento tiene asociado un valor clave.
Aceleran el proceso de búsqueda de un registro de información según una clave.
provee de un acceso casi directo a dichos registros,  en promedio, una búsqueda puede llegar a requerir sólo uno o dos intentos en la memoria o el archivo que contiene la información.

¿Cómo funciona una tabla hash?

Para usar una tabla hash se necesita:
Una estructura de acceso directo (normalmente un array). 
Una estructura de datos con una clave 
Una función resumen (hash) cuyo dominio sea el espacio de claves y su imagen (o rango) los números naturales.

Las operaciones básicas implementadas en una tabla hash

      Buscar( Tabla t, clave x) 
      Devuelve el elemento de la tabla T[h(x)]
  
  Insertar (Tabla t, elemento k)
      Añade el elemento k, T[h(clave(k)] <-- k
  
  Eliminar (Tabla t, clave x)
      Retira de la tabla el elemento con clave x, T[h(x)] <-- Libre

Las tablas hash se diseñan considerando el problemas de las colisiones esto es dada dos claves distintas x1 , x2, se obtenga la misma dirección o índice, h(x1)=h(x2).

Convierte el dato considerado campo clave (tipo entero o cadena de caracteres) en un índice dentro del rango de definición del array que almacena los elementos.

   h(x): K  --> L
   K : conjunto de claves
   L: conjunto de direcciones de memoria
   
Algunas  aplicaciones de las funciones hash

Identificar algún archivo de computadora independientemente de su nombre o ubicación lo cual es usado en redes P2P o Peer to peer (intercambio de archivos punto a punto) tales como Kazaa, Ares Galaxy, Overnet, BitTorrent, entre otras. 
Identificar un registro en una base de datos y permitir con ello un acceso más rápido a los registros (incluso más rápido que teniendo índices). 

Factor de carga

El parámetro que mide la proporción entre el número de elementos almacenados, n, en una tabla hash y el tamaño de la tabla, m, se denomina factor de carga     λ = n/m. se recomienda elegir m de tal forma que el factor de carga sea  λ ≤ 0.8

Aritmética Modular

h (x)=x modulo m

Genera valores dispersos calculando el resto de la división entera entre la clave x (puede ser una cadena) y el tamaño de la tabla m.
Es recomendable que el tamaño “m” de la tabla sea un número primo mayor, pero cercano al numero de “n” de elementos que se tienen previsto que almacene la tabla.

Ejemplo:

Registros a almacenar n= 900,  campo clave elegido:  número de identificación, elegir el tamaño de la tabla hash y calcular la posición que ocupan los elementos cuyo num. de identificación es: 245643 245981 257135

Solución:

Se toma m = 997 al ser este un num. primo próximo y tiene factor de carga (n/m) aprox. 0.8, se aplica la función de hash de aritmética modular y se obtienen la sig. Direcciones:
h(245646)= 245643/997 = 381
h(245981) = 245981/997 =719
h(257135)= 257135/ 997 = 906

Plegamiento

Técnica que  consiste en partir la clave x en varias partes: x1,x2 … xn. La combinación de las partes de un modoconveniente ( ejem. sumando las partes) da como resultado la dirección del registro, la función hash se define:

h(x)=x1 + x2 +…+xn

Mitad del cuadrado

Consiste en calcular el cuadrado de la clave “x” y luego extraer de este resultado los dígitos que se encuentran en ciertas posiciones, el num. de dígitos a extraer depende del rango de dispersión que se quiera obtener.
Utilizar las mismas posiciones de extracción para todas las claves.

Ejemplo:

Se calculan las direcciones para las claves del ejemplo anterior para:

245643, h(245643) = 483  paso a paso
245643 --> 245643^2 --> 60340483449 --> (dígitos 4,5,y 6 por la derecha) 483

Se repite el procedimiento para las demás claves.

Método de la multiplicación

Genera la dirección de una clave en tres pasos.
Multiplica la clave x por una constante real  0 < R < 1
Determina la parte decimal “d” del num. obtenido en la multiplicación R*x
Multiplica el tamaño de la tabla “m”, por “d”  y al truncarse el resultado se obtiene un num. entero en el rango 0… m-1 que será la dirección dispersa.

Ejemplo:

Tomado a R = 0.6180334, por ejemplo con la clave x =  245981,  m = 1000, la dirección se obtiene de la sig. manera

R * x: 0.6180334 * 245981 --> 152024.4738
d = 152024.4738 – ParteEntera(152024.4738) --> 0.4738
h(245981): 1000 * 0.4738 --> ParteEntera (473.8) --> 473

Este método tiene dos características:
Dos claves con los dígitos permutados, no tienen mayor probabilidad de generar una colisión.
Dos valores de claves numéricas muy próximas, generan direcciones dispersas que pueden estar muy separadas.

Colisiones y resolución de colisiones

Se considerarán dos métodos para resolver colisiones: la exploración de direcciones y el direccionamiento enlazado.

Exploración de direcciones

Inicializar las posiciones de la tabla a un valor que indique vacío, por ejemplo, null.
Se utilizan cuando todos los elementos colisionados o no, se almacenan en una tabla.
Se explora consecutivamente en una secuencia de direcciones hasta que se encuentre una posición libre, métodos involucrados: insertar, búsqueda, eliminar.

Exploración lineal

Fácil de implementar, pero tiene un inconveniente, el agrupamiento de elementos de la tabla.
Sea “p” la dirección que devuelve la función hash, si “p” ya esta ocupada entonces se buscar la primera posición disponible que siga a “p”.
La secuencia de exploración es lineal: p, p+1 … m-1. La tabla se considera circular.

Ejemplo usando exploración lineal

Se tienen 9 elementos: x1, x2,..,x9 la función de dispersión les genera las sig. Direcciones:
Elementos:   x1    x2    x3   x4    x5    x6    x7    x8   x9
h(x):              5      8     11    9      5     7      8      6    14

Aplicando exploración lineal son:
Elementos:   x1    x2    x3   x4    x5    x6    x7    x8   x9
Posición:       5      8      11   9     6       7    10    12  14

Exploración cuadrática:

Es una alternativa para evitar al agrupamiento de los elementos
Sea “p” la dirección que devuelve la función hash, si “p” ya esta ocupada entonces se buscan las direcciones p, p+1, p+4, p+9 … p+i^2, considerando la tabla como un array circular, i = 1, 2, 3 …

Ejemplo usando exploración cuadrática:

Se tienen 9 elementos: x1, x2,..,x9, el tamaño de la tabla es 17, la función de dispersión les genera las sig. Direcciones:
Elementos:   x1    x2    x3   x4    x5    x6    x7    x8   x9
h(x):              5      8     10    8      5    11     6      7     7

Al aplicar la exploración cuadrática queda:
Elementos:   x1    x2    x3   x4    x5    x6    x7    x8   x9
Posición:       5      8     10    9     6     11     7     16   15

Doble dirección dispersa

Si en el intento de insertar o buscar, se produce una colisión, entonces  se obtiene otro desplazamiento con otra función hash, h’(x) = p’.
La secuencia de exploración p, p+p’, p+2p’, p+3p’ … se inspecciona hasta encontrar una posición libre para insertar, el elemento buscado.

Direccionamiento enlazado

Una alternativa a la secuencia de exploración
Se basa en utilizar lista enlazadas ( cadenas de elementos) de tal forma que en cada lista de colocan los elementos que tienen la misma dirección hash.

Resumen tablas hash

Las tablas hash son estructuras de datos para la cuales la complejidad de las operaciones básicas: insertar, buscar y eliminar es constante.
La correspondencia entre un elemento y el índice de la tabla se hace con las funciones de transformación de claves.
Siempre existe la posibilidad de que colisionen dos claves.
Dos criterios deben seguirse al elegir una función hash h(x).
Que la complejidad de la función h(x) sea constante y fácil de evaluar.
h(x)  debe distribuir uniformemente las direcciones sobre el conjunto de índices posibles, de forma que se minimice el número de colisiones.