[SER222] M03_04 Linear Probing (1/5): The Concept

Summary

En este video, se introduce el concepto de tablas hash con sondeo lineal. Se explica cómo se usan arrays de tamaño M para almacenar pares clave-valor, y por qué M debe ser al menos tan grande como N, el número de elementos a insertar. En el sondeo lineal, cada clave se inserta en el índice proporcionado por una función hash, pero si el índice está ocupado, se busca un espacio vacío moviéndose secuencialmente a la derecha. A través de un ejemplo simple, se demuestra cómo manejar colisiones y cómo encontrar un espacio libre en el array para insertar elementos.

Takeaways

• 😀 El concepto de una tabla hash con sondeo lineal implica usar un arreglo de tamaño M para almacenar pares clave-valor.
• 😀 M debe ser al menos tan grande como N (el número de elementos a insertar) para evitar desbordamientos o sobrescritura de datos.
• 😀 El uso de una función hash permite calcular un índice donde insertar el valor. Si ese índice está ocupado, se mueve al siguiente.
• 😀 El sondeo lineal implica comenzar en un índice y desplazarse hacia la derecha hasta encontrar una ranura vacía.
• 😀 En caso de colisión, si un índice está ocupado, el algoritmo revisa la siguiente posición y sigue hasta encontrar un espacio disponible.
• 😀 Si el número de elementos a insertar (N) es mayor que el tamaño del arreglo (M), puede haber problemas como sobrescribir o descartar datos.
• 😀 La técnica de sondeo lineal requiere que haya suficiente espacio vacío en la tabla para evitar errores o pérdida de datos.
• 😀 La diferencia entre el sondeo lineal y el enfoque de encadenamiento es que el encadenamiento usa listas en cada índice para almacenar múltiples valores, mientras que el sondeo lineal utiliza un solo valor por índice.
• 😀 En un ejemplo, insertar la clave 4 en una tabla de tamaño 4 de manera que haya colisiones muestra cómo se realiza el sondeo hacia la siguiente ranura vacía.
• 😀 El algoritmo de sondeo lineal puede implicar que se necesiten varias verificaciones de índices hasta encontrar un espacio libre, lo que puede afectar la eficiencia.
• 😀 El video promete un ejemplo más detallado con un conjunto de datos más grande en el siguiente segmento, para ilustrar cómo funciona el sondeo lineal con más elementos.

Q & A

¿Qué es una tabla hash con sondeo lineal?

Es una técnica para almacenar datos en una tabla hash, donde los elementos se colocan en una matriz de tamaño M. Si la posición inicial para un elemento está ocupada, se mueve a la siguiente posición disponible en la matriz.

¿Por qué es importante que el tamaño de la tabla M sea al menos igual a N?

Es importante porque, en el sondeo lineal, solo se puede almacenar una pareja clave-valor por índice. Si M es menor que N, no habrá suficientes espacios para insertar todos los elementos, lo que causaría errores o sobrescrituras no deseadas.

¿Cómo funciona la función hash en este método?

La función hash se utiliza para calcular el índice de la tabla donde debe insertarse un elemento. En el ejemplo dado, la función hash es simplemente el valor del elemento modificado por el tamaño de la tabla (M).

¿Qué sucede si la posición calculada por la función hash ya está ocupada?

Si la posición calculada está ocupada, el algoritmo de sondeo lineal mueve el índice hacia la derecha, verificando cada posición siguiente hasta encontrar una posición vacía para insertar el elemento.

¿Qué sucede si no se encuentra un espacio vacío en la tabla?

Si no se encuentra un espacio vacío, el proceso de inserción no puede continuar correctamente, lo que generaría problemas si la tabla está llena o el tamaño de M es inadecuado.

¿Cómo se resuelve una colisión en sondeo lineal?

Cuando ocurre una colisión (es decir, cuando dos claves intentan ocupar el mismo espacio), el algoritmo revisa la siguiente posición disponible en la tabla y sigue buscando hasta encontrar un espacio vacío.

¿Qué diferencia hay entre el sondeo lineal y el encadenamiento?

En el encadenamiento, cada posición de la tabla puede contener una lista de elementos. Esto permite manejar un número ilimitado de colisiones, mientras que en el sondeo lineal, la tabla tiene un tamaño fijo y las colisiones se resuelven desplazando elementos.

¿Por qué el sondeo lineal requiere que M sea mayor que N?

Porque, si la tabla tiene menos índices que elementos a insertar, se generarán colisiones continuas y no se podrán insertar todos los elementos. Esto podría llevar a que los datos se pierdan o se sobrescriban.

¿Cómo se comporta el algoritmo cuando se inserta un elemento que ya tiene una posición ocupada?

Cuando un elemento no puede ser insertado en su índice original debido a que está ocupado, el algoritmo comienza a mover una posición a la derecha hasta encontrar un espacio vacío donde pueda insertar el elemento.

¿Por qué es importante mantener la relación entre M y N?

Mantener M al menos tan grande como N es crucial para garantizar que la tabla hash no se llene demasiado rápido, lo que podría generar problemas de rendimiento y dificultad para insertar nuevos elementos.