Hash tables en Python
Clase 46 de 56 • 21 Días de Python
Contenido del curso
Edgar Alarcón
student•
hace 3 años
Clase 46 de 56 • 21 Días de Python
Contenido del curso
Las hash tables, también conocidas como tablas hash o diccionarios, son estructuras de datos eficientes y versátiles que nos permiten almacenar y recuperar datos utilizando una función hash.
La idea principal detrás de las hash tables es utilizar una función hash para calcular el índice donde se almacenará cada par clave-valor en un arreglo de tamaño fijo. La función hash toma la clave y produce un valor numérico único que se utiliza para determinar la ubicación en la tabla. Esto permite un acceso rápido a los valores, ya que no es necesario buscar a través de todos los elementos como en una lista o una matriz.
Complejidad algorítmica
Si medimos la complejidad de los métodos de la hash table con Big o notation, podremos notar que es de lo más eficiente. Debido a que siempre se mantiene constante.
| Operación | Complejidad Algorítmica |
|---|---|
| Inserción | O(1) |
| Búsqueda | O(1) |
| Eliminación | O(1) |
En una hash table bien implementada con una función hash eficiente, todas estas operaciones tienen una complejidad constante (O(1)). Esto significa que el tiempo de ejecución no depende del tamaño de la hash table, lo cual es una característica clave de las hash tables y las hace altamente eficientes para manejar grandes volúmenes de datos.
Implementación básica de una hash table
En python basta con usar un simple diccionario como hash table o crear tu propia implementación como verás a continuación
class HashTable: def __init__(self, size): self.size = size self.buckets = [[] for _ in range(size)] def hash(self, key): # La función hash toma una clave y devuelve un índice calculado # utilizando una función hash. return hash(key) % self.size def insert(self, key, value): # El método insert toma una clave y un valor, # y los almacena en la hash table. index = self.hash(key) self.buckets[index].append((key, value)) def get(self, key): # El método get toma una clave # y devuelve el valor correspondiente almacenado en la hash table. index = self.hash(key) for k, v in self.buckets[index]: if k == key: return v return None def remove(self, key): # El método remove toma una clave # y elimina el par clave-valor correspondiente de la hash table. index = self.hash(key) for i, (k, v) in enumerate(self.buckets[index]): if k == key: del self.buckets[index][i] return def retrieve_all(self): # El método retrieve_all devuelve todos # los valores almacenados en la hash table. all_values = [] for bucket in self.buckets: for key, value in bucket: all_values.append(value) return all_values
Esta implementación utiliza una lista de listas (self.buckets) para representar los buckets de la hash table. Cada bucket es una lista que almacena los pares clave-valor correspondientes. La función hash se implementa utilizando la función hash() incorporada de Python, y se utiliza el operador módulo (%) para asegurar que el índice calculado esté dentro del rango válido de buckets.
Los métodos insert, get, remove y retrieve_all proporcionan la funcionalidad básica para manipular la hash table. Puedes utilizar estos métodos para insertar pares clave-valor, obtener valores por clave, eliminar pares y obtener todos los valores almacenados.
Al comprender y utilizar las hash tables de manera efectiva, podemos optimizar el rendimiento y resolver problemas de manera eficiente en una amplia gama de aplicaciones.
Edgar Alarcón
Waldir Zapata Garcia
Jhon Freddy Tavera Blandon
Nicolas Alpargatero
Paola Alapizco
Nicolas Alpargatero
Una animación que ayuda en comprensión: https://www.youtube.com/watch?v=9zqGQQly0To
El concepto de tablas hash es ampliamente utilizado en aplicaciones como:
my_table = HashTable(10) my_table.insert("nombre", "Juan") my_table.insert("edad", 25) print(my_table.get("nombre")) # Output: "Juan" my_table.remove("edad") all_values = my_table.retrieve_all() print(all_values) # Output: ["Juan"]
En resumen, las hash tables son estructuras de datos eficientes y versátiles que permiten almacenar y recuperar datos de manera rápida. En Python, podemos utilizar el diccionario como una hash table nativa o implementar nuestra propia versión personalizada utilizando una función hash para calcular los índices donde se almacenarán los elementos.
En los cursos no se ve esto o si? ni sabía que Hash Tables era los mismos diccionarios 🐍👀
Hay un curso de Estructuras de Datos impartido por Diego De Granda donde explica super bien y a detalle las estructuras de datos, incluidas las Hash Tables, en el curso utilizan JavaScript pero la lógica y los fundamentos son los mismos en cualquier lenguaje de programación, todo lo que enseñan en ese curso se puede implementar sim problemas en Python :D
Gracias, aunque si los cursos de Diego son como el módulo de Programación Basica paso, pero lo agregare a la lista.