Hashing

Búsqueda mediante transformación de claves (hashing)
Es un método de búsqueda 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.
Una función de Hash es una caja negra que tienecomo entrada una llave y como salida una dirección
h(K)=address

Ejemplo: h(LOWELL)=4
|[pic] |

Figura 9.1

El hashing es similar al indexamiento en el sentido de asociación entre llaves y direcciones relativas de registros
Pero difiere de los índices en 2 cosas:
• La direccióngenerada por Hash suele ser aleatoria (random).
o No hay una relación aparente entre la llave y la localización del registro correspondiente
• El Hash permite que 2 llaves puedan producir la misma salida --> direcciones iguales, a esto se le conoce como "colisión".  Existen distintos grados de colisiones Figura 9.2
|[pic]|

Figura 9.2

Un Algoritmo de Hash
No existe una fórmula "única" para hash, pero el producirla es un algoritmo que básicamente se presenta en 3 pasos:

1) Representar la llave de manera numérica (siempre que no sea de por sí un número)
Una buena opción es usar los valores ASCII o bien los Unicode de las letras

LOWELL=  L   O W  E   L  L   _   _  _   _   _   _
                     76 79 87 69 76 76 32 32 32 32 32 32

1.- Restas sucesivas:
Esta función se emplea con claves numéricas entre las que existen huecos de tamaño conocido, obteniéndose direcciones consecutivas. Un ejemplo serian los alumnos de ingeniería en sistemas que entraron en el año 2005 sus números de control son consecutivos y esta definido el numero de alumnos.
05210800-05210800»» 0
05210801 -05210800»» 1
05210802 -05210800»» 2
…
05210899 -05210800»» 99
2.- Aritmética modular:
El índice de un número es resto de la división de ese número entre un número N prefijado, preferentemente primo. Los números se guardarán en las direcciones de memoria de 0 a N-1. Este método tiene el problema de que dos o más elementos pueden producir el mismo residuo y un índice puedeser señalado por varios elementos. A este fenómeno se le llama colisión. Si el número N es el 7, los números siguientes quedan transformados en:
1679 »> 6
4567 »> 3
8471 »> 1
0435 »> 1
5033 »> 0
Mientras mas grande sea número de elementos es mejor escoger un número primo mayor para seccionar el arreglo en más partes. El número elegido da el número de partes en que se secciona el arreglo, ylas cada sección esta compuesta por todos los elementos que arrojen el mismo residuo, y mientras mas pequeñas sean las secciones la búsqueda se agilizara mas que es lo que nos interesa.
3.- Mitad del cuadrado:
Consiste en elevar al cuadrado la clave y coger las cifras centrales. Este método también presenta problemas de colisión.
709^2=502681 –> 26
456^2=207936 –> 79
105^2=11025 –> 10879^2=772641 –> 26
619^2=383161 –> 31
Nota: en caso de que la cifra resultante sea impar se toma el valor número y el anterior.
4.- Truncamiento:
Consiste en ignorar parte del número y utilizar los elementos restantes como índice. También se produce colisión. Por ejemplo, si un número de 7 cifras se debe ordenar en un arreglo de elementos, se pueden tomar el segundo, el cuarto y el sexto para formarun nuevo número:
5700931 »> 703
3498610 »> 481
0056241 »> 064
9134720 »> 142
5174829 »> 142
5.- Plegamiento:
Consiste en dividir el número en diferentes partes, y operar con ellas (normalmente con suma o multiplicación). También se produce colisión. Por ejemplo, si dividimos el número de 7 cifras en 2, 2 y 3 cifras y se suman, dará otro número de tres cifras (y si no, se toman las tres...