SOLUCIÓN DE COLISIONES.
Grupo 7
Cristhian Camilo Martinez Rey
Jhon Eddi Malagon Gonzalez
Juan David Rosero Torres
Julio Cesar Flórez Báez
Ingeniería de sistemas, Facultad de Ingeniería
Universidad Distrital Francisco José de Caldas
Bogotá
2020
Tabla de contenidos
Métodos de solución de colisiones para todo tipo de búsqueda interna: 3
Reasignación 4
Prueba lineal 4
Prueba cuadrática 5
Doble dirección hash 8
Arreglos anidados 10
Encadenamiento 12
Métodos de solución de colisiones para todo tipo de búsqueda externa: 13
Referencias 17
MÉTODOS DE SOLUCIÓN DE COLISIONES.
Métodos de solución de colisiones para todo tipo de búsqueda interna:
El ingeniero Bruno Lopez Takeyas nos habla de que la elección de un método
adecuado para resolver colisiones es tan importante como la elección de una
buena función hash.1
Cairo por otro lado afirma que se debe hacer un esfuerzo importante para
encontrar una función hash que ofrezca la mayor uniformidad en la distribución
de claves. Además, menciona que 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 2. Sin embargo,
esta solución demanda un alto costo en memoria; por lo que Cairo propone
otros métodos.
Algunos de los métodos para resolver las colisiones son:
-
Reasignación: Entre el principio de comparación y asignación de
elementos, Takeyas nos habla de que existen varios métodos que
trabajan con esto, los cuales son:
-
Prueba lineal: Takeyas dice que esta 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 último es el primero.
La principal desventaja del método es que puede haber un fuerte
agrupamiento alrededor de ciertas claves, mientras que otras
zonas del arreglo permanecen vacías. Si las concentraciones de
claves son muy frecuentes, la búsqueda será principalmente
secuencial, perdiendo así las ventajas del método hash. Takeyas
nos muestra el siguiente ejemplo:
1
(Ing. Bruno Lopez Takeyas) Métodos de tratamiento de colisiones, pag 1.
2
(Cairo, 1993) Estructuras de datos pág. num 407
Imagen No.1 tomada de Métodos de tratamiento de colisiones
Ing. Bruno Lopez Takeyas
Como se puede ver en la tabla, se presentan algunas colisiones,
por ejemplo la clave 25 presenta colisión con la clave 35,
gráficamente se soluciona así:
Imagen No.2 tomada de Métodos de tratamiento de colisiones
Ing. Bruno López Takeyas
Como se puede observar en la imagen, la clave 25, 43 y 56 se
insertan con normalidad, hasta que la clave 35 presenta una
colisiones, así que como vemos en la imagen No.2 la clave 35
mira si el siguiente espacio, que sería la posición número 7, esta
desocupado, y así sucesivamente hasta que encuentra uno vacío,
que sería el que se encuentra después del 56, es decir, el espacio
número 8 del arreglo.
Cairo menciona que 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. El proceso de búsqueda concluye cuando el elemento
es hallado o cuando se encuentra una posición vacía. Es
importante recalcar que para Cairo en este método el arreglo se
trata como una estructura circular donde: “El siguiente elemento
después del último es el primero” 3. Sin embargo, la principal
desventaja de este método es que puede haber una fuente de
agrupamiento alrededor de ciertas claves, mientras otras claves
del arreglo pueden 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.
Joyanes utiliza el método de exploración lineal el cual, es la forma
más primaria y simple de resolver una colisión entre claves al
aplicar una función de dispersión. Supóngase que se tiene un
elemento de clave x, la dirección que devuelve la función h(x) = p,
si esta posición ya está ocupada por otro elemento se ha
producido una colisión. La forma de resolver está colisión, con
3
(Cairo, 1993) Estructuras de datos pág. num 407
exploración lineal, consiste en buscar la primera posición
disponible que siga a p. La secuencia de exploración que se
genera es lineal: p, p+1, p+2, ... m-1, 0, 1, ... y así
consecutivamente hasta encontrar una posición vacía. La tabla se
ha de considerar circular, de tal forma que considerando m-1 la
última posición, la siguiente es la posición 0 4.
-
Prueba cuadrática: Takeyas nos dice que este método es similar
al de prueba lineal. La diferencia consiste en que en el cuadrático
las direcciones alternativas se generan como D+1, D+4, D+9, …,
D+ , que permite una mejor distribución de las claves
colisionadas.5
La principal desventaja de este método es que pueden quedar
casillas del arreglo sin visitar. 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. Se presenta el siguiente ejemplo :
Imagen No.3 tomada de Métodos de tratamiento de colisiones
Ing. Bruno Lopez Takeyas
En la tabla se puede ver que todo transcurre con normalidad
hasta que se llega a la clave 35, que es cuando se presenta una
colisión. Y se soluciona así:
4
(Joyanes, 2014) Estructura de datos en C pag. 414
5
(Ing. Bruno Lopez Takeyas) Métodos de tratamiento de colisiones pag 2.
Imagen No.4 tomada de Métodos de tratamiento de colisiones
Ing. Bruno Lopez Takeyas
Analizando el caso del clave número 4 (35), podemos ver que
presenta colisión con 25, lo que requiere ser solucionado,
utilizando este método cuadrático podemos ver que la clave 35 se
corrio un total de 4 espacios y quedó en la posición 10, así con
las demás colisiones que se presentaron.
Para Álvarez Giraldo y Soto Ocampo este método es una
alternativa a usar cuando se quiere evitar la agrupación de claves
que se presenta cuando se usa el método de prueba lineal. Para
el uso de este método, se supone que a un elemento con clave x
le corresponde la dirección p del arreglo, pero la posición p ya se
encuentra ocupada, entonces el método de prueba cuadrática
debe buscar las direcciones p, p+1, p+4, p+9,....p+ ,
considerando el arreglo como circulas. Además, menciona que
este método recibe su nombre debido al desplazamiento relativo
6
de . El ejemplo que proponen los autores es el siguiente:
25 43 56 35 54 13 80 104
6
(Álvarez Giraldo & Soto Ocampo, 2012) Métodos para la resolución de las colisiones
[6/11/2020]
Tabla No.1 tomada de Métodos para la resolución de colisiones
Alvarez Giraldo y Soto Ocampo
Usando los datos de la Tabla No.1 y haciendo uso de la función
modular con n=10 se obtienen los siguientes resultados.
X 1 2 3 4 5 6 7 8 9 10
h(x) 80 43 54 25 56
13 104 35
Tabla No.2 tomada de Métodos para la resolución de colisiones
Alvarez Giraldo y Soto Ocampo
Haciendo uso del método de prueba cuadrática los datos
quedarían de la siguiente manera.
X 1 2 3 4 5 6 7 8 9 10
h(x) 80 55 43 54 25 56 13 104 35
Tabla No.3 tomada de Métodos para la resolución de colisiones
Alvarez Giraldo y Soto Ocampo
Joyanes nos dice que la resolución de colisiones con la
exploración lineal provoca que se agrupen los elementos de la
tabla según se va acercando el factor de carga a 0.5 y una
alternativa para evitar la agrupación es la exploración cuadrática.
Suponiendo que un elemento con clave x le corresponde la
dirección p, y que la posición de la tabla indexada por p está
ocupada, el método de exploración o prueba cuadrática busca en
las direcciones p, p+1, p+4, p+9, ... p+i2, considerando a la tabla
como un array circular. El nombre de cuadrática, a esta forma de
explorar, se debe al desplazamiento relativo, i2 para valores de i=
1, 2, 3, …7
-
Doble dirección hash: Takeyas habla de que 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.8
La función Hash que se aplique a las direcciones puede o no ser
la misma que originalmente se aplicó a la clave. Según Takeyas
no existe una regla que permita decidir cuál será la mejor función
a emplear en el cálculo de las sucesivas direcciones.
Imagen No.5 tomada de Métodos de tratamiento de colisiones
Ing. Bruno Lopez Takeyas
Como podemos ver en la tabla, se presentan colisiones y se
aplica la función hash hasta que se encuentre una posición vacía,
como por ejemplo la clave 13, la cual fue necesario aplicar un
total de 4 veces la función hash. A continuación se presenta la
representación gráfica.
7
(Joyanes, 2014) Estructura de datos en C pag. 415
8
(Ing. Bruno López Takeyas) Métodos de tratamiento de colisiones pag 3
Imagen No.6 tomada de Métodos de tratamiento de colisiones
Ing. Bruno Lopez Takeyas
Álvarez Giraldo y Soto Ocampo mencionan que este método
utiliza una segunda función hash. Se tiene una función hash
principal , y otra función hash secundaria . El primer
intento de insertar o buscar, un nuevo elemento inspecciona la
posición , se hay una colisión, se obtiene un segundo
desplazamiento con otra función hash . Entonces, la
secuencia de búsqueda se
inspeccionan hasta encontrar una posición libre 9. El ejemplo que
proponen los autores es el siguiente:
Teniendo en cuenta los datos de la Tabla No.2 … y usando la
nueva función hash se obtienen los
siguientes datos
K 25 43 56 35 54 13 80 104
h(k) 6 4 7 6 5 4 1 5
9
(Álvarez Giraldo & Soto Ocampo, 2012) Métodos para la resolución de las colisiones
[6/11/2020]
h’(D)
8 6 7
h’(D’)
8 9
h’(D’’) 10
Tabla No.4 tomada de Métodos para la resolución de colisiones
Alvarez Giraldo y Soto Ocamp
Usando el método de doble dirección se obtiene lo siguiente:
X 1 2 3 4 5 6 7 8 9 10
h(x) 80 43 54 25 56 35 104 10
Tabla No.5 tomada de Métodos para la resolución de colisiones
Alvarez Giraldo y Soto Ocampo
Para Sánchez la doble dirección hash consiste en crear una
posición alternativa en la tabla al obtener una colisión aplicando una de
las funciones hash, ya sea al buscar una posición o al ingresar en una
posición vacía. Para detener este proceso es necesario encontrar una
posición vacía o el elemento que se estaba buscando. La función
aplicada a la nueva llave puede ser o no ser la misma que se le aplica a
la llave que produce una colisión10
10
(Sánchez et al, nd) Hashing: Técnicas y Hash para la Protección de Datos pag 5
-
Arreglos anidados: Takeyas dice que este método consiste en que
cada elemento del arreglo tenga otro arreglo en el cual se almacena los
elementos colisionados11. Si bien, la solución parece ser sencilla, es
claro que también resulta ineficiente. Al trabajar con arreglos se depende
del espacio que se haya asignado a este, lo cual induce a un nuevo
problema; elegir un tamaño adecuado del arreglo que permita el
equilibrio entre el coste de memoria y el número de valores colisionados.
Se presenta el siguiente ejemplo:
Imagen No.7 tomada de Métodos de tratamiento de colisiones
Ing. Bruno Lopez Takeyas
Con lo cual, se puede ver las diferentes colisiones que se presentan en
el problema, y por consiguiente, y según el método de Arreglos anidados
se hace lo siguiente:
Imagen No.8 tomada de Métodos de tratamiento de colisiones
Ing. Bruno Lopez Takeyas
Como se puede ver, al haber una colisión se creó otro arreglo anidado al
primero en donde se guarda la clave en la misma posición que debería ir
en el primer arreglo.
Para Álvarez Giraldo y Soto Ocampo este método consiste en que cada
elemento del arreglo tenga otro arreglo, en el cual se almacenen los
elementos que colisionan (una matriz) 12. Sin embargo, mencionan que
11
(Ing. Bruno López Takeyas) Métodos de tratamiento de colisiones pag 4
12
(Álvarez Giraldo & Soto Ocampo, 2012) Métodos para la resolución de las colisiones
[6/11/2020]
este método es muy ineficiente debido a que se necesita elegir un
tamaño adecuado del arreglo que permita el equilibrio entre el costo de
memoria y el número de valores que colisionan que pudiera almacenar.
El ejemplo que proponen los autores es el siguiente:
Teniendo en cuenta los datos de la Tabla No.1 y aplicando el método de
arreglos anidados, el resultado sería el siguiente.
X 1 2 3 4 5 6 7 8 9 10
h(x) 80 43 54 25 56
13 104 35
Tabla No.6 tomada de Métodos para la resolución de colisiones
Alvarez Giraldo y Soto Ocampo
Sanchez describe que este método consiste en que la posición que
produce colisión tenga otro vector para guardar esta posición, pero este
método parece fácil, sin embargo, es realmente inútil debido a la
cantidad de espacios que habría que crear cada vez que se produce una
colisión dentro de los arreglos creados sería imposible tener un cálculo
adecuado de cuanto espacio tener.13
-
Encadenamiento: Takeyas dice que este método consiste en que cada
elemento del arreglo tenga un apuntador a una lista ligada, la cual se
genera e irá almacenando los valores colisionados a medida que se
requiera14. Se muestra el siguiente ejemplo:
Imagen No.9 tomada de Métodos de tratamiento de colisiones
Ing. Bruno Lopez Takeyas
Se podría ver una relación con este método y el anterior es que, en este
caso, se liga con una lista dinámica, y en la anterior con arreglos, como
se puede ver a continuación:
13
(Sánchez et al, nd) Hashing: Técnicas y Hash para la Protección de Datos pag 5
14
(Ing. Bruno López Takeyas) Métodos de tratamiento de colisiones pag 4
Imagen No.10 tomada de Métodos de tratamiento de colisiones
Ing. Bruno Lopez Takeyas
Para Álvarez Giraldo y Soto Ocampo el método de encadenamiento o
direccionamiento enlazado se basa en utilizar listas enlazadas, de tal
forma que en cada lista se coloquen los elementos los elementos que
tienen la misma dirección hash. Todos los elementos que colisionan:
van a estar ubicados en la misma lista
enlazada15. El ejemplo que proponen los autores es el siguiente:
Teniendo en cuenta los datos de la Tabla No.1 y aplicando el método de
encadenamiento, el resultado sería el siguiente.
X 1 2 3 4 5 6 7 8 9 10
h(x) 80 43 54 25 56
13 104 35
Tabla No.7 tomada de Métodos para la resolución de colisiones
Alvarez Giraldo y Soto Ocampo
Sanchez menciona que este método consiste en que cada elemento
contenga un enlace a una lista para que de esta manera sea manera
sea más fácil almacenar los valores colisionados este método es muy
eficiente debido al dinamismo16
15
(Álvarez Giraldo & Soto Ocampo, 2012) Métodos para la resolución de las colisiones
[6/11/2020]
16
(Sánchez et al, nd) Hashing: Técnicas y Hash para la Protección de Datos pag 5
Métodos de solución de colisiones para todo tipo de búsqueda
externa:
Cormen usa el direccionamiento abierto para las soluciones de colisiones en
búsquedas externas donde todos los elementos se almacenan en la propia
tabla hash. Es decir, cada entrada de la tabla contiene un elemento del
conjunto dinámico o NIL. Al buscar un elemento, examinamos
sistemáticamente los espacios de la tabla hasta que se encuentra el elemento
deseado o hasta que queda claro que el elemento no está en la tabla. No hay
listas ni elementos almacenados fuera de la tabla, ya que los hay en el
encadenamiento. Por tanto, en el direccionamiento abierto, la tabla hash puede
"llenarse" para que no se puedan realizar más inserciones; el factor de carga
nunca puede exceder 1.17
Cairo nos habla de las búsquedas externas con colisiones, lo más importante
para poder evitarlas es elegir un tamaño adecuado de cubetas y de bloques.
Con respecto a las cubetas, si se definen muy pequeñas el número de
colisiones aumenta, mientras que si se definen muy grandes se pierde
eficiencia en cuanto a espacio de almacenamiento 18. Además, si se necesitará
copiar una cubeta en memoria principal y esta fuera muy grande, ocasiona
problemas por falta de espacio. Otro inconveniente que se presenta en el caso
de cubetas muy grandes es que se requiere mucho tiempo para recorrerlas.
Con el tamaño de los bloques es importante considerar la capacidad de estos
para almacenar registros. Un bloque puede almacenar uno, dos o más
registros. Normalmente los tamaños de las cubetas y los bloques dependen de
las capacidades del equipo con el que se está trabajando .
Imagen No.11 tomada de Estructuras de datos de [Link]
Cairo nos presenta el anterior ejemplo, en el que cada cubeta tiene un bloque,
y por lo tanto, una capacidad máxima y determinada por el tamaño del bloque
asociado con ella. Una vez que se satura la capacidad de la cubeta, cualquier
registro asignado a ella producirá una colisión. Además, nos habla de las
siguientes formas para tratar estos casos:
17
(Cormen, 2009) Introduction to Algorithms pag. 269
18
(Cairo, 1993) Estructura de datos pag. 429
- Uso de áreas independientes para colisiones: Cairo dice que consiste
en definir áreas separadas (secundarias) de las áreas primarias de
almacenamiento, en las que se almacenarán todos los registros que se
hayan colisionado19. 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ía
que buscar a lo largo del área secundaria hasta encontrar el elemento
deseado.
Imagen No.12 tomada de Estructuras de datos de [Link]
Otra forma consiste en dividirla en bloques, asociando cada uno de ellos
a uno del área primaria. Esta alternativa optimiza el tiempo de búsqueda
en el área de colisiones, pero tiene el inconveniente de que estos
bloques podrían, a su vez, saturarse, ocasionando nuevamente
colisiones.
19
(Cairo, 1993) Estructura de datos pag. 431
Imagen No.13 tomada de Estructuras de datos de [Link]
- Uso de áreas de colisiones entre los bloques de almacenamiento
primario: Cairo afirma que este método consiste en definir áreas de
colisiones entre los bloques de almacenamiento primario. Una vez
detectada una colisión en un bloque se debe buscar en el área de
colisiones inmediata a dicho bloque 20. Si el elemento no se encuentra y
el área de colisiones está llena se continuará la búsqueda a través de
otras áreas de colisiones. El proceso termina cuando el elemento se
encuentra o bien cuando existen espacios vacíos en un bloque. El
esquema sería el siguiente:
Imagen No.14 tomada de Estructuras de datos de [Link]
Para Jonghun Park el problema de las colisiones en la búsqueda externa es
menos severo con los bloques, porque se puede hacer un hash en mismo
bloque tantas veces como la cantidad de registros que puede haber en un
bloque sin causar problemas 21. Sin embargo, se pueden evitar estas colisiones
utilizando una variación de encadenamiento en la que se mantiene un puntero
en cada bloque a una lista enlazada de registros de desbordamiento para el
bloque. puntero de registro: incluye tanto una dirección de bloque como una
posición de registro relativa dentro del bloque tal como se observa en la imagen
No. 15.
20
(Cairo, 1993) Estructura de datos pag. 432
21
(Jonghun Park, Sin fecha),Disk Storage, Basic FileStructures, and HashingStructures, and
Hashing [6/11/2020]
Imagen No.15 tomada de Disk Storage, Basic FileStructures, and HashingStructures, and Hashi
de Jonghun Park
Referencias
1) Takeyas, B. L. (s. f.). MÉTODOS DE TRATAMIENTO DE COLISIONES.
Colisiones. Recuperado 6 de noviembre de 2020, de
[Link]
os/Apuntes/[Link]
2) Cairo Battistutti. (1993). Estructuras de datos. (pp. 420-445).
[Link]
ardati_tercera_edicion_
3) Alvarez Giraldo, L., & Soto Ocampo, D. (2012). Métodos para la
resolución de las colisiones [PDF] (1st ed., pp. 4-12). Visitado 5
Noviembre 2020, desde:
[Link]
colisiones
4) .Park, Jonghun. (Sin fecha). Disk Storage, Basic File Structures, and
Hashing [Ebook] (1st ed., p. 23). Departamento de Ingeniería industrial.
Visitado 6 Noviembre 2020, desde:
[Link]
5) Joyanes, L., & Zahonero, I. (2014). Estructura de datos C++.
6) Sánchez, S., Domínguez, P., Velásquez, L., Asesor, P., Tejedor
-Morales, I., & Yahaira, M. (n.d.). Hashing: Técnicas y Hash para la
Protección de Datos. 1–7. [Link]
Lima/student_Papers/[Link]
7) Cormen, H. (2009). Introduction to Algorithms (Third Edit).
[Link]
[Link]
