MonografíaEsta es la versión html del archivo
http://www.austral.edu.ar/web/ingenieria/ayed/Hash.doc.
G o o g l e genera automáticamente versions html de los documentos
mientras explora la web.
Para vincularse a esta página o para marcarla, utilice el siguiente
url:
http://www.google.com/search?q=cache:Q8YvJ2L_By8J:www.austral.edu.ar/web/ingenieria/ayed/Hash.doc+resolucion+de+colisiones+en+el+direccionamiento&hl=es
Google no tiene relación con los autores de esta página ni es
responsable de su contenido.
Se han resaltado estos términos de búsqueda: resolucion
colisiones direccionamiento
TAD Tabla Hash
Definición.
Es un conjunto formado por un número arbitrario de elementos distintos (del
mismo tipo), identificado cada uno por una palabra clave diferente, junto con un
conjunto de procedimientos de acceso.
Breve Introducción.
A diferencia de una Búsqueda indexada por claves ordinaria, donde usamos el
valor de las claves como índices de un arreglo y necesitamos indispensablemente
que los mismos sean enteros distintos dentro de un rango equivalente al rango
del Arreglo, utilizar el método de Hashing nos permite manejar aplicaciones de
búsqueda donde no tenemos claves con tan fortuitas propiedades. El resultado es
un método de búsqueda completamente diferente a los métodos basados en
comparaciones, ahora en vez de navegar por las estructuras comparando palabras
clave con las claves en los items, tratamos de referenciar items en una tabla
directamente haciendo operaciones aritméticas para transformar claves en
direcciones de la tabla. Esto último se logra implementando una Función Hash,
que se va a encargar de dicha transformación.
Idealmente , todas las claves van a mapear a direcciones diferentes, pero
es muy frecuente que dos o mas claves diferentes sean transformadas a la misma
dirección, cuando esto pasa, decimos que estamos en presencia de una Colisión.
Es por eso que también debemos implementar algún proceso de resolución de
Colisiones, que se va a encargar de tratar tales situaciones. Uno de los métodos
de resolución de colisiones que existen usa Listas ligadas (Linked lists) y se
lo denomina encadenamiento directo o Hashing abierto el cual es muy útil en
situaciones dinámicas, donde el numero de elementos es difícil de predecir por
adelantado.
El Hashing es un buen ejemplo de balance entre tiempo y espacio. Si no
hubiera limitaciones de memoria, entonces podríamos hacer cualquier búsqueda en
un solo acceso simplemente utilizando la clave como una dirección de memoria.
Este ideal no puede ser llevado a cabo, porque la cantidad de memoria requerida
es prohibitiva cuando las claves son largas. De la misma manera, si no hubiese
limitación de tiempo, podríamos usar un mínimo espacio en memoria usando un
método secuencial. Hashing provee una manera de usar una razonable cantidad de
memoria y tiempo y lograr un balance entre los dos extremos mencionados. En
particular, podemos lograr el balance que deseemos simplemente ajustando el
tamaño de la tabla, sin necesidad de re-escribir código o cambiar algoritmos.
En líneas generales podemos decir, que es razonable esperar búsquedas
(Search), borrados (Delete) e inserciones (Insert) en tiempo constante ,
independientemente del tamaño de la tabla. O sea que es ideal para aplicaciones
que realicen mayoritariamente este tipo de operaciones, por el otro lado,
Hashing no provee implementaciones eficientes para otras operaciones como por
ejemplo Ordenamiento (Sort) o Selección (Select)
Funciones Hash:
Es la que se va a encargar de transformar las claves en direcciones de la
tabla.
Podríamos definir a la función ideal como aquella que distribuya a todos
nuestros objetos lo mas uniformemente posible sobre la gama de valores índice,
es decir, si tenemos una tabla que puede almacenar M items, entonces requerimos
de una función que transforme claves a enteros en el rango [0, M-1] ,que la
salida sea aproximadamente equiprobable para cada entero., y que la distribución
no esté ligada a patrón alguno. Debe ser calculable de modo eficiente, o sea,
estar compuesta de un numero reducido de operaciones aritméticas básicas.
No hay reglas que permitan determinar cual será la función mas apropiada
para un conjunto de claves, para asegurarse de una uniformidad máxima. Hacen un
análisis de las características de las claves, puede sin embargo ayudar en la
elección de la función.
La implementación de la función hash depende del tipo de clave. No va a ser
la misma si la clave es un int, un float o un String
A continuación algunas funciones a modo de ejemplo :
· Función Modulo: Tomamos el resto de la división entre la clave y el numero de
M de items. Estadísticamente se puede verificar que para una mayor uniformidad
en la distribución, M debe ser un número primo, o al menos que sea divisible por
pocos números.
· Función Cuadrado: Elevamos al cuadrado la clave y tomamos los dígitos
centrales como dirección. El número de dígitos a tomar es determinado por el
rango del índice (por ejemplo si tengo 100 índices, tomo solo 2 dígitos)
Otros ejemplos de función, pero para Strings:
· Sumatoria de valores ASCII: Tomamos el resto entre la sumatoria de los valores
ASCII de la cadena de caracteres y el número M (tamaño de la tabla). Como char
es un valor entero que es como mucho 127, para valores de M grandes, voy a
necesitar que las claves sean de una longitud considerable, de otra manera la
distribución no va a ser uniforme.
3. Resolución de Colisiones:
Que hacemos cuando ingresamos una clave en la Función Hash, y ésta nos
devuelve una dirección que ya esta siendo ocupada por otro objeto?
Hay varios métodos de manejar estas situaciones. Vamos a discutir en
profundidad los dos mas simples: Hashing Abierto y Hashing Cerrado
3.1 Hashing Abierto: (encadenamiento directo)
La forma mas sencilla de resolver las colisiones es simplemente crear para
cada dirección de la tabla, una lista encadenada (Linked List) de todos los
elementos cuyas llaves mapean al mismo índice.
Cuando busquemos una clave vamos a tener que recorrer la lista que le
corresponda hasta encontrar nuestro ítem. Definimos el factor de carga como l =
N/M , que va a ser el largo promedio de cada lista.
(N = numero de elementos insertados, M = cantidad de listas)
Las listas pueden dejarse desordenadas o bien mantenerlas ordenadas. Lo mas
frecuente es usar listas desordenadas porque es mas fácil de implementar , y es
mas eficiente, vamos a tener una Inserción de orden constante y una búsqueda
proporcional a l .
En el caso que utilicemos la tabla en su mayor parte haciendo búsquedas va
a ser útil mantener las listas ordenadas, con esto lograremos acelerar las
búsquedas por un factor de 2 a cambio de una Inserción mas lenta.
Como elegir el tamaño M de la tabla?
Deberíamos elegir una M que sea suficientemente chica de manera que no
estemos derrochando una gran cantidad de memoria contigua con links vacíos, pero
lo suficientemente grande de modo que las búsquedas secuenciales sean
eficientes.
La práctica indica que debemos elegir un M que sea aproximadamente entre 1/5 y
1/10 de las cantidad de claves que esperamos que se ingresen en la tabla.
Una de las mayores virtudes de encadenamiento directo es que esta
decisión no es crítica: si se ingresan mas claves de las esperadas, simplemente
las búsquedas van a ser un poco mas lentas que con un M mas grande. Mientras que
si se ingresan menos claves de las esperadas, tendremos una búsqueda
súper-rápida con tal vez cierto derroche de espacio.
3.2 Hashing Cerrado: (direccionamiento abierto)
Si tenemos la posibilidad de predecir con suficiente precisión la cantidad
de elementos que van a ser ingresados en la tabla hash, y tenemos suficiente
memoria contigua disponible para guardar todas las claves con lugar de sobra,
entonces ya no vale la pena usar una estructura de datos secundaria (las listas)
como en Hashing Abierto.
Ahora vamos a necesitar indefectiblemente una tabla mas grande, tal que el
tamaño M sea mayor que la cantidad N de items, valiéndonos de los espacios
vacíos en la tabla para resolver las colisiones. Estos métodos son los que
conocemos como métodos de Hashing Cerrado.
Generalmente , el factor de carga debería estar por debajo de l = 0.5 para
una buena performance. A continuación veremos las 3 estrategias mas comunes para
la resolución de colisiones.
3.2.1 Búsqueda Lineal: (Linear Probing)
Es el más simple de los métodos de Hashing Cerrado . Cuando nos encontramos
en presencia de una colisión, simplemente buscamos, avanzando de a un lugar por
vez, el próximo lugar vacío en la tabla, y guardamos ahí la clave si no está
repetida.
La inspección comienza en la posición a la cual nos lleva la función hash,
ahí tenemos tres posibles situaciones: si la posición actual de la tabla
contiene un ítem cuya clave es igual a la que buscamos, entonces tenemos un hit,
si la posición de la tabla está vacía, tenemos un miss, de otra manera seguimos
con la próxima posición en el siguiente índice, continuando (volviendo al
principio de la tabla si llegamos al final) hasta que encontremos o un miss o un
hit.
Al igual que en Hashing abierto, la performance del método de linear
probing depende del factor l. Aunque la forma de calcular l = N/M ,es la misma,
lo interpretamos de manera diferente. En Hashing Abierto l es el porcentaje de
posiciones ocupadas en la tabla y por supuesto debe ser menor que 1.
Para con un l chico , esperamos que la mayoría de las búsquedas encuentren
una posición vacía en unos pocas inspecciones (probes) en la tabla. Mientras que
si el factor es muy cercano a 1 (tabla casi llena) una búsqueda puede llevar un
gran numero de inspecciones e incluso puede caer en un ciclo infinito, por eso
no se debe cargar la tabla hasta valores muy cercanos al llenado total
Efectos indeseados: Clustering primario.
El costo promedio de la búsqueda lineal depende fuertemente de la
independencia de las inspecciones respecto de la inspección anterior .
Desafortunadamente estas no son totalmente independientes, lo cual provoca que
se generen en ciertas zonas de la tabla, grupos contiguos de datos (clusters)
mientras que otras zonas permanecen vacías. Si este efecto es muy pronunciado,
la búsqueda se tornará principalmente secuencial, perdiendo así las ventajas del
método hash.
La cantidad promedio de celdas inspeccionadas en una inserción usando Búsqueda
lineal es :
Como podemos apreciar en el gráfico, a partir de l = 0.80, la cantidad de
inspecciones necesarias para una inserción, hace que este método sea
insostenible.
3.2.2 Búsqueda Cuadrática: (Quadratic Probing)
Búsqueda cuadrática es un método de resolución de colisiones mejora el
problema del agrupamiento primario (Clustering) de la Búsqueda Lineal. El
proceso es similar al anterior, pero mientras que la función de inspección de
Búsqueda Lineal es f(i) = i ; ahora vamos a usar una función cuadrática f(i) =
i2, entonces , en una inserción cuando encontremos un lugar ocupado avanzaremos
primero 1, luego 22 ,luego 32 ,etc. hasta encontrar un lugar vacío.
Si bien Búsqueda cuadrática mejora sustancialmente el problema de
Clustering Primario, tiene la desventaja de que pueden quedar celdas sin visitar
(Clustering Secundario), en particular, si la tabla esta llena en mas de un 50%
(l>0.5) , no hay garantías de encontrar una celda vacía si el tamaño de la tabla
no es PRIMO.
Sin embargo, si el tamaño de la tabla es un número primo esta Garantizado que
podremos insertar un nuevo elemento.
Como borrar una clave de una tabla con Búsqueda lineal o cuadrática? No
podemos simplemente borrarla, porque los items que fueron insertados después no
van a ser encontrados ya que la búsqueda va a ser interrumpida por el agujero
que dejo el borrado. Una solución es aplicar rehashing para los items
insertados posteriormente, otra mas sencilla sería poner un sentinela que ocupe
el espacio de la clave borrada.
3.2.3 Hashing Doble
La Solución definitiva para eliminar casi completamente el Clustering tanto
primario como secundario de los métodos citados anteriormente, es el Hashing
Doble. En el cual una segunda función es usada para manejar la resolución de
colisiones. La segunda función debe ser elegida con cuidado, de otra manera el
programa puede no funcionar. No puede haber ningún caso en la segunda función
evalué a cero, ya que esto generaría un ciclo infinito, también es importante
que el valor de la segunda función sea relativamente primo al tamaño de la
tabla, de otra manera las secuencias serían muy cortas.
Una segunda función simple y efectiva podría ser la siguiente:
En Hashing doble, la única forma de borrar items es reemplazándolos por
sentinelas, de otra manera se perderían algunas claves.
3.2.4 Re-Hashing
Cuando las tablas se llenan demasiado, el tiempo de ejecución de algunas
operaciones va a empezar a ser muy largo. Sobre todo cuando combinamos muchas
inserciones con borrados. Una solución es crear otra tabla que sea el doble de
grande (con una nueva función hash asociada) y procesar la tabla hash original
entera, computando el nuevo valor hash para cada (no-sentinela) elemento e
insertarlo en la nueva tabla.
Esta operación completa es lo que denominamos Re-Hashing. Obviamente es una
operación muy costosa (orden N), pero dado que no va a pasar muy frecuentemente,
no esta nada mal y su efecto va a pasar prácticamente desapercibido. Solo el
desafortunado usuario cuya inserción provoque un Re-Hash va a sentir el efecto.
En que momento aplicar el Re-Hash queda a criterio del programador, algunas
posibilidades son:
- Aplicar Re-hash cada vez que la tablaa este llena en mas de un 50%
- Aplicar Re-hash solo cuando una inserrción falla
- Aplicar Re-hash cuando el factor de ccarga l supera un valor estipulado.
Grafico que muestra la evolución del tamaño de una tabla-hash respecto a la
cantidad de elementos que tenga. Criterio de rehashing l > 0.5
El método de Re-Hashing es apropiado para usar en implementaciones de tabla
de símbolos donde los patrones de uso son impredecibles, ya que puede manejar
tablas de todos los tamaños de una forma razonable.
3.2.5 Hashing Extensible
Cuando la cantidad de información con la cual debemos lidiar es muy grande
para entrar en la memoria, nuestra máxima preocupación pasa a ser la cantidad de
accesos a disco requeridos para obtener datos.
Sea Hashing abierto o cerrado el que usemos, el gran problema es que las
colisiones podrían causar que varios bloques sean examinados durante una
búsqueda, inclusive en una tabla hash bien distribuida.
Extensible Hashing permite que una búsqueda sea ejecutada en 2 accesos a
disco y también las inserciones en unos pocos accesos.
El método es muy parecido a la estructura árboles B, pero fijamos el tamaño
de las hojas o buckets a M, tal que sea igual a la cantidad de items que
entren en un bloque del disco, D va a ser la cantidad de Bits y el tamaño de la
raíz o Directorio va a ser entonces 2D.
Cuando el bucket se llena, lo dividimos en 2 nuevos buckets, mientras
que cuando el Directorio se llena, agregamos un dígito al mismo, duplicando su
tamaño.
La función Hash van a ser los últimos dígitos de la clave (lo que definimos como
D) y va a ir creciendo con el tiempo.
Ejemplo gráfico de una inserción donde es necesario dividir un bucket:
(antes de la inserción)
En este ejemplo la capacidad de los buckets es igual a 3.
Podemos ver como, al insertar la clave #10, que direcciona a 010,
terminamos en el Bucket #0 que esta lleno, entonces tenemos que dividir el
Bucket. Creamos un nuevo Bucket #4. Ahora el Bucket #0 y el #4 van a tener 2
elementos cada uno, todas las claves que direccionen a 00 deben ser puestas en
el Bucket #0 y todas las que direccionen a 01 deben ser puestas en el Bucket #4.
(después de la inserción)
Ahora un ejemplo de expansión del directorio:
(antes de la expansión)
Como la profundidad del bucket iguala la profundidad del directorio,
tenemos que duplicar el directorio. Va a hacer un nuevo Bucket #3. Las claves
que direccionen a 110 van a ser ubicadas en el Bucket #2, y las llaves que
direccionen a 111... van a ser ubicadas en el Bucket #3. Las otras entradas del
directorio deben ser duplicadas. Por ejemplo , las llaves que direccionen a 100
o a 101 van a seguir estando en el Bucket #1. La siguiente imagen nos muestra el
resultado.
Conclusión
Las tablas Hash nos van a ser muy útiles cuando necesitemos operaciones de
Inserción y Búsqueda en tiempos promedio de orden constante.
Vamos a tener que prestar mucha atención al factor de carga, para que la
tabla no pierda sus cualidades; si usamos hashing abierto un factor cercano a 1
es ideal y si usamos hashing cerrado no dejar que el factor supere 0.5 es una
buena idea, de ser necesario podemos aplicar re-hashing.
También tendremos que elegir sabiamente la función hash que mejor
distribuya nuestros datos.
De los distintos tipos de Hashing expuestos en este trabajo, podemos
concluir que:
Linear Probing y Quadratic Probing son los mas rápidos.
Doble Hashing hace el uso mas eficiente de la memoria.
Separate Chaining es el más fácil de implementar.
Y Extensible Hashing es la mejor opción cuando la cantidad de datos es muy
grande para trabajar solo en memoria.
Bibliografía:
- Algorithms in C++ , Robert Sedgewick.
- Algoritmos y estructuras de datos, Nikklaus Wirth.
- Data Structures and Analysis in C++ , Mark Allen Weiss.
- Data Structures & Problem solving in JJava, Mark Allen Weiss.
- National Institute of Standards and Teecnology (www.nist.gov)
http://www.google.com.mx/search?q=cache:Q8YvJ2L_By8J:www.austral.edu.ar/web/ingenieria/ayed/Hash.doc+resolucion+de+colisiones+en+el+direccionamiento&hl=es