[SER222] M03_04 Linear Probing (2/5): Algorithm Trace

Summary

En este video, se explica cómo simular una tabla hash con sondeo lineal. El ejemplo se centra en un arreglo de tamaño 11, donde se insertan varias claves utilizando una función hash. A medida que se insertan los elementos, el video demuestra cómo manejar colisiones mediante la técnica de sondeo lineal, es decir, probando el siguiente índice cuando el actual está ocupado. A través de ejemplos prácticos, el video ilustra cómo se distribuyen las claves en la tabla hash y cómo se resuelven las colisiones, brindando una comprensión clara del funcionamiento de esta estructura de datos.

Takeaways

• 😀 El tamaño de la tabla hash es M = 11.
• 😀 La función de hash utilizada es K mod 11 + 1.
• 😀 La inserción de elementos en la tabla hash se realiza usando sondeo lineal.
• 😀 Se comienza con un índice inicial y, si la posición está ocupada, se avanza al siguiente índice.
• 😀 Si un índice está ocupado, el número de intentos (i) se incrementa para buscar una nueva posición.
• 😀 Los primeros cinco elementos a insertar son 3, 11, 7, 0, 14 y 1.
• 😀 El primer intento de inserción para cada clave se calcula con la fórmula de hash (K mod 11 + i).
• 😀 En caso de colisiones, los elementos se reubican en el siguiente índice libre.
• 😀 El proceso de inserción asegura que, si un índice está ocupado, se pruebe el siguiente hasta encontrar espacio.
• 😀 El resultado final de la tabla hash muestra los elementos insertados en los índices calculados o desplazados por colisiones.
• 😀 El objetivo del algoritmo es simular el funcionamiento de una tabla hash con sondeo lineal, explicando cada paso del proceso de inserción.

Q & A

¿Qué es una tabla hash con sondeo lineal?

Una tabla hash con sondeo lineal es una estructura de datos utilizada para almacenar claves y valores. Cuando una clave se mapea a una posición ya ocupada en la tabla, se busca la siguiente posición libre, moviéndose de manera secuencial (lineal) hasta encontrarla.

¿Qué significa el valor M en el contexto de la tabla hash?

El valor M representa el tamaño de la tabla hash, es decir, el número total de posiciones o índices disponibles en la tabla para almacenar los elementos.

¿Cómo se calcula la posición inicial de una clave en la tabla hash?

La posición inicial de una clave se calcula utilizando la función hash, que en este caso es 'K mod 11 + 1', donde K es la clave y 11 es el tamaño de la tabla (M). El valor resultante indica la posición inicial en la tabla.

¿Qué sucede si la posición calculada ya está ocupada en una tabla hash con sondeo lineal?

Si la posición calculada ya está ocupada, el sondeo lineal incrementa el índice y vuelve a calcular la posición, buscando la siguiente posición libre hasta encontrar un espacio disponible.

¿Qué hace la función de hash en este ejemplo específico?

La función de hash 'K mod 11 + 1' mapea una clave K a una posición en la tabla hash, utilizando el módulo 11 para asegurar que el valor de la clave se ajuste al tamaño de la tabla, y sumando 1 para evitar que la clave se mapee a la posición 0.

¿Por qué se menciona el 'mod 11' en la función hash?

'Mod 11' se utiliza para garantizar que el resultado de la función hash se mantenga dentro del rango de índices de la tabla (de 0 a 10 en este caso, dado que M = 11). Esto asegura que la clave se distribuya correctamente en la tabla.

¿Cómo se resuelve el conflicto cuando la posición deseada está ocupada?

El conflicto se resuelve incrementando el valor de 'i' (el número de intentos) y recalculando la posición con la fórmula 'K mod 11 + i'. Si la nueva posición también está ocupada, el proceso se repite hasta encontrar una posición libre.

¿Qué significa 'i' en la función hash y cómo afecta al sondeo lineal?

'i' representa el número de intentos o colisiones. Si la posición inicial está ocupada, 'i' se incrementa en cada intento de buscar una nueva posición. Esto asegura que la búsqueda sea secuencial hasta encontrar un espacio libre.

¿Qué sucede con las claves cuando se insertan en la tabla hash en este ejemplo?

Las claves se insertan en las posiciones calculadas por la función hash. Si una posición está ocupada, se aplica el sondeo lineal para encontrar la siguiente posición disponible. Las claves insertadas en este ejemplo fueron 3, 11, 7, 0, 14 y 1.

¿Cómo queda la tabla hash al final del proceso de inserción?

Al final del proceso de inserción, las claves se distribuyen en las posiciones calculadas. La tabla resultante tiene las siguientes claves en los índices: índice 0 tiene 11, índice 1 tiene 0, índice 2 tiene 1, índice 3 tiene 3, índice 4 tiene 14, y el índice 7 tiene 7.