PDF de programación - Métodos de tratamiento de Colisiones

Administración de Archivos Ing. Bruno López Takeyas


MÉTODOS DE TRATAMIENTO 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 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
reasignación de elementos. Se analizaran tres de ellos:


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

trabajan bajo el principio de comparación y



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 una posició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 perdiendo así las ventajas del
método hash. Con el ejemplo se ilustra el funcionamiento del algoritmo:



Administración de Archivos Ing. Bruno López Takeyas


1

2

3

4

5

6

7

8

9


10



V

80



43

54

25

56

35

13


104



K H(K)


25
43
56
35
54
13
80
104


6
4
7
6
5
4
1
5


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 + i² en vez de
D + 1, D + 2,...,D + i. Esta variación permite una mejor distribución de las
claves colisionadas.
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 1²
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án
visitadas todas las casillas.
A continuación se presenta un ejemplo que ilustra el funcionamiento:

V

80

55



43

54

25

56

13


25
43
56
35
54
13
80
104
55



K H(K)


6
4
7
6
5
4
1
5
6



1

2

3

4

5

6

7

8

9

10

104


35


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.



1 80

2
3

4 43
5 54
6 25
7 56
8 35
9 13
10 104

H'(D) H'(D') H'(D'')

K H(K)

25
6 ---- ----- ------
43 4 ----- ------ ------
56 7 ----- ------ ------
35 6 8 ------ ------
54 5 ----- ------ ------
13 4 6 8 10
80 1 ------ ------ --------
104 5 7 9 -------


Administración de Archivos Ing. Bruno López Takeyas


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')



Administración de Archivos Ing. Bruno López Takeyas



v


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 la solucion parece ser
sensilla, es claro también que resulta ineficiente. Al trabajar con arreglos se
depende del espacio que se alla asignado a este lo cual onduce 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


1
2
3
4
5
6
7
8
9
10



Encadenamiento
Consiste en que cada elemento 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.



k
25
43
46
35
54
13
80
104



13
104
35



. . .



80


43
54
25
56



H(k)

6
4
7
6
5
4
1
5



K
25
43
56
35
54
13
80
104



H(K)

6
4
7
6
5
4
1
5

Administración de Archivos Ing. Bruno López Takeyas



1

2

3

4

5

6

7

8

9

10

80



43

54

25

56



13

104

35