Laboratorio
Enviado por yescor20 • 2 de Abril de 2014 • 2.901 Palabras (12 Páginas) • 279 Visitas
TRABAJO ESCRITO SOBRE SOLUCION DE COLISIONES
EDGAR YESID CORTES INSUASTY
DAVID ENRIQUE MAECHA
UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS
FACULTAD INGENIERIA
SISTEMAS
VI SEMESTRE
CONSULTA
BOGOTA
2014
TRABAJO ESCRITO SOBRE SOLUCION DE COLISIONES
EDGAR YESID CORTES INSUASTY
DAVID ENRIQUE MAECHA
DOCENTE
JULIO FLOREZ SANCHEZ
UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS
FACULTAD INGENIERIA
SISTEMAS
VI SEMESTRE
CONSULTA
BOGOTA
2014
CONTENIDO
INTRODUCCION
DEFINICION
REASIGNACION
PRUEBA LINEAL
PRUEBA CUADRATICA
DOBLE DIRECCION HASH
ARREGLOS ANIDADOS
ENCADENAMIENTO
USO DE AREAS INDEPENDIENTES DE LAS COLISIONES
USO DE AREAS DE COLISIONES ENTRE LOS BLOQUES DE ALMACENAMIENTO PRIMARIO
BIBLIOGRAFIA
INTRODUCCION
El presente trabajo pretende dar a conocer todo lo referente a solución de colisiones explicando de forma clara y fácil de entender el tema, se mostraran ejemplos para fácil comprensión del lector, se muestra la estructura de la consulta, como funciona y ejemplos de forma grafica.
2. DEFINICION
SOLUCION DE COLISIONES
La elección de un método adecuado para resolver colisiones es tan importante como la elección de una buena función hash. Cuando esta obtiene una misma dirección para dos claves diferentes se está ante una colisión. Normalmente cualquiera que sea el método elegido resulta costoso tratar las colisiones. Es por ello que se debe hacer un esfuerzo importante para encontrar la función que ofrezca la mayor uniformidad en la distribución de las claves.
La manera más natural de resolver el problema de las colisiones es reservar una casilla por clave; es decir, aquellas que se corresponden una a una con las posiciones del arreglo. Pero como ya se menciono esta solución puede tener un alto costo en memoria; por lo tanto, se deben analizar otras alternativas que permitan equilibrar el uso de memoria con el tiempo de búsqueda.
Algunos de los métodos más utilizados para resolver colisiones, se pueden clasificar en:
Reasignación
Arreglos anidados
Encadenamiento
3. REASIGNACION
Existen varios principios de reasignación, a continuación se analizaran tres:
Prueba lineal
Prueba cuadrática
Doble dirección hash
3.1 PRUEBA LINEAL
Este método consiste en que una vez que se detecta la colisión se recorre el arreglo secuencialmente a partir del punto de colisión, buscando al elemento. El proceso de búsqueda concluye cuando el elemento es hallado, o cuando se encuentra una posición vacía. El arreglo se trata como una estructura circular: el siguiente elemento después del último es el primero.
La principal desventaja es que puede haber un fuerte agrupamiento alrededor de ciertas claves, mientras que otras zonas del arreglo podrían permanecer vacías. Si las concentraciones de claves son muy frecuentes, la búsqueda será principalmente secuencial, perdiendo así las ventajas del método hash.
EJEMPLO
Sea V un arreglo unidimensional de 10 elementos. Las claves son: 25, 43, 56, 35, 54, 13, 80 y 104 fueron asignadas según la función hash: H(K) = (Kmod10) + 1
El dato a buscar es 35, al aplicar la clave hash a 35 se obtiene la dirección 6, como el elemento buscado no se encuentra avanza hasta la siguiente posición, hasta llegar a la posición 8 donde lo encuentra.
Estructuras de datos-cairo3ed
3.2 PRUEBA CUADRATICA
Este método es similar al anterior. La diferencia consiste en el que de prueba cuadrática las direcciones alternativas se generaran como D + 1, D + 4, D + 9,…D + i^2, en vez de D + 1, D + 2,… D + i. Esta variación permite una mejor distribución de
...