Laboratorio

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 las claves que colisionan.

EJEMPLO

Sea V un arreglo de 10 elementos, las claves son: 25, 43, 56, 35, 54, 13, 104 y 55. El dato a buscar es 35. La función hash asignada es: H (K) = (Kmod10) + 1

Estructuras de datos-cairo3ed

Cuando se le aplica hash a 35 la dirección dada es 6, se calcula luego la suma D + (I*I), el algoritmo concluye cuando encuentra la clave en la posición 10.

3.3 DOBLE DIRECCION HASH

Este método consiste en que una vez hallada la colisión, se genera otra dirección aplicando la misma dirección hash a la dirección previamente obtenida. El proceso se detiene cuando el elemento es hallado o cuando se encuentra una posición vacía.

DH (K)

D’ (H (D))

D’’ (H (D’))…

La función hash que se aplica no necesariamente tiene que ser la misma que originalmente se aplico a la clave; podría ser cualquier otra, sin embargo, no existe ningún estudio que precise cual es la mejor función que se debe utilizar en el cálculo de las direcciones sucesivas.

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

Además se definió

...