El origen de los algoritmos de hash es la ambición de los científicos
por encontrar una forma más rápida de encontrar la información
| Tipo de Búsqueda |
Complejidad |
| Búsqueda Secuencial |
O(N) |
| B-Trees |
O(logk N) |
| ??? |
O(1) |
Una función de Hash es una caja negra que tiene como entrada una llave
y como salida una dirección
|
|
El hashing es similar al indexamiento en el sentido de asociación entre
llaves y direcciones relativas de registros
Pero difiere de los índices en 2 cosas:
La dirección generada por Hash suele ser aleatoria (random).
No hay una relación aparente entre la llave y la localización del registro correspondiente
El Hash permite que 2 llaves puedan producir la misma salida --> direcciones iguales, a esto se le conoce como "colisión". Existen distintos grados de colisiones Figura 9.2
|
En el ejemplo que mostramos en la sección anterior la función de Hash se basa en lo siguiente:
| Llave |
ASCII |
Producto |
Dirección |
| BALL |
66 65 |
66x65=4290 |
290 |
| LOWELL |
76 79 |
76x79=6004 |
004 |
| TREE |
84 82 |
84x82=6888 |
888 |
A simple vista notamos que nuestra función de hash es pobre ya que fácilmente
habrán llaves que generen la misma dirección ej (OLIVIER),
a éstas llaves que generan las mismas direcciones se les llama "sinónimas".
Idealmente lo que se buscaría es tener un "algoritmo de hash perfecto"
en el cual no ocurran colisiones y siempre nos garantice direcciones diferentes.
Pero desafortunadamente esto es casi imposible, se dice que 1 de 10^120000
algoritmos evitarían dichas colisiones, así que hay que acostumbrarse
a la idea de trabajar y lidiar con colisiones.
Para reducir el número de colisiones se tienen algunas soluciones:
Propagar los registros: Buscar funciones que distribuyan muy aleatoriamente
los registros podemos evitar "agrupaciones" de llaves que produzcan las
mismas direcciones
Usar memoria extra: En el ejemplo anterior planteamos tener una
dirección de entre 1000 posibles, el uso de memoria extra se basa
en proponer un espacio de direcciones posibles mucho más grande que
el número de registros a usar, de modo que si vamos a insertar 100
registros un espacio de 500 direcciones nos una mejor opción de
esparcir mejor.
Colocar más de un registro en una dirección: A diferencia de los casos anteriores donde cada dirección almacena únicamente un registro, este concepto se basa en "buckets" o cubetas de datos en cada dirección, ahí se colocan algunos (casi todos) los registros que colisionan de manera que al hacer una búsqueda debemos recuperar la cubeta entera y ahi buscar por el registro deseado.
No existe una fórmula "única" para hash, pero el producirla es un algoritmo que básicamente se presenta en 3 pasos:
1) Representar la llave de manera numérica (siempre que no sea de por sí un número)
Una buena opción es usar los valores ASCII o bien los Unicode de las letras
LOWELL= L O W E L L _ _ _ _ _ _
76 79 87 69 76 76 32 32 32 32 32 32
2) Plegar y Agregar
Combinar algunos de estos números para generar pequeños trozos con los que podamos trabajar
76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 32
De manera que podemos hacer algunas operaciones matemáticas con dichos números para finalmente obtener un número del cual obtendremos la dirección
7679 + 8769 + 7676 + 3232 + 3232 = 30 588
Nota: Respecto a la implementación se puede dar el caso de formar números demasiado grandes, tanto que llegue al overflow del tipo de datos que estemos usando. Para solucionar esto podemos usar funciones como el "mod" intermedias para no tener ese problema.
3) Dividir por un número primo y usar el resultado como dirección
Los archivos de hash por lo general suelen limitarse a un cierto rango de direcciones posibles para aprovechar mejor el concepto de memoria. de manera que podemos concluir nuestro algoritmo con la fórmula:
a= s mod n
donde a es la dirección resultante, s es la suma o resultado de los pasos anteriores y n el número de direcciones posibles en el archivo
Existen innumerables operaciones adicionales que pueden aplicarse en las fórmulas, así como las técnicas para limitar el valor final. Entre ellas se encuentran: elevar a alguna potencia, raíz cuadrada, convertir los números de base (hexadecimal, octal), etc...
Continuando con las soluciones para colisiones analicemos el uso de memoria.
Es posible predecir cómo se van a distribuir los registros en un archivo,
esto se hace a través de probabilidades.
La Distribución e Poisson
Probabilidad de que la dirección "b" sea escogida
p(B) = b = 1/ N
N= número de direcciones posibles
Probabilidad de que la dirección no sea escogida "a"
p(A) = a = (N-1)/N = 1 - (1/N)
La probabilidad de que una posición sea escogida 2 veces
p(BB)= b x b
De manera más general tenemos la función de Poisson para nuestros
fines:
La probabilidad de que "x" registros tengan la misma dirección
p(x)= (r/N)^x e^(- r/N)
x!
donde N es el número de direcciones disponibles
r es el número de
registros a insertar
x número de registros
asignados a alguna dirección
Ejemplo: N=1000 y r= 1000
p(2)= 0.184
p(3)= 0.061
p(4)= 0.015
Por otro lado si tenemos N direcciones, el número de direcciones con
x colisiones será:
Np(x)
Densidad del archivo
Para complementar las probabilidades anteriores podemos analizar otro dato
más, la densidad del archivo.
Número
de registros = r = densidad del archivo
Número de
espacios N
Si tenemos por ejemplo un archivo donde estamos considerando 100 direcciones
(espacios) y tenemos 75 registros entonces la densidad será de:
75 / 100 = 0.75 = 75 %
Este valor no nos indica el porcentaje de espacio en el archivo real, es
solo la relación entre el espacio físico y el de direcciones,
mientras más densa sea la relación mayor será
el número de colisiones
El algoritmo es el más popular y de hecho bastante simple:
Cuando insertamos un registro obtenemos su dirección con la función Hash
Si la dirección esta libre entonces lo insertamos ahí
En caso contrario se busca la primer dirección subsecuente que esté disponible y ahí se inserta
Es importante recordar que nuestro archivo puede (debe en muchos casos) tener un número fijo de direcciones posibles, de manera que si alcanzamos ese número máximo de direcciones entonces debemos buscar un espacio disponible desde el inicio del archivo. Si no queda ninguno entonces quizás tuvimos un error en nuestros cálculos y planeación del archivo.
Nota: con espacio disponible nos referimos a un espacio "reutilizado" o
bien a un espacio vacío, considerando que al eliminar un registro
lo que hacemos es reutilizar su espacio.
|
Para las búsquedas
Se obtiene el hash correspondiente
A parte de esa dirección empezamos a buscar por el registro deseado o un espacio vacío
En caso de encontrar un espacio totalmente vacío (nuevo, no reutilizable) entonces podemos afirmar que el registro no se encuentra en nuestro archivo.
Si se alcanza el final del archivo y no se encuentra el registro buscado ni un espacio vacío entonces seguimos buscando desde el inicio del archivo hasta volver al punto de partida (dirección original del hash).
|
La idea es muy similar a la que se presentó en la sección
anterior, sólo existen algunas diferencias notables:
Cada dirección representa una agrupación de datos (cubeta)
Aquí el porcentaje de colisiones es mayor, así debe ser
para aprovechar el concepto de agrupación
Cuando una cubeta se llena (Figura 9.5) entonces tenemos un overflow y debemos
buscar una cubeta disponible para seguir insertando. Afortunadamente este
caso no sucede muy a menudo
| Green... |
Hall... |
|
| Jenks... |
||
| King... |
Land... |
Marks... |
Distribución en el almacenamiento por cubetas
Respecto a las fórmulas de distribución la expresión
de Poisson permanece intacta ya que el cálculo es igual solo que
aquí nos interesa tener un mayor número de colisiones por
dirección.
Por otro lado para la densidad si tendremos una ligera variación,
de manera que el cálculo ahora se obtendrá como:
r = Número
de registros
bN Registros por
cubeta X Número de espacios o direcciones
a) Double Hashing
Esta técnica se basa en la idea de generar otro hash, quizás
con un formula diferente.
De manera que si el hash de una llave nos da por ejemplo 5 y ya existe un
registro en esa posición entonces se vuelve a aplicar otro hash que
nos de una dirección más dispersa por ejemplo 505 y de alguna
manera nos garantice menos colisiones. Es importante aclarar que este método
no eliminar las colisiones solo no ayuda a encontrar más rapidamente
un registro en un espacio donde de antemano sabemos que existe este problema.
b) Chained Progressive Overflow
La idea, como se muestra en la figura 9.6, es muy simple y se basa en crear
una lista ligada entre los distintos registros "sinónimos" de manera
que nos podemos desplazar entre aquellos que colisionan de una manera más
ágil y natural.
|
c) Chaining with Separate Overflow Area
Aquí se emplea nuevamente el concepto de encadenamiento a través
de una lista ligada, con la diferencia que aquellos registros "sinónimos"
que colisionan se van almacenando en un archivo aparte llamado "Overflow
Area" (figura 9.7), de manera que en el archivo de datos (Primary Data Area)
sólo se almacena la cabeza de dicha lista.
|
d) Scatter Tables
La idea es parecida a la anterior sólo que aquí no existe
un área primaria de datos, sólo apuntadores hacia distintas
cabeceras de listas donde residen aquellas llaves "sinónimas" que
producen la misma dirección (figura 9.8). Los detalles de implementación
pueden variar, desde algunas no muy convenientes como el usar muchos archivos
para las diversas listas o bien el implementar en un solo archivo una "lista
de listas".
|
En la sección 9.3 se mencionaron varias técnicas relacionadas
con Hash y el manejo de colisiones, dichas técnicas se basan en una estructura
estática, es decir, se calcula un cierto número de posiciones
posibles (registros) y en base a este supuesto se amplía el espacio de
direcciones y en consecuencia se disminuyen las colisiones.
Desafortunadamente este esquema "estático" no es muy adecuado para la
mayoría de las aplicaciones ya que normalmente no se tiene un estimado
del número de registros que se almacenarán, de manera que se requiere
una estructura también basada en Hash pero que sea más dinámica
de modo que permita "crecer" y adecuarse a cualquier número de elementos;
así surge el Hash Extendido.
El algoritmo de Hash Extendido se basa en una estructura de recuperación
conocida como "trie", la cual se encuentra dentro del grupo de búsquedas
por radio, esto debido a que se presenta un árbol donde cada rama presenta
un radio de posibilidades hacia donde moverse. en la figura 9.9 tenemos un radio
de 26 que son las letras del alfabeto.
|
De manera que el "radio" definirá el número de ramas posibles
desde cada nodo, en la figura 9.10 el radio es igual a 10 ya que únicamente
emplea números.
|
Para el caso del hash extendido, el trie que se emplea es de radio 2, utilizando
como valores posibles el 1 y el 0, significando un bit. De manera que las
decisiones de "a qué rama moverse" se definirá como una decisión
bit por bit. Así, si buscamos alguna llave cuyo hash produce una dirección
empieza con "11" entonces recuperaremos la "cubeta C".
|
Como se puede observar le "trie" es una estructura en forma de árbol,
pero si tratamos de manejarlo como tal tendremos un caso similar al indexamiento
tradicional resultando la mejor solución en un B-Tree. Así que
para poder aprovechar los beneficios del trie lo que se hace es representarlo
a manera de arreglo de registros (cubetas en la mayoría de los casos)
contiguos, al cual se le conoce como "directorio".
Para convertir el trie a directorio lo primero que se debe hacer es representar
el árbol como una estructura completa donde existan al mismo nivel el
máximo número de hojas posible (Figura 9.12a), posteriormente
elaboramos el arreglo en un archivo de manera que utilicemos todo el rango de
direcciones posibles (00,01,10,11) donde cada dirección contendrá
un apuntador a la cubeta correspondiente.
|
Manejando el overflow
La gran ventaja de esta estructura es que permite de una manera muy sencilla
manejar el overflow en las cubetas, supongamos que existe un overflow en "A",
gracias a que de antemano teníamos reservada una dirección extra
(la rama adicional del árbol) simplemente usamos esa dirección
para apuntar hacia la nueva cubeta "D".
|
Por otro lado supongamos que el overflow ahora ocurre en "B", a diferencia
del ejemplo anterior aquí no tenemos una dirección extra para
relacionar a la nueva cubeta "D". De manera que dinámicamente el
trie deberá crecer ahora a 3 bits de profundidad (figura 9.14a).
Nuevamente completamos el árbol de 3 niveles para tener todas las
hojas completas (figura 9.14b) y para formar el directorio debemos hacer
un "ajuste" de manera que ahora el rango de direcciones irá de 000
hasta 111 (Figura 9.14c).
|
En esta sección se omiten los detalles de implementación, pero
cabe mencionar algunos de ellos:
Las direcciones obtenidas por el hash suelen leerse de derecha a izquierda, ejemplo:
Supongamos que vamos a ingresar la llave 45 y su hash nos da 000 0010 1110 0011, naturalmente a la izquierda siempre tendremos muchos 0s así que tendríamos muchas colisiones para esos valores así que se opta por empezar a la derecha, de modo que tendríamos 1100 0111 0100 0000, y por lo tanto la llave se almacenaría en la cubeta "C"
Para la eliminación lo que se debe hacer es "colapsar" el directorio de registros, buscando aquellas cubetas que sean vecinas.
El concepto de Hash es un caso ideal en la recuperación de información O(1)
El Hash tradicional es muy eficiente pero tiene 2 problemas principales: colisiones y el hecho de ser estático
El Hash extendido es una estructura relativamente moderna que promete ser mejor que el B-Tree, desafortunadamente existen algunas deficiencias que lo limitan, entre ellas:
No se tienen algunas métricas importantes acerca de la capacidad de cada cubeta
Al igual que el BTree la estructura crece dinámicamente y permite búsquedas de alta velocidad; pero para el acceso secuencial (B+Tree) es una ventaja que sigue ganando la competencia.