Imagen donde se encuentra una tabla de hash.
El objetivo principal de estas tablas es el de realizar inserciones, eliminaciones y búsquedas en un cierto tiempo promedio constante.
La estructura de hash se tiene que construir con 3 elementos básicos:
- Tiene que tener un vector que sea capaz de almacenar N elementos.
- Necesita una función de dispersión que nos deje a partir de la clave obtener el indice o posición en donde se encuentra el dato asociado a la clave (en caso de haber más de un elemento en la misma clave se forma o extiende una lista enlazada en ellos).
- Por ultimo una función de resolución de colisiones.
Análisis asintótico de la tabla hash
Las tablas hash suelen implementarse sobre vectores de una dimensión, también se pueden implementar multi-dimensionales basadas en varias claves. Como en el caso de los arrays, las tablas hash proporcionan tiempo constante de búsqueda promedio O(1), no importa el número de elementos en la tabla. Aunque, en casos particulares malos el tiempo de búsqueda puede llegar a O(n), es decir, en función del número de elementos.
En cuanto a otras estructuras como árboles binarios de búsqueda equilibrados son más rápidos en promedio (tiempo de búsqueda O(log n)) pero la información está ordenada en todo momento.
¿Como funciona?
Las operaciones básicas que se implementan en las tablas hash son las siguientes:
inserción (llave, valor)
búsqueda (llave) y esta devuelve valor
La mayor parte de las implementaciones incluyen borrar (llave), ya que se pueden ofrecer funciones con iteración en la tabla, para incrementarla o vaciarla, incluso algunas tablas permiten almacenar múltiples valores bajo la misma clave.
Funciones hash
Una buena función hash es fundamental para el buen provecho de una tabla hash. Las colisiones son generalmente resueltas por algún tipo de búsqueda lineal, entonces si la función tiende a crear valores similares, las búsquedas resultantes se volverán lentas.
Las funciones hash que se encuentran más utilizadas son:
- Hash de división
- Hash de multiplicación
Si por alguna razón, se necesita una tabla hash con tantos elementos o punteros como una potencia de 2 o de 10, será mejor usar una función hash de multiplicación, independiente del tamaño de la tabla. Se escoge un tamaño de tabla m >= |D| (m mayor o igual al tamaño del diccionario) y un cierto número irracional φ (normalmente se usa 1+5^(1/2)/2 o 1-5^(1/2)/2). De este modo se define h(k)= Suelo(m*Parte fraccionaria(k*φ)).
Proceso de Inserción
- Para poder almacenar un elemento en la tabla hash se tiene que convertir su clave a un número. Esto lo podemos conseguir aplicando la función resumen (hash) a la clave del elemento.
- El resultado de la función resumen tiene que mapearse al espacio de direcciones del arreglo que se usa como soporte, lo cual conseguimos con la función módulo. Después este paso se obtiene un índice válido para la tabla.
- El elemento se almacena en la posición de la tabla obtenido en el paso anterior.
- Si en la posición de la tabla ya había otro elemento, se ha producido una colisión. Este problema se puede solucionar uniendo una lista a cada posición de la tabla, aplicando otra función o buscando el siguiente elemento libre. Estas posibilidades se deben de considerar al momento de recuperar los datos.
Proceso de Búsqueda
- Para poder recuperar los datos, necesitamos únicamente conocer la clave del elemento, a la cual se le aplica la función resumen.
- El valor que obtenemos se mapea al espacio de direcciones de la tabla.
- Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave que la usa en la búsqueda, entonces es el querido. Si la clave es diferente, se ha de buscar el elemento según la técnica usada para solucionar el problema de las colisiones al guardar el elemento.
Resolución de colisiones
Encadenamiento separado o Hashing abierto
Ventajas de la técnica sobre el direccionamiento abierto:
- El borrado es simple
- El crecimiento de la tabla puede posponerse durante mucho más tiempo ya que el rendimiento baja mucho más lentamente incluso cuando todas las casillas ya están ocupadas.
- Muchas tablas hash encadenadas no requieren crecimiento nunca, dado que la degradación de rendimiento es lineal en la medida que se va llenando la tabla.
Imagen que demuestra el encadenamiento.
Direccionamiento abierto o Hashing cerrado
Estas tablas hash de direccionamiento abierto pueden guardar los registros directamente en el array. Las colisiones se resuelven mediante una investigación del array, en el que se buscan distintas plazas del array (secuencia de investigación) hasta que el registro es encontrado o se llega a una casilla vacía, indicando que no existe esa llave en la tabla.
Entre las secuencias de investigación más útiles se encuentran:
- sondeo lineal: es cuando el intervalo de cada intento es constante (con frecuencia 1).
- sondeo cuadrático: es cuando el intervalo de los intentos incrementa linealmente (los indices son descritos en funciones cuadráticas).
- doble hasheo: cuando el intervalo es constante para cada registro que es calculado por otra función de hash.
Ejemplo de seudocódigo de una tabla hash
registro par { llave, valor }
var vector de pares casilla [0,... Ncasillas - 1]
función buscar_casilla (llave) {
i = hash (llave) módulo de Ncasillas
mientras {
if casilla [i] esta libre o casilla[i].llave = llave
return i
i = (i +1) módulo de Ncasillas
}
}
función búsqueda (llave)
i = buscar_casilla (llave)
if casilla [i] está ocupada /* Llave en la tabla */
return casilla[i].valor
else /* Llave está en la lista */
return no encontrada
función asignar (llave, valor) {
i = buscar_llave (casilla)
if casilla [i] está ocupada
casilla[i].valor = valor
else {
if tabla casi llena {
hacer tabla más grande (nota 1)
i = buscar_casilla (llave)
}
casilla[i].llave = llave
casilla[i].valor = valor
}
}
Un ejemplo en donde aplicamos esto en la vida cotidiana es en los directorios telefónicos, donde tenemos que hace runa búsqueda y eliminamos lo que no es o sea similar, y cuando encontramos lo que queríamos habremos terminado nuestra búsqueda (un ejemplo simple).
Referencias:
8.
ResponderEliminar