Consulta colisiones

CONTENIDO

1  Colisiones en búsquedas internas        3

1.1 Definición        3

1.1.1 Según Luis Joyanes, Lucas Sánchez y Ignacio Zahonero        3

1.1.2 Según Cairo y Guardati        3

1.2 Reasignación        3

1.2.1 Según Cario y Guardati        3

1.2.2 Según Luis Joyanes, Lucas Sánchez y Ignacio Zahonero        6

2  Colisiones en búsquedas externas        14

     2.1 Definición        14

            2.1.1. Según Jorge Villalobos        14

            2.1.2. Según Robert Sedgewick        14

            2.1.3. Según Cairo y Guardati        14

     2.2 Uso de áreas independientes para colisiones.        14

     2.3 Uso de áreas de colisiones entre los bloques de almacenamiento                                                                                            

           primario.        15

     2.4 Open hashing                                                                         15

     2.5 Closed Hashing                                                                         16

1  Colisiones en búsquedas internas

1.1 Definición

1.1.1 Según Luis Joyanes, Lucas Sánchez y Ignacio Zahonero

En una función de dispersión se puede generar la misma posición al ser aplicada a las claves de dos o más registros diferentes, por lo que se obtiene una misma posición para ubicar dos registros diferentes. ^[1] A esto se le conoce como una colisión, la cual es necesaria resolver porque es imposible que dos registros ocupen la misma posición.  Una función ideal debería generar direcciones distintas para dos claves distintas pero no siempre es así y para esto debemos recurrir a diferentes métodos de solución de colisiones.

1.1.2 Según Cairo y Guardati

Es cuando una función hash obtiene una misma dirección para dos claves diferentes, se encuentra ante una colisión. La elección de un método adecuado para resolver las colisiones es tan importante como una elección de una buena función hash ^[2] ya que la elección de esta puede significar un gran costo para tratar la colisión y se necesita encontrar una función que ofrezca la mayor uniformidad en la distribución de las claves.

1.1.3 Según Robert Sedwick  

Las colisiones son el encuentro de una o más claves en una misma dirección, esta dirección es dada por una función de dispersión que transforma una clave de búsqueda en direcciones, que idealmente, deberían dar direcciones diferentes a cada una de las claves que se ingresen^[3], pero no es así y ahí es donde se necesitaran los métodos de resolución de colisiones.

1.2 Reasignación

1.2.1 Según Cario y Guardati

Para el método de reasignación existen varios métodos propios como la prueba lineal, la prueba cuadrática y el Doble de dirección hash.

• El método de prueba lineal consiste en que una vez se detecta la colisión, se recorre el arreglo secuencialmente a partir del punto de colisión buscando al elemento. Este proceso, al hallar el elemento, concluye en otro caso, al encontrar una posición vacía. Este arreglo es tomado como una estructura circular tomando el primer elemento como el siguiente al último. ^[4]

Ejemplo: sea V un arreglo unidimensional de 10 elementos. Las claves 25,43,56,35,54,13,80 y 104 de una función hash:

[pic 1]

        Se necesita solucionar la colisión en K=35

        [pic 2]                [pic 3]

Figura nº1 Arreglo ejemplo prueba lineal   Figura nº2 tabla con H(k) ejemplo

• El método de la prueba cuadrática tiene ciertas semejanzas con la lineal, con la diferencia que en la cuadrática las direcciones se generan como  lo cual permite que se distribuyen las claves en colisión mejor. [pic 4]

Ejemplo: sea V un arreglo unidimensional de diez elementos. Las claves 25,43,56,35,54,13,80,104 y 55.

[pic 5]

        solución de colisiones por prueba cuadrática K=35

                 [pic 6]          [pic 7]

                Figura nº3 arreglo ejemplo nº2        Figura nº4 tabla H(K) ejemplo nº2

• Doble dirección hash, al detectar la colisión, inmediatamente genera otra dirección aplicando la misma función a la dirección previamente obtenida. Este proceso se detiene cuando el elemento es hallado o se encuentra en una posición vacía. La función hash aplicada no necesariamente debe ser la misma que se aplicó por primera vez, puede ser cualquier otra. No se dice cual es la mejor opción. Generalmente se usan derivadas de la función.

        Ejemplo:

                        [pic 8]

Figura nº 5 tabla doble dirección hash

1.2.2 Según Luis Joyanes, Lucas Sánchez y Ignacio Zahonero

Para la resolución de una colisión existe la posibilidad de usar el método de exploración de direcciones. Para este método existen diversos métodos, los cuales, se utilizan al encontrarse todos los elementos colisionados almacenados en una misma tabla.

...