domingo, 15 de mayo de 2011

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+12, P+22, P+32, P+42 
      • 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              


                        

    1 comentario: