TRANSFORMACIÓN DE CLAVES (HASHING)
Una tabla hash es una colección de ítems que se almacenan de tal manera que
sea más fácil encontrarlos más tarde. Cada posición de la tabla hash, a menudo
llamada una ranura, puede contener un ítem y se llama por un valor entero
comenzando en 0. Por ejemplo, tendremos una ranura llamada 0, una ranura
llamada 1, una ranura llamada 2, y así sucesivamente. Inicialmente, la tabla hash
no contiene ningún ítem por lo que cada ranura está vacía.
La correspondencia entre un ítem y la ranura a donde pertenece ese ítem en la
tabla hash se denomina la función hash. La función hash tomará cualquier ítem de
la colección y devolverá un número entero en el rango de nombres de las ranuras,
entre 0 y m-1.
MÉTODO DEL RESIDUO
Consiste en tomar el residuo de la división de la clave entre el numero de
componentes del arreglo.
La función hash queda definida por la siguiente formula:
H(K)=(KmodN)+1
Se recomienda que N sea el numero primo inmediato inferior al numero total de
elementos.
Ejemplo:
Supongamos que tenemos el conjunto de ítems enteros 54, 26, 93, 17, 77 y 31.
Con un arreglo de 11. Nuestra primera función hash, denominada “método del
residuo”, simplemente toma un ítem y lo divide por el tamaño de la tabla,
devolviendo el residuo como su valor hash
(ℎ(𝑖𝑡𝑒𝑚)=𝑖𝑡𝑒𝑚%11)
Una vez calculados los valores hash, podemos insertar cada ítem en la tabla hash
en la posición designada:
Ventajas:
Son una de las funciones más rápidas de búsqueda y nos permiten usar
valores naturales de la llave.
Nos permite lograr una independencia lógica y física, debido a que los
valores de las llaves logran su independencia del espacio de direcciones.
Es considerada la que mejor se desempeña.
Desventajas
El desempeño va a variar entre cada función.
Todo dependerá del contexto en el que se aplique la función.
No permite repetir una misma llave.
No se permite usar registros de longitud variable
MÉTODO MEDIO CUADRADO
Consiste en elevar al cuadrado la clave y tomar los dígitos centrales como
dirección. El numero de dígitos a tomar queda determinado por el rango del índice.
La función hash que definida por la sig. formula:
H(K) = digitos_centrales (K2) + 1
La suma de los digitos centrales de la clave K (elevada al cuadrado) más 1 .
, debe obtener un valor entre 1 y N ( N, tamaño del arreglo).
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. Calcular las direcciones que se obtendrán al aplicar función de
conversión por la mitad del cuadrado de los números empleados:
4205 7148 3350
Solucion
Si elegimos, por ejemplo, el cuarto y quinto dígito significativo, quedaría
Ventajas:
Son una de las funciones más rápidas de búsqueda.
Puede desempeñarse mejor en archivos con factores de carga baja
Desventajas:
No se permite usar registros de longitud variable.
No permite repetir una misma llave.
Produce resultados erráticos dependiendo de la longitud de la llave a utilizar
en la dirección.
Fuentes consultadas:
JOYANES, L. (2008). Fundamentos de la programación. Algoritmos y
Estructura de Datos, 4a Edición. Madrid: McGraw-Hill. .
JOYANES, L.; RODRIGUEZ, L; FERNANDEZ, M. (2003). Fundamentos de
programación Libro de problemas. 2a Edición. Madrid: McGraw-Hill.
AHO, Alfred V.; HOPCROFT, John E.; ULLMAN, Jeffrey D.
(1998). Estructuras de datos y algoritmos. México: Addison Wesley.
