By Tabla Hash gy MonicaEscobar15 cbenpanR 14, 2016 pagos UNIVERSIDAD TECNICA DEL NORTE FACULTAD DE INGENIERA EN CIENCIAS APLICADAS CARRERA DE INGENIERIA EN SISTEMAS COMPUTACIONALES ESTRUCTURA DE DATOS Nombre: Jonathan Fredd Gracia Churta Fecha: 01 de Febrero ors to View nut*ge Definición: Colisiones: Exploración Lineal: Exploración Cuadrática: Hashing Enlazado.
TABLAS DE DISPERSIÓN Definición: Las tablas de dispersión son estructuras de datos que tienen como finalidad realizar las operaciones fundamentales de búsqueda y eliminación de un registro en un tiempo de ejecución onstante (complejidad constante O (1) La organización ideal de una tabla es de tal forma que el campo clave de los elementos se tabla dispersa debe proporcionar métodos de resolución de colisiones.
Exploración Lineal: Es la forma más primaria y simple de resolver una colisión entre claves, al aplicar una función de dispersión. Supóngase que se tiene un elemento de clave x , la dirección que devuelve la función h(x) = p , si esta posición ya está ocupada por otro elemento se ha producido una colisión. La forma de resolver está colisión con exploración lineal consiste en buscar a primera posición disponible que siga a p .
La secuencia de exploración que se genera es lineal: p, p+l, p+2, m-l, 0, 1, y así consecutivamente hasta encontrar una posición vacía. La tabla se ha de considerar circular, de tal forma que siendo m-l la última posición, la siguiente es la posición O Exploración Cuadrática: La resolución de colisiones con la exploración lineal provoca que se agrupen los elementos de la tabla según se va acercando el factor de carga a 0. . Una alternativa para evitar la agrupación es la exploración cuadrática. Suponiendo que a un elemento con clave x le corresponde la irección py que la posición de la tabla indexada por p está ocupada, el método de exploración o prueba cuadrática busca en las direcciones p, p+l, p+4, p+9 , p+i 2 , considerando la tabla como un array circular.
El nombre de cuadrática para esta forma de explorar se debe al desplazamiento relativo, i 2 para valores de Hashing Enlazado: Una alternativa a la secuencia de explor relativo, i 2 para valores de i— 1, 2, 3.. Hashing Enlazado: Una alternativa a la secuencia de exploración es el direccionamiento (hashing) enlazado. Se basa en utilizar listas enlazadas (cadenas de elementos), de tal forma que en ada lista se colocan los elementos que tienen la La Figura 12. muestra la estructura de datos básica para este método de dispersión. La idea fundamental es la siguiente: si se ha elegido una función hash que genera direcciones en el rango 0 a m-l , se debe crear una tabla de m posiciones, indexada de O a m-l ; cada posición de la tabla contendrá la dirección (referencia) de acceso a su correspondiente lista enlazada. La estructura de datos empleada para la implementación de una tabla dispersa con direccionamiento enlazado es un array de listas enlazadas.
Cada posición i es una referencia a la lista enlazada, sus nodos son elementos de la tabla dispersa cuyo direccionamiento hash, obtenido con la función hash elegida, es i . Ahora, los elementos de la tabla dispersa se agrupan en listas enlazadas, por consiguiente es necesario que dispongan de un campo adicional para poder enlazar con el siguiente elemento. Yojanes Agu lar , Luis, and zohonero Martínez, Ignacio. Estructuras de datos en Java. España: McGraw-Hill España, 2008. ProQuest ebrary_ Web. 1 February 2016. Copyright C 2008. McGraw-Hill España. All rights reserved. 31_1f3
