Estructura De Datos: Colisiones Y Tablas Hash

Introducción

Cuando utilizamos estructuras de almacenamiento como los arreglos podemos realizar diferentes funciones como, ingresar, eliminar y búsqueda, este último concepto es el que estudiaremos esta semana.

Veremos formas de ordenamiento tales como secuencial, binaria tablas hash, que iremos desglosando a medida que vamos avanzando en este control.

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.

R.- la función principal en el ordenamiento de un arreglo en ciertos casos deben tener al menos un proceso de orden previo, es decir que los datos recibidos son ordenados por ejemplo si recibimos 5 – 4 – 2 – 3 – 1, los algoritmos los ordenan primero quedando de la siguiente forma: 1 – 2 - 3 – 4 – 5, ahora bien en la tablas hash esto no es necesario ya que lo que este método hace es designarle un índice a cada dato que recibe le entrega un número por orden de llegada, ósea tomando el ejemplo anterior si recibimos 5 – 4 – 2 – 3 – 1, tomara los siguientes índices respectivamente (1) - (2) - (3) - (4) - (5), ahora bien 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”, para poder tratar con este problema que es inevitable en algunos algoritmos existen tres posibles soluciones:

Opción 1: cuando un índice ya está utilizado por otro elemento en el arreglo al dato se le aplicará el siguiente índice sin utilización que se encuentre, sin embargo un nuevo dato que ingrese puede volver a tener el mismo problema y que se le asigne un índice ya utilizado.

Opción 2: se reservan posiciones al final del arreglo ante posibles colisiones, sin embargo esto genera otra interrogante, pues no sabemos cuántas colisiones tendremos, obviamente si no conocemos la cantidad de datos que en el arreglo ingresaran.

Opción 3: por último tenemos este método que es vez de utilizar arreglos de números, utiliza punteros es uno de los más recomendados por el poco tiempo de búsqueda que demora, lo que realiza son listas en los índices enlazadas una vez que los datos entran son ingresados al final de los mismos índices para irlos ordenando y los punteros los entregan en el arreglo.

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: es tipo de búsqueda la realiza como su nombre lo indica en forma ordenada desde el primer dato hasta el último, esto solo si es que no encuentra el dato que busca, sino solo realizará este procedimiento hasta que encuentre el dato buscado, el tiempo de ejecución puede ser O(n2) y O(n).

B.- Búsqueda Binaria: en esta búsqueda el arreglo se divide en dos partes para encontrar el número deseado, ahora bien si el número se encuentra en la posición media el proceso de búsqueda se termina, si el número es menor al número del centro está en el primer arreglo que se separóy nuevamente se vuelve a dividir, esto se repetirá hasta que el número buscado quede en el centro, por otro lado si al realizar la separación el número es mayor al central entonces este está en el segundo arreglo separado y se repite el procedimiento al igual que antes, el tiempo de ejecución es de log(2, N+1).

...