Hash

TABLAS HASH
[pic]

1. INTRODUCCIÓN.
Una aproximación a la búsqueda radicalmente diferente a las anteriores consiste en proceder, no por comparaciones entre valores clave, sino encontrando alguna función h(k) que nos dé directamente la localización de la clave k en la tabla.
La primera pregunta que podemos hacernos es si es fácil encontrar tales funciones h. La respuesta es, en principio,bastante pesimista, puesto que si tomamos como situacion ideal el que tal función dé siempre localizaciones distintas a claves distintas y pensamos p.ej. en una tabla de tamaño 40 en donde queremos direccionar 30 claves, nos encontramos con que hay 4030 = 1.15 * 1048 posibles funciones del conjunto de claves en la tabla, y sólo 40*39*11 = 40!/10! = 2.25 * 1041 de ellas no generan localizacionesduplicadas. En otras palabras, sólo 2 de cada 10 millones de tales funciones serian 'perfectas' para nuestros propósitos. Esa tarea es factible sólo en el caso de que los valores que vayan a pertenecer a la tabla hash sean conocidas a priori. Existen algoritmos para construir funciones hash perfectas que son utilizadas para organizar las palabras clave en un compilador de forma que la búsqueda decualquiera de esas palabras clave se realice en tiempo constante.
Las funciones que evitan valores duplicados son sorprendentemente dificiles de encontrar, incluso para tablas pequeñas. Por ejemplo, la famosa "paradoja del cumpleaños" asegura que si en una reunión están presentes 23 ó más presonas, hay bastante probabilidad de que dos de ellas hayan nacido el mismo dia del mismo mes. En otraspalabras, si seleccionamos una función aleatoria que aplique 23 claves a una tabla de tamaño 365 la probabilidad de que dos claves no caigan en la misma localización es de sólo 0.4927.
En consecuencia, las aplicaciones h(k), a las que desde ahora llamaremos funciones hash, tienen la particularidad de que podemos esperar que h( ki ) = h( kj ) para bastantes pares distintos ( ki,kj ). El objetivo será puesencontrar una función hash que provoque el menor número posible de colisiones (ocurrencias de sinónimos), aunque esto es solo un aspecto del problema, el otro será el de diseñar métodos de resolución de colisiones cuando éstas se produzcan.

2. FUNCIONES HASH.
El primer problema que hemos de abordar es el cálculo de la función hash que transforma claves en localizaciones de la tabla. Másconcretamente, necesitamos una función que transforme claves(normalmente enteros o cadenas de caracteres) en enteros en un rango [0..M-1], donde M es el número de registros que podemos manejar con la memoria de que dispongamos.como factores a tener en cuenta para la elección de la función h(k) están que minimice las colisiones y que sea relativamente rápida y fácil de calcular, aunque la situaciónideal sería encontrar una función h que generara valores aleatorios uniformemente sobre el intervalo [0..M-1]. Las dos aproximaciones que veremos están encaminadas hacia este objetivo y ambas están basadas en generadores de números aleatorios.

Hasing Multiplicativo.
Esta técnica trabaja multiplicando la clave k por sí misma o por una constante, usando después alguna porción de los bits delproducto como una localización de la tabla hash.
Cuando la elección es multiplicar k por sí misma y quedarse con alguno de los bits centrales, el método se denomina el cuadrado medio. Este metodo aún siendo simple y pudiendo cumplir el criterio de que los bits elegidos para marcar la localización son función de todos los bits originales de k, tiene como principales inconvenientes el que las claves conmuchos ceros se reflejarán en valores hash también con muchos ceros, y el que el tamaño de la tabla está restringido a ser una potencia de 2.
Otro método multiplicativo, que evita las restricciones anteriores consiste en calcular h(k) = Int[M * Frac(C*k)] donde M es el tamaño de la tabla y 0 1, las fórmulas paroximadas son:
[pic]
Estas expresiones se aplican incluso cuando Ó>>1, por lo que...