Laboratorio 8: Tablas de dispersión

publicado a la‎(s)‎ 29 jun 2012, 10:23 por Hernan Nina Hanco   [ actualizado el 1 ago 2013, 7:13 ]
I) OBJETIVOS
  • Implementar modelos de tablas de dispersión y sus respectivas aplicaciones.
II) MARCO CONCEPTUAL

Hashing o localización
Es una forma de Implementación de tablas hash que dispone de técnicas para realizar inserciones, eliminaciones y búsquedas con coste medio constante.

Funcion hash o de localización
Función que asocia a un elemento y un índice.

Colisión
El empleo de la función de localización introduce una complicación, es posible que a dos elementos distintos les corresponda la misma posición.

Métodos para resolver la colisión
  • Exploración Lineal.- Consiste en buscar secuencialmente en el vector o arreglo hasta que encontremos una posición vacía y pueda agregar el elemento. Sin embargo, cuando el vector o arreglo esta con mas del 70% de su espacio ocupado, las búsquedas se hacen complicadas.
  • Exploración Cuadrática.- Es un método que mejora las deficiencias de la exploración lineal. utiliza la formula F(i)=i*i. Adiciona al valor de hash las funcion F(i).
  • Encadenamiento separado.- Una alternativa a la exploración cuadrática, maneja un arreglo o vector de listas enlazadas. La función Hash indica en que lista se debe almacenar un elemento.
III) PRACTICAS
1) Implementación básica de una tabla hash, con un función hash para números enteros de 16 bits.

namespace AppDispersion { public class TablaHash {
        // Arreglo o vector de elementos enteros private int[] tabla; public TablaHash(int n) { tabla = new int[n];
            // inicializar la tabla
            for (int i=0;i<tabla.Length;i++)
            {
                tabla[i]=0;
            } }
        /* Insertar un elemento al arreglo*/ public void insertar(int elemento) {
            // Determinar el indice del elemento utilizando la función hash int indice = hash(elemento);
            // Asignar elemento a la posición del indice
            // no se controla colisiones - se sobre escriben los elementos.
            tabla[indice] = elemento }
                 /* Implementación de una función hash para enteros de 16 bits */ private int hash(int clave) { return clave % tabla.Length; }
        /* Implementación de una función hash para enteros de 16 bits */ public void MostrarTabla() { for (int i = 0; i < tabla.Length; i++) { Console.Write("Indice: {0} ",i); Console.Write("\t"); Console.Write("Elemento: {0} ", tabla[i]); Console.Write("\n"); } } public bool busqueda(int clave) { return tabla[hash(clave)]!=0; } } }

Programa principal:

namespace AppDispersion
{
    class Program
    {
        static void Main(string[] args)
        {
           
            TablaHash tablaHash = new TablaHash(11);
            tablaHash.insertar(8);
            tablaHash.insertar(7);
            tablaHash.insertar(27);
            tablaHash.insertar(16);
            tablaHash.insertar(17);
            // mostrar la tabla Hash
            tablaHash.MostrarTabla();
            Console.ReadKey();
        }
    }
}

IV) TAREAS
  • Implementar una aplicación donde permita crear una tabla hash de tamaño "n" y poder almacenar, buscar y mostrar los elementos en la tabla.
  • Implementar los métodos de resolución de colisiones lineal, cuadrática y hashing enlazado.
V) Proyecto
  • Descripción: Implementar un Diccionario donde se registre la palabra y su significado. Se debe implementar una función hash para determinar los indices de una Palabra o cadena de caracteres.
  • Fecha de entrega: Martes 06 de Agosto del 2013
  • Numero de personas para el proyecto: 2
  • Recomendación: Evitar la copia de proyectos anteriores o de compañeros.
VI) REFERENCIAS
  • Estructura de datos en Java, Mark Allen Weiss, Addision Wesley - Pearson Educación. Capitulo 19 Tablas de Dispersión.
Comments