[SER222] M03_04 Linear Probing (3/5): Implementation

Summary

En este video, se explora la implementación de una tabla hash con sondeo lineal en Java, destacando las técnicas de manejo de colisiones, inserción y búsqueda de elementos. El código utiliza dos arreglos paralelos para almacenar claves y valores, y se explica la importancia de mantener un factor de carga bajo para optimizar el rendimiento. Además, se aborda el proceso de redimensionar la tabla cuando es necesario, y se analizan los desafíos asociados con la eliminación de elementos, debido a la alteración del orden de los índices. Este enfoque busca lograr un rendimiento eficiente en operaciones de inserción, búsqueda y eliminación.

Takeaways

• 😀 El uso de arrays paralelos en tablas hash no es recomendable, ya que puede generar duplicación de código y complicar el mantenimiento.
• 😀 El tamaño del array de la tabla hash debe ser un número primo grande, como 997, para evitar problemas de colisiones.
• 😀 La clase `LinearProbingHashST` usa dos arrays paralelos: uno para las claves y otro para los valores. Ambos deben tener el mismo tamaño.
• 😀 La relación ideal entre los elementos (`N`) y el tamaño del array (`M`) es que `M` debe ser al menos el doble de `N` para evitar una alta carga y mantener el rendimiento.
• 😀 El factor de carga de la tabla hash (N/M) idealmente debería ser alrededor de 0.5 para asegurar un rendimiento de O(1) en las operaciones.
• 😀 El método `put()` verifica si la tabla hash tiene suficiente espacio antes de insertar nuevos elementos. Si no lo tiene, se debe redimensionar.
• 😀 En el método `put()`, se utiliza un bucle de sondeo lineal para encontrar una ranura vacía o una clave existente, y se actualiza el valor si la clave ya está presente.
• 😀 El método `get()` busca una clave en el array utilizando un proceso similar al de `put()`, pero solo retorna el valor asociado a la clave si la encuentra.
• 😀 El método `resize()` se utiliza para duplicar el tamaño del array de la tabla hash si la carga es demasiado alta. Esto implica crear una nueva tabla y transferir las entradas existentes a ella.
• 😀 La implementación de `delete()` en tablas hash con sondeo lineal es compleja, ya que después de eliminar un elemento, es necesario verificar y reubicar elementos en la secuencia de sondeo para mantener la integridad de la tabla.
• 😀 Al eliminar un elemento, el proceso de sondeo puede verse afectado, y algunos elementos deben desplazarse para llenar el espacio vacío y evitar colisiones en las búsquedas futuras.

Q & A

¿Por qué se considera malo el uso de arreglos paralelos en la implementación de una tabla hash?

Los arreglos paralelos son considerados malos porque requieren mantener dos arreglos al mismo tiempo, uno para las claves y otro para los valores. Esto aumenta la complejidad y el riesgo de errores, ya que ambos arreglos deben modificarse simultáneamente.

¿Cuál es la razón de usar un número primo grande para el tamaño del arreglo en una tabla hash?

El uso de un número primo grande como tamaño del arreglo ayuda a reducir la posibilidad de colisiones y mejora la distribución de las claves en la tabla hash, optimizando el rendimiento de las operaciones.

¿Qué significa el 'factor de carga' en una tabla hash y por qué es importante?

El factor de carga es la relación entre el número de elementos (N) y el tamaño del arreglo (M). Es importante porque un factor de carga bajo, idealmente alrededor de 0.5, garantiza un buen rendimiento en las operaciones de inserción, búsqueda y eliminación, evitando que la tabla se sobrecargue.

¿Qué sucede si el factor de carga es demasiado alto?

Si el factor de carga es demasiado alto, el rendimiento de la tabla hash se degrada. Esto puede llevar a una mayor cantidad de colisiones y una disminución de la eficiencia de las operaciones, lo que podría resultar en un tiempo de ejecución cercano a O(N).

¿Cómo funciona el método `put` en una tabla hash con sondeo lineal?

El método `put` comienza verificando si el arreglo tiene suficiente espacio. Luego, intenta insertar el par clave-valor en el índice determinado por la función hash. Si ya existe una clave en ese índice, se actualiza el valor. Si no, se busca el siguiente espacio vacío usando sondeo lineal.

¿Qué ocurre si ya existe un valor para la clave en la tabla durante la inserción?

Si la clave ya existe en la tabla, el método `put` actualiza el valor asociado a esa clave en lugar de insertar un nuevo par clave-valor.

¿Por qué se crea una nueva tabla hash al redimensionar en lugar de modificar la existente?

Se crea una nueva tabla hash más grande porque cambiar el tamaño de una tabla hash existente es un proceso complejo. La forma más sencilla es construir una tabla nueva, transferir los elementos de la tabla original y luego reemplazar las referencias.

¿Qué es el proceso de sondeo lineal en la búsqueda de un espacio vacío o un elemento en una tabla hash?

El sondeo lineal consiste en recorrer los índices de la tabla de manera secuencial, comenzando desde el índice calculado por la función hash, hasta encontrar un espacio vacío o un elemento con la clave buscada.

¿Por qué es difícil implementar una operación de eliminación (`delete`) en una tabla hash con sondeo lineal?

La eliminación es difícil porque puede interrumpir la secuencia de sondeo. Si se elimina un elemento, los elementos desplazados pueden perderse durante la búsqueda posterior, ya que la operación de eliminación afecta la cadena de elementos que deben ser verificadas para encontrar otros valores.

¿Qué implica el hacky enfoque para redimensionar una tabla hash y cómo afecta al rendimiento?

El enfoque hacky consiste en crear una nueva tabla hash más grande, agregar los elementos de la tabla original y luego simplemente reemplazar las referencias a los arreglos de claves y valores con las de la nueva tabla. Esto es eficiente en términos de tiempo, pero no optimiza completamente la manipulación interna del arreglo.