8.3 ALGORITMO DE BUSQUEDA HASH.

Existe un método que puede aumentar la velocidad de 
búsqueda donde los datos no necesitan estar ordenados y 
esencialmente es independiente del número n. Este método 
se conoce como transformación de claves o hashing. El 
hashing consiste en convertir el elemento almacenado 
(numérico o alfanumérico) en una dirección (índice) dentro 
del array.


 La idea general de usar la clave para determinar la dirección 
del registro es una excelente idea, pero se debe modificar de 
forma que no se desperdicie tanto espacio. Esta modificación 
se lleva a cabo mediante una función que transforma una 
clave en un índice de una tabla y que se denomina función 
de Randomización o Hash. Si H es una función hash y X es 
un elemento a almacenar, entonces H(X) es la función hash
del elemento y se corresponde con el índice donde se debe 
colocar X.



El método anterior tiene una deficiencia: suponer que dos 
elementos X e Y son tales que H(X) = H(Y). Entonces, cuando 
un el elemento X entra en la tabla, éste se inserta en la 
posición dada por su función Hash, H(X). Pero cuando al 
elemento Y le es asignado su posición donde va a ser 
insertado mediante la función hash, resulta que la posición 
que se obtiene es la misma que la del elemento X. Esta 
situación se denomina Randomización o Hashing con 
colisión o choque.


Una buena función Hash será aquella que minimice los 
choques o coincidencias, y que distribuya los elementos 
uniformemente a través del array. Esta es la razón por la que 
el tamaño del array debe ser un poco mayor que el número 
real de elementos a insertar, pues cuanto más grande sea el 
rango de la función de randomización, es menos probable que 
dos claves generen el mismo valor de asignación o hash, es 
decir, que se asigne una misma posición a más de un 
elemento.

Funciones Hash más usadas:

1. Hash de División:

Dado un diccionario D, se fija un número m >= |D| (m mayor o igual al tamaño del diccionario) y que sea primo no cercano a potencia de 2 o de 10. Siendo k la clave a buscar y h(k) la función hash, se tiene h(k)=k%m (Resto de la división k/m).

2. Hash de Multiplicación

Si por alguna razón, se necesita una tabla hash con tantos elementos o punteros como una potencia de 2 o de 10, será mejor usar una función hash de multiplicación, independiente del tamaño de la tabla. Se escoge un tamaño de tabla m >= |D| (m mayor o igual al tamaño del diccionario) y un cierto número irracional φ (normalmente se usa 1+5^(1/2)/2 o 1-5^(1/2)/2). De este modo se define h(k)= Suelo(m*Parte fraccionaria(k*φ))