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              


                    

Método de ordenamiento "INSERCIÓN" - Lenguaje C

El método de "inserción" está basado en la técnica que utilizan los jugadores de cartas para odernar sus cartas. El jugador va insertando cada una de las cartas en la posición correspondiente.

Se considera una parte de la lista ya ordenada, ubicando cada elemento y colocándolo en el lugar que corresponde tomándo en cuenta su valor, como se muestra en la siguiente imágen:

Para implementar este método en el lenguaje de programación C, se debe emplear el siguiente procedimiento:

void ordenar(int vector[])

{
   int i, a, aux;

   for (i=1; i < 4; i++)
   {
      aux = vector[i];

      for (a=i-1; a >= 0 && vector[a] > aux; a--)
      {
         vector[a + 1] = vector[a];

      }

      vector[a+1] = aux;

   }
}

Para observar una corrida en frío de dicho procedimiento puede hacer click en el link para WINDOWS:  https://docs.google.com/leaf?id=0B_tJ5vXCSmOoMzJhMGIwZmQtYWRlYy00ZjczLTgwYzgtNjM3N2Q2MjFiMjhh&hl=en&authkey=CN2DjY8O

O click aquí para UBUNTU:  https://docs.google.com/leaf?id=0B_tJ5vXCSmOoOWY4Y2IxNDYtZGVlNi00NThhLTg2ZDktYWFjYTQ5NDE0M2Rh&hl=en&authkey=CLzA_HM