Estructura

INSTRUCCIONES

1. Defina con sus propias palabras, qué se entiende por “colisiones” en el tratamiento de los datos mediante Tablas Hash y explique cuáles son las medidas que podemos utilizar para tratarlas.

2. Defina con sus propias palabras los siguientes términos e indique brevemente cómo trabajan sus algoritmos básicos. Indique para cada uno de ellos de qué orden es el tiempo de ejecución esperado de dichos algoritmos:

a. Búsqueda Secuencial.

b. Búsqueda Binaria.

DESARROLLO

1. Defina con sus propias palabras, qué se entiende por “colisiones” en el tratamiento de los datos mediante Tablas Hash y explique cuáles son las medidas que podemos utilizar para tratarlas.

Con respecto a las colisiones en el tratamiento de los datos mediante tabla de Hash, es referente a situaciones que se producen cuando dos entradas son distintas a una función de hash, estas hacen que sea una misma salida.

Las funciones principales tienen que tener un claro ordenamiento, esto con el objetivo de que todo lo que tenga que ver con arreglos y que en determinados casos, este tiene que tener al menos un proceso de orden previo, con ello se quiere explicar que los datos que se reciben, deben ser ordenados, como por ejemplo 53 – 55 – 50 – 54 – 51 - 52, los algoritmos los ordenan primero quedando de la siguiente manera, 50 – 51 – 52 – 53 – 54 – 55, pero en una tabla hash no tiene que ser necesario puesto que el método hace designarle un índice a cada dato que recibe la entrega un numero por orden de llegada.

Como ejemplo anterior si se recibe 33 – 35 – 30 – 31 - 32, tomara los siguientes índices respectivamente (30) - (31) - (32) - (33) - (35) , tomando en cuenta que este sistema también tiene problemas y es lo que nos aboca en esta pregunta y es que en muchas ocasiones al entregar los índices puede existir efectos de redundancia, a los que nos referimos “colisión”.

Con respecto a las colisiones, estas son de manera frecuente cuando ciertos algoritmos que están malos en ciertas aplicaciones especializadas con un relativo número pequeño de entradas. Esto de cierta forma tiene un muy alto porcentaje de que no ocurra y deben carecer de colisiones, ya que los números potenciales de posibles entradas son mayor que el número de salidas que puede producir un hash. Sin embargo en una función donde se pueden introducir datos de longitud arbitraria y de la cual devuelve un hash de tamaño fijo, siempre habrá colisiones, esto ya que un hash dado puede pertenecer a un infinito número de entradas.

Para poder tener una solución en las colisiones, el tratamiento de colisiones es la solución para aquello, estando disponible diferentes maneras de solucionarlas, claro está que su eso es con las más efectivas, esta tiene

...