[SER222] M03_04 Separate Chaining (3/4): Implementation

Summary

En este video, el instructor explica detalladamente la implementación de una tabla hash basada en encadenamiento. Se aborda la creación de una clase genérica para claves y valores, la inicialización de la tabla hash y el uso de listas enlazadas para resolver colisiones. Se profundiza en la función hash y las operaciones de obtención e inserción de elementos. Además, se discuten los desafíos de implementar funciones como eliminar elementos y redimensionar la tabla. Finalmente, se invita a los espectadores a experimentar con el código para familiarizarse con su funcionamiento y los conceptos subyacentes.

Takeaways

• 😀 Se utiliza una tabla hash con encadenamiento separado para manejar colisiones en la implementación.
• 😀 La clase `SeparateChainingHashTable` usa genericos para las claves y los valores, permitiendo flexibilidad en los tipos de datos.
• 😀 El constructor de la tabla hash acepta un parámetro para el tamaño del arreglo o utiliza un valor predeterminado (997, que es un número primo).
• 😀 El arreglo `st` almacena listas vinculadas, implementadas con la clase `SequentialSearchST`, que funcionan como una tabla simple para almacenar los pares clave-valor.
• 😀 La función `hash()` se utiliza para calcular el índice en el arreglo mediante un código hash, el cual se ajusta a través de un operador de módulo.
• 😀 La operación `get()` busca una clave en la lista correspondiente en el arreglo y devuelve el valor si encuentra una coincidencia.
• 😀 La operación `put()` inserta un nuevo par clave-valor en la lista correspondiente en el arreglo, gestionando colisiones mediante encadenamiento.
• 😀 Los métodos `get` y `put` se basan en recorrer las listas vinculadas en el índice calculado por la función de hash.
• 😀 Implementar un método de eliminación de clave es complejo debido a la necesidad de iterar sobre la lista vinculada y eliminar el nodo correspondiente.
• 😀 La redimensión de la tabla hash es complicada, ya que al cambiar el tamaño, es necesario volver a insertar todos los elementos debido a los cambios en los índices después de la rehashing.

Q & A

¿Qué es un hash table de encadenamiento (chaining) y cómo funciona?

Un hash table de encadenamiento es una estructura de datos que usa listas enlazadas para manejar colisiones. Cuando dos claves tienen el mismo índice de hash, se almacenan en una lista en esa posición del arreglo, lo que permite manejar múltiples elementos con el mismo índice sin perder información.

¿Por qué se utilizan genéricos para las claves y los valores en este hash table?

Se utilizan genéricos para permitir que cualquier tipo de objeto se pueda usar como clave o valor, lo que hace que el hash table sea flexible y reutilizable para diferentes tipos de datos sin necesidad de especificar tipos concretos.

¿Cuál es el propósito de la variable 'M' en la implementación?

La variable 'M' representa el tamaño del arreglo donde se almacenan las listas enlazadas, es decir, el número de 'buckets' en el hash table. Este valor define la capacidad inicial de la estructura y es importante para la distribución de las claves.

¿Cómo se crea el arreglo que contiene las listas enlazadas en esta implementación?

El arreglo se crea utilizando una técnica especial de Java que permite crear un arreglo de objetos genéricos. Se inicializa un arreglo de tipo 'SequentialSearchST', y luego se llena cada posición con una lista enlazada vacía para almacenar las claves y valores.

¿Qué problema resuelve el uso del método hashCode en esta implementación?

El método hashCode convierte un objeto en un valor entero que se usa para determinar el índice donde se almacenará en el arreglo. Este valor se procesa con operaciones bitwise para asegurarse de que se ajuste al tamaño del arreglo y se distribuya adecuadamente.

¿Cómo funciona la operación 'get' en este hash table?

La operación 'get' utiliza el valor de hash de una clave para determinar su índice en el arreglo. Luego, se recorre la lista enlazada en esa posición para verificar si alguna de las claves coinciden y devolver el valor asociado a esa clave.

¿Qué hace la operación 'put' en esta implementación?

La operación 'put' inserta un nuevo par clave-valor en la lista enlazada correspondiente al índice calculado mediante el hash. Si la clave ya existe, el valor se actualiza; si no, se agrega como un nuevo nodo en la lista.

¿Qué dificultades se presentan al implementar una función de 'eliminar clave' (delete)?

Eliminar una clave es complicado porque, aunque se puede determinar rápidamente la posición usando el hash, se necesita recorrer la lista enlazada completa en esa posición para encontrar y eliminar el nodo que contiene la clave, lo que implica un recorrido de la lista.

¿Cuál es el desafío al redimensionar el arreglo en un hash table de encadenamiento?

El desafío de redimensionar un hash table es que los índices generados por el hash dependen del tamaño del arreglo. Al cambiar el tamaño del arreglo, es necesario recalcular los índices de todas las claves existentes y volver a insertarlas, lo que hace que la operación de redimensionamiento sea costosa.

¿Por qué se utiliza un número primo (997) como tamaño predeterminado del arreglo?

Se utiliza un número primo como tamaño del arreglo para reducir las colisiones, ya que los números primos tienen una mayor probabilidad de distribuir uniformemente las claves en el arreglo, lo que mejora la eficiencia del hash table.