Una tabla hash (o hash table) es una de las estructuras de datos más potentes y eficientes que existen. Permite almacenar y recuperar información en tiempo O(1) en promedio, es decir, de forma casi instantánea.
¿Qué es una función hash?
El corazón de una tabla hash es la función hash: un algoritmo que convierte cualquier dato (clave) en un número entero (índice) que se usa para almacenar el valor en un array.
def hash_simple(clave, tamaño):
return sum(ord(c) for c in str(clave)) % tamaño
print(hash_simple("python", 10)) # Siempre da el mismo resultadoColisiones: el problema principal
El mayor problema de las tablas hash son las colisiones: cuando dos claves distintas producen el mismo índice. Hay dos formas principales de resolverlas:
1. Encadenamiento (Chaining)
Cada posición del array contiene una lista enlazada de todos los elementos que colisionan:
class TablaHashChaining:
def __init__(self, tamaño=100):
self.tabla = [[] for _ in range(tamaño)]
def insertar(self, clave, valor):
indice = hash(clave) % len(self.tabla)
for i, (k, v) in enumerate(self.tabla[indice]):
if k == clave:
self.tabla[indice][i] = (clave, valor)
return
self.tabla[indice].append((clave, valor))Complejidad temporal
| Operación | Caso promedio | Peor caso |
|---|---|---|
| Insertar | O(1) | O(n) |
| Buscar | O(1) | O(n) |
| Eliminar | O(1) | O(n) |
Casos de uso reales
- Diccionarios en Python (
dict) — implementados internamente como tablas hash - Detección de duplicados — buscar duplicados en O(n) en lugar de O(n²)
- Caché de bases de datos — Redis usa hash tables internamente
Ejemplo práctico: detección de duplicados
def tiene_duplicados(lista):
vistos = set() # Internamente es una tabla hash
for elemento in lista:
if elemento in vistos:
return True
vistos.add(elemento)
return False
print(tiene_duplicados([1, 2, 3, 2, 5])) # True — O(n)Las tablas hash son esenciales para cualquier programador. Su eficiencia O(1) las convierte en la primera opción cuando necesitas búsquedas rápidas. Los dict y set de Python son tablas hash bajo el capó.