Ingeníero

Funciones Hash*
Guido Urdaneta 11 de febrero de 2010

1. Introducción
Una función hash es una función que mapea un dato (posiblemente grande y de tamaño arbitrario) de un conjunto U a un dato pequeño, usualmente un número entero comprendido entre 0 y M − 1, el cual puede utilizarse como índice en un arreglo, por ejemplo. Al dato a mapear suele llamársele clave, mensaje u otro nombredependiendo de la aplicación, mientras que al dato mapeado se le puede llamar valor hash, código hash, o simplemente hash. h : U −→ {0, 1, 2, · · · , M − 1} Las funciones hash tienen muchísimas aplicaciones en computación, siendo la búsqueda una de las más importantes. La estructura de datos fundamental para realizar búsquedas usando funciones hash es la tabla hash, en la cual el valor hash se interpretacomo la posición de un arreglo en donde se almacena el valor buscado. Puesto que las funciones hash pueden mapear elementos de un conjunto más grande a uno más pequeño, es posible que dos o más claves sean mapeadas al mismo valor hash. En este caso se habla de una colisión y se desea que la probabilidad de éstas sea muy baja. Los algoritmos de tabla hash básicamente se enfocan en cómo resolverlas colisiones. El enfoque más simple es tener una lista para cada posible valor hash, guardar todas las claves con el mismo valor hash en la lista correspondiente y resolver las colisiones con una búsqueda lineal.

1.1. Propiedades deseadas
1.1.1. Bajo costo

Se desea que el costo computacional de una función hash sea bajo. Por ejemplo, un árbol balanceado permite hacer búsqueda binariarealizando aproximadamente log n comparaciones. Si el calcular la función hash toma un tiempo mayor que realizar log n comparaciones, entonces puede que no tenga sentido usar una tabla hash.
* Tomado

principalmente de TAOCP Volumen 3 (Knuth) y Wikipedia

1

1.1.2.

Uniformidad

Una función hash debe mapear los datos esperados de entrada de la manera más uniforme posible. La razón es queesta es la manera de minimizar el número de colisiones, ya que mientras más colisiones haya, mayor será el tiempo de ejecución de los algoritmos basados en funciones hash. Por ejemplo, si hay muchas claves mapeadas al mismo valor hash en una tabla hash, las búsquedas degenerarán en búsquedas lineales.

2. Algoritmos para implementar funciones hash
2.1. Función hash trivial
Si la clave es losuficientemente pequeña, es posible que ésta pueda usarse como valor hash sin hacer modificaciones.

2.2. Hash de una palabra
Para hacer una función hash que mapee de datos cuyo tamaño es menor o igual al de la palabra de la computadora (típicamente n dígitos binarios) al conjunto de los enteros comprendidos entre 0 y M − 1 (M sería el número de entradas en una tabla hash), existen dos métodosbásicos: 1. El método de división: h(K) = KmodM, donde K es la clave. En este caso se recomienda que M no sea potencia de 2 (ya que el resultado sería tomar los bits menos significativos de la clave ignorando los más significativos) y que tampoco divida a 2k ± a, donde k y a son enteros pequeños. En la práctica, usar números primos que no dividan a 2k ± a (k y a pequeños) suele dar buenos resultados.(( A ) ) 2. El método de multiplicación: h(K) = M w K mod1 , donde w es 2n y A se recomienda que sea un entero relativamente primo a w. Knuth sugiere un buen valor para A/w es la pro(√ ) porción áurea φ −1 = 5 − 1 /2 ≈ 0, 6180339887, ya que en este caso valores sucesivos tenderán a dividir intervalos en del segmento [0, 1) según la proporción áurea. La principal ventaja de este método conrespecto al de división es que el valor M no es muy importante. Nota: la operación xmod1 cuando x es un número con parte fraccionaria, produce como resultado la parte fraccionara. Por ejemplo 5, 43mod1 = 0, 43. La notación x se refiere a la parte entera de x. Por ejemplo, 7, 93 = 7. Si A/w ≈ 0, 6180339887 y M = 1000 entonces h(3) = 1000 ((0, 6180339887 × 3) mod1) = 1000 (1, 8541019661mod1) = 1000 × 0,...