Funciones HASH - Algoritmos y Programación II

La tabla HASH es una forma de insertar elementos en un arreglo, dicha inserción no depende de una comparación de valores (mayor o menor) sino que depende de una función determinada (f(x), siendo "x" el elemento a insertar. Estas funciones de dispersión pueden ser las siguientes:

• Aritmética modular:  f(x) = x módulo de m; En lenguaje C f(x) = x % m. Siendo "x" el elemento y "m" el tamaño de la tabla.
• Plegamiento:  X = X1 X2 X3 X4...Xn  -->  f(x) = X1+X2+X3+X4+...+Xn.
• Mitad del cuadrado: Calcula  X²  y se extraen determinados dígitos del mismo.
• Método de la multiplicación: Se calcula lo siguiente:
• R* X
• D = R+X-L[(R*X)]
• f(X) = [M*D]                    Siendo X el dato y R un valor real.

Clasificación de las tablas de hash:

Tabla de hash abierta: Esta tabla contiene en cada una de las posiciones del arreglo una lista. De esta forma:

• Tabla de hash cerrada: En este tipo de tabla, a diferencia del anterior, solo puede haber un elemento por casilla en la tabla. Se puede dar el caso donde dos elementos distintos, al aplicarle a función de dispersión, arrojan la misma posición, estas situaciones son llamadas COLISIONES, que se pueden resolver de la siguiente manera:
• Exploración lineal: Consiste en sumar una unidad a la posición obtenida hasta encontrar una casilla disponible, es decir, P= P, P+1, P+2... 
• Exploración cuadrática: En este caso la colisión se resuelve así: P= P, P+1², P+2², P+3², P+4²… 
• Doble dirección dispersa: Sea f(x)= p y otra función f'(x) = p' se genera lo siguiente: P= P, P+P', P+2P', P+3P', P+4+'...

NOTA: Si la cantidad de elemento a insertar es "m", es recomendable que el tamaño de la tabla sea el primer número primo inmediatamente superior a m. 

Para  observar un ejemplo de una tabla de hash abierta en el lenguaje de programación C presiona aquí:  https://docs.google.com/leaf?id=0B_tJ5vXCSmOoNWY3MmU5YjQtYmFkZS00OGM4LThkY2EtYjA1MjY3MDNiOTU0&hl=en    

Para observar un ejemplo de una tabla de hash cerrada en el lenguaje de programación C presiona aquí:  https://docs.google.com/leaf?id=0B_tJ5vXCSmOoNTVjYjVjYzgtOGYyMC00MDk0LWFkMzktYWZkODBiNDI2ODA4&hl=en