- HASHING *******
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 h(K)=address
Ejemplo: h(LOWELL)=4
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). o 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
Un Algoritmo de Hash 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…
Distribución de un archivo de Hash 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
