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

...