Hashing

María Luisa Velasco Ramírez

• El origen de los algoritmos de hash es la ambición de los científicos por encontrar una forma más rápida de encontrar la información:

• O(1)• Las técnicas de búsqueda basadas en

comparaciones, tal como los enfoques secuénciales no son muy eficientes en velocidad y recuperación de información.

• En ese caso HASHING (también conocido como método de dispersión) es una metodología altamente eficiente para estas operaciones.

• Hashing consiste en una transformación matemática de una clave k con una función h(k) que da como resultado la posición de k en una tabla (llamado también transformación key-to-address o KAT).

• El verbo en inglés 'to hash' significa cortar o mezclar, analógicamente en recuperación de la información hashing significa cortar una parte de la clave y utilizarla como base de la búsqueda.

• La función hash h(k) toma como entrada una clave k y produce como resultado un valor entero distribuido uniformemente en un rango determinado. Este valor se usa como índice para la búsqueda o inserción de un dato en un arreglo llamado también ' tabla de hash ' o también 'tablas dispersas'.

• Por ejemplo: • Para un número 31, su transformación de

clave por medio de sumas (tipo de técnica de transformación de claves) nos genera una dirección 4, por lo tanto se va a colocar el número 31 en la Posición 4.

Posición 1 2 3 4 5 631

• 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.

• Ahora bien, cuando se tienen dos números que generan la misma dirección se tiene una colisión. Por lo tanto se necesita solucionar la colisión, y tenemos dos tipos de direccionamiento:

• 1) Direccionamiento Abierto. • Este tipo de solución de colisiones consiste en

colocar en la siguiente posición vacía el número que generó la colisión.

Posición 1 2 3 4 5 631 41 13

Números a insertar: 31, 41, 13:

Direccionamiento cerrado. • Este tipo de solución de colisiones no se tiene

ningún problema con que se repita la misma dirección, utilizando el uso de listas.

null

null

null

45

null

0

1

2

3

4

5

6

null

Función Modulo(por división)

• Consiste en tomar el residuo de la clave entre el número de componentes del arreglo. Si se tiene un arreglo de N elementos y sea K la clave del dato a buscar o a almacenar. La función hash queda definida como:

• H(k) = (K % N) +1

• Para tener una mejor uniformidad en la distribución, N debe ser un número primo o divisible por muy pocos números. Por lo tanto dato N, si éste no es un número primo se tomará el valor primo más cercano.

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).

• Si las claves, por ejemplo; son enteros de ocho dígitos y la

tabla de transformación tiene mil posiciones, entonces el primero, segundo y quinto dígitos desde la derecha pueden formar la función de conversión. Ejemplo: 72588495 se convierte en 895. El truncamiento es un método muy rápido, pero falla para distribuir las claves de modo uniforme.

Plegamiento:

• La técnica de plegamiento 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.

• Ejemplo:• 13000000 --> 130=130+000+00

12345678 --> 657=123+456+7871140205 --> 118 --> 1118=711+402+0513602499 --> 259=136+024+9925000009 --> 259=250+000+09

Métodos de tratamiento de colisionesEjemplo, aplicando la función módulo para determinar la dirección de la clave:H(k) = (K % N) +1

Prueba cuadrática

Doble hash• Lo que se hace es aplicar una segunda función de dispersión a la

clave, y luego se prueba a distancias h2(x), 2h2(x), ... • Usar una segunda función de hash, diferente de la primera,• para determinar el incremento que usar para repartir las llaves.

• Es muy importante la buena elección de h2(x) y, además, nunca debe ser cero. Si se elige la función:

• h2(x) = R - (x MOD R) • con R un número primo menor que MAX_T, funcionará bien.

• Utilizando como segunda función hash 7-(clave%7) el ejemplo quedaría de la siguiente manera:

80

35

43

54

25

56

13

104

55

K H(k) H’(k)

25 6

43 4

56 7

35 6 7

54 5

13 4 1

80 1

104 5 1

55 6 1

• Si observan, a partir de la segunda función hash, se realizan los incrementos dados de acuerdo a la dirección obtenida, es decir si la dirección obtenida en la segunda función es 4, a partir de la dirección que causó la colisión se realizan incrementos de 4 en 4 hasta encontrar una celda vacía .

Otro Ejemplo

• Teniendo un arreglo de N=10 elementos, para facilidad del cálculo, pero recuerden que preferentemente N debe ser primo.

• Insertar en una tabla Hash cuya función H(k)= clave% N los elementos 3,7,23,34,50,27,14,12

• Manejar las colisiones por:• Exploración lineal.• Exploración cuadrática• Doble hash. Teniendo como segunda función hash : 7-

(dato%7).

0

501 2

123

34

235

346

147

78

279

La primera colisión se presenta con el número 23, la segunda colisión con el número 34 , tercera colisión con el 27 y cuarta con el 14.

Prueba o Exploración Lineal:

1

502

123

34

345

146 7

78

239

2710

Doble hash

La primera colisión se presenta con el 23, con la segunda función hash, los incrementos a partir de la dirección que causó la colisión son de 5 en 5; la segunda colisión sucede con el elemento 27, con la 2ª función hash le corresponde los incrementos de 1 en 1, la cuarta colisión sucede con el número 14, con la 2ª función le corresponde los incrementos de 7 en 7, se debe incrementar a partir de la dirección en dónde se creó la colisión 7 posiciones más y así sucesivamente hasta que encuentre una posición vacía.

Ejercicio:

• Dado un arreglo de tamaño 13; inserta los siguientes datos:

• 19, 24, 15, 28, 37, 26, 52, 27, 40, 50• Indicando qué datos tienen colisión • Teniendo como función hash (dato % tamañoArreglo)• Manejando las colisiones por:• Exploración lineal.• Exploración cuadrática• Doble hash. Teniendo como segunda función hash : 7-

(dato%7).

Fuentes Bibliográficas• Métodos de tratamiento de colisiones, consultado el 20 de febrero de 2009,

disponible en:http://www.itnuevolaredo.edu.mx/maestros/sis_com/takeyas/Apuntes/Administracion_Archivos/Apuntes/Colisiones.PDF

• Hayet,J.B(2008)Tablas Hash, consultado el día 20 de febrero 2009 Disponible en: http://www.cimat.mx/~jbhayet/CLASES/PROGRAMACIONII/clase19.pdf

• Capítulo 7. Tablas de Hash, consultado el día 20 de febrero de 2009, disponible en:http://profesores.elo.utfsm.cl/~tarredondo/info/datos-algoritmos/c7.pdf

• Algoritmos Computacionales: Introducción al análisis y diseño • Sara Baase, Allen Van Gelder. • Editorial Addison Wesley ISBN 9702601428