Solucion De Colisiones

INTRODUCCIÓN

El presente trabajo invita al lector a descubrir los diferentes métodos para tratar las colisiones, las cuales se presentan cuando en la misma dirección de memoria se tratan de ubicar varios datos, seguidamente se tratara en general los conceptos y tipos de índices en las estructuras de datos.

SOLUCIÓN DE COLISIONES

La elección de un método adecuado para resolvercolisiones es tan importante como la elección de una buena función hash. Cuando la función hash obtiene una misma dirección para dos claves diferentes, se esta ante una colisión.
Algunos métodos mas utilizados para resolver colisiones son los sig.:

* Reasignación
* Arreglos anidados
* Áreas de desborde

Reasignación

Existen varios métodos que trabajan bajo el principio de comparación yreasignación de elementos. Se analizaran tres de ellos:

* Prueba lineal
* Prueba cuadrática
* Doble dirección hash

a) Prueba lineal

Consiste en que una vez detectada la colisión se debe de recorrer 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 bien cuando se encuentra unaposición vacía. Se trata al arreglo como a una estructura circular: el siguiente elemento después del ultimo es el primero.
La principal desventaja de este método es que puede haber un fuerte agrupamiento alrededor de ciertas claves, mientras que otras zonas del arreglo permanecerían vacías. Si las concentraciones de claves son muy frecuentes, la búsqueda será́ principalmente secuencial perdiendoasí́ las ventajas del método hash. Con el ejemplo se ilustra el funcionamiento del algoritmo:

b) Prueba Cuadrática

Este método es similar al de la prueba lineal. La diferencia consiste en que en el cuadrático las direcciones alternativas se generan como D + 1, D + 4, D + 9, . . ., D + i2 en vez de
D + 1, D + 2,...,D + i. Esta variación permite una mejor distribución de las clavescolisionadas.
La principal desventaja de este método es que pueden quedar casillas del arreglo sin visitar. Además, como los valores de las direcciones varían en 12 unidades, resulta difícil determinar una condición general para detener el ciclo. Este problema podría solucionarse empleando una variable auxiliar, cuyos valores dirijan el recorrido del arreglo de tal manera que garantice que seránvisitadas todas las casillas.
A continuación se presenta un ejemplo que ilustra el funcionamiento:

c) Doble dirección hash

Consiste en que una vez detectada la colisión se debe generar otra dirección aplicando la función hash a la dirección previamente obtenida. El proceso se detiene cuando el elemento es hallado, o bien cuando se encuentra una posición vacía.
D =H(K)
D' = H(D) D'' =H(D')
La función hash que se aplique a las direcciones puede o no ser la misma que originalmente se aplico a la clave. No existe una regla que permita decidir cual será́ la mejor función a emplear en el calculo de las sucesivas direcciones.

Arreglos anidados

Este método consiste en que cada elemento del arreglo tenga otro arreglo en el cual se almacena los elementos colisionados. Si bien lasolución parece ser sencilla, es claro también que resulta ineficiente. Al trabajar con arreglos se depende del espacio que se halla asignado a este lo cual conduce a un nuevo problema difícil de solucionar: elegir un tamaño adecuado de arreglo que permita el equilibrio entre el coste de memoria y el numero de valores colisionados que pudiera almacenar.

Encadenamiento

Consiste en que cadaelemento del arreglo tenga un apuntador a una lista
ligada, la cual se ira generando e ira almacenando los valores colisionados a medida que se requiera.

INDICES PARA ARCHIVOS

CONCEPTO GENERAL:

Son estructuras de acceso auxiliares, utilizadas para aumentar la velocidad de recuperación de los registros en respuesta a ciertas condiciones de búsqueda.

* Proporcionan caminos de acceso...