6.3 Búsqueda por funciones de Hash

Búsqueda por funciones de Hash 

Es un método que aumenta la velocidad de búsqueda, pero que no requiere que los elementos estén ordenados. Consiste en asignar a cada elemento un índice mediante una transformación del elemento. Esta correspondencia se realiza mediante una función de conversión, llamada función hash.

*”Supongamos que tiene una colección de datos, cada uno de ellos es identificado por una clave. Es claro que resulta atractivo tener acceso a ellos de manera directa; es decir, sin recorrer algunos datos antes de localizar el buscado. El método por transformación de claves permite realizar justamente esta actividad; es decir localizar el dato en forma directa. El método trabaja utilizando una función que convierte una clave dada en una dirección -índice- dentro del arreglo.”

La función hash (h) aplicada a la clave genera un índice del arreglo que permite acceder directamente al elemento.
i=H(clave)

Esta función hash debe de ser simple de calcular y asignar direcciones de la manera mas uniforme posible. Es decir, debe generar posiciones diferentes dadas dos claves también diferentes:

H(k1)=i1          H(K2)=i2           K1≠K2

  
Si esta condición no ocurre hay una colisión, es decir la asignación de una misma dirección a dos o mas claves distintas.

H(K1)=1       H(K2)=i               K1≠K2

En este contexto, para trabajar con este método de búsqueda se debe seleccionar previamente:

• Una función hash que sea fácil de calcular y distribuya uniformemente las claves. 
• Un método de contingencia para resolver colisiones. Si estas se presentan, se contara con algún método que genere posiciones alternativas.

Funciones hash comunes:

• Función hash por modulo: división. 

H(K)=(KmodN)

• Función hash cuadrado. 

H(K)=digitCent(k^2)

Métodos de solución de colisión comunes:

• Reasignación lineal 
• Doble hash 
• Encadenamiento

VENTAJAS Y DESVENTAJAS

VENTAJAS

• El tiempo de búsqueda es independiente del numero de componentes del arreglo. 
• Es muy útil en archivos extensos y grandes cantidades de datos. 
• Gran versatilidad.

DESVENTAJAS

• Planteamiento e implementación complicada. 
• No merece la pena en arreglos pequeños. 
• Puede ser difícil solucionar colisiones. 
• Requiere mucho análisis de la función hash y claves a usar.