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 que ver con crear un arreglo de número, crear un arreglo de punteros, donde cada puntero señala el principio de una lista enlazada. De esa forma se busca que cada elemento que llega a un determinado índice se pone en el último lugar de la lista de ese índice. Ese tiempo de búsqueda se reduce considerablemente, y no hace falta poner restricciones en su tamaño de arreglo, esto ya que se pueden añadir nodos dinámicos a la lista.

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:

Con aquello se busca el poder tener una recuperación de información, siendo entonces uno de los métodos y aplicaciones más importantes para poder buscar y encontrar la información, siendo también que está netamente relacionada con las tablas para consultas. Aquellas tablas que contienen una cantidad de información

...