Este método genera claves o llaves que representen de manera casi unívoca a un documento o conjunto de datos. este método nos permite aumentar la velocidad de búsqueda sin necesidad de tener los elementos ordenados. Cuenta también con la ventaja de que el tiempo de búsqueda es prácticamente independiente del número de componentes del arreglo.
Una importante desventaja de hashing es que el conjunto de posibles claves es siempre mayor al número de espacios disponibles. Es decir, dos o más claves pueden asignarse a la misma dirección en la tabla de hash. Cuando dos claves se direccionan a la misma dirección o bucket se dice que hay una colisión, y a las claves se les denomina sinónimos.
Cuando hay colisiones se requiere de un proceso adicional para encontrar una posición disponible para la clave. Esto obviamente degrada la eficiencia del método, por lo que se trata de evitar al máximo esta situación. Una función de hashing que logra evitar al 100% las colisiones es conocida como hashing perfecto.
Truncamiento
Ignora parte de la clave y se utiliza la parte restante directamente como índice (considerando campos no numéricos y sus códigos numéricos).
Ejemplo:
Se tiene claves de tipo entero de 8 dígitos y para la tabla de transformación tiene mil posiciones, entonces para la dirección(índice) se considera: el primer, segundo y quinto dígito de derecha forman la función de conversión.
clave:72588495 –> h(clave)=728
Plegamiento
Esta técnica consiste en la partición de la clave en diferentes partes y la combinación de las partes en un modo conveniente (a menudo utilizando suma o multiplicación) para obtener el índice.
La clave x se divide en varias partes x1, x2, x3,….xn, donde cada parte (con la única posibilidad de excepción de la última parte, tiene el mismo número de dígitos que la dirección especificada)
H(x)= x1 + x2 + x3 +…+ xn
Ejemplo:
Aritmética Modular
Este método convierte la clave a un entero, se divide por el tamaño del rango del índice y toma el resto como resultado. La función que se utiliza es el MOD(módulo o resto de la división entera).
H(x)= x MOD m Donde m es el tamaño del arreglo. La mejor elección de los módulos son los números primos.
Ejemplo:
Un vector T tiene cien posiciones (0..100). Se tiene que las claves de búsqueda de los elementos de la tabla son enteros positivos. La función de conversión H debe tomar un número arbitrario entero positivo x y convertirlo en un entero en el rango de (0..100)
H(x)= x MOD m Si clave=234661234 MOD 101 = 56 234661234 MOD 101 = 56
Mitad del Cuadrado
Este método consiste en calcular el cuadrado de la clave x. La función de conversión se define como:
H(x)=c. Donde c se obtiene eliminando dígitos a ambos lados de x2.
Ejemplo:
Una empresa tiene ochenta empleados y cada uno de ellos tiene un número de identificación de cuatro dígitos y el conjunto de direcciones de memoria varía en el rango de 0 a 100. Se pide calcular las direcciones que se obtendrán al aplicar la función de conversión por la mitad del cuadrado de los números empleados:
x –> 4205 7148 3350
x2 –> 17682025 51093904 11222500
Por lo tanto H(x) =82 93 22
Colisiones
La función de conversión H(x) no siempre proporciona valores distintos puede suceder que para dos claves diferentes x1 y x2 se obtiene la misma índice(dirección). Se deben encontrar métodos para dar solución a las colisiones que se pueden presentar.
Ejemplo de Colisión:
H(123445678) = 123445678 MOD 101 = 44
H(123445880) = 123445880 MOD 101 =44 Para dos claves distintas 123445678 y 123445880; al aplicar la función H la dirección es 44, por lo tanto ha ocurrido una colisión.
Resoluciones de Colisiones
Un método comúnmente utilizado para resolver una colisión es cambiar la estructura del arreglo de modo que pueda alojar más de un elemento en la misma posición. De modo que cada posición i del vector sea por si mismo un vector capaz de contener N elementos.
El problema que se presenta, es como saber el tamaño de N. Si N es muy pequeño, el problema de las colisiones aparecerá cuando aparezcan N + 1 elementos.
Vídeo resumen del método hashing
Nayth Galaz 