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ó una función H’ en caso de colisión: H’ (D) = (K mod10) + 1

El elemento a buscar es 13, al aplicarle la función hash se obtuvo una dirección D = 4, como en esa posición no se encuentra el elemento buscado se aplica reiteradamente H’, generando direcciones hasta localizar el valor deseado. En este ejemplo fue preciso aplicar H’ tres veces obteniéndose las dirección 6, 8 y 10 en la cual finalmente se encontró el dato buscado.

4. ARREGLOS ANIDADOS

Este método consiste en que cada elemento del arreglo tenga otro arreglo, en el cual se almacenen los elementos que colisionan, si bien la solución es sencilla, es claro que resulta ineficiente. Al trabajar con arreglos se depende del espacio que se haya asignado a estos, lo cual conduce a un nuevo problema difícil de solucionar: elegir un tamaño adecuado de arreglo que permita un equilibrio entre el costo de memoria y el número de valores que pudieran analizar.

EJEMPLO

Sea V un arreglo unidimensional de 10 elementos. Las claves son: 25, 43, 56, 35, 54, 13, 80 y 104 se almacenaron en un arreglo utilizando la función hash: H (K) = (Kmod10) + 1

5. ENCADENAMIENTO

Este método consiste en que cada elemento del arreglo tenga un apuntador a una lista ligada, la cual se irá generando y almacenaran los valores que colisionan. Es el método más eficiente debido al dinamismo propio de las listas, cualquiera que sea el número de colisiones que se presenten, se podrán resolver sin inconvenientes.

Como desventajas se menciona el hecho de que ocupa espacio adicional al de la tabla y que exige el manejo de listas ligadas. Además si las listas crecen demasiado se perderá la facilidad de acceso directo 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, la función hash utilizada para almacenar los datos es: H (K) = (Kmod10) + 1

Una vez detectada la colisión en una cierta posición del arreglo, se debe recorrer la lista asociada a ella hasta encontrar el elemento buscado o llegar a su final.

USO DE AREAS INDEPENDIENTES PARA COLISIONES

Consiste en definir áreas separadas de las primarias de almacenamiento, en las que se almacenaran todos los registros que hayan colisionado. El área de colisiones puede estar organizada de diferentes maneras. Una alternativa consiste en tener el área común a todas las cubetas. En consecuencia si se produce una colisión habrá que buscar a lo largo del área secundaria hasta encontrar el elemento deseado.

Otra forma de organizar el área de

...