Tablas hash: el principio de los diccionarios

Al finalizar este tema

Podrás explicar cómo funcionan las tablas hash y comprender el principio por el cual los diccionarios de Python logran búsquedas en O(1).

Problema: encontrar uno entre un millón

Para buscar un valor específico en una lista, es necesario compararlo uno por uno desde el principio.

users = ["Kim Hun", "Lee Su", "Park Jin", ...]  # 1 millón de personas
"Kim Hun" in users  # Peor caso: 1 millón de comparaciones — O(n)

Si los datos aumentan diez veces, el tiempo de búsqueda también aumenta diez veces. ¿No hay alguna forma de evitarlo?

Las tablas hash son estructuras de datos en las que el tiempo de búsqueda permanece casi constante, sin importar cuánto aumenten los datos.

Función hash: convertir claves en direcciones

La idea central de una tabla hash es sencilla: convertir la clave en un número (dirección) para acceder directamente a dicha dirección.

"Kim Hun" → función hash → 427  → almacenado en table[427]
"Lee Su" → función hash → 12   → almacenado en table[12]
"Park Jin" → función hash → 891  → almacenado en table[891]

La analogía de la biblioteca es adecuada. Al buscar un libro en una biblioteca, no se revisan las estanterías desde el principio. Se consulta el número de clasificación (signatura) y se va directamente al estante correspondiente. La función hash actúa precisamente como este "asignador de números de clasificación".

# Función hash integrada de Python
hash("Kim Hun")     # -4340382828924905128 (diferente en cada ejecución)
hash("Lee Su")     # 7421390584116839301
hash(42)         # 42 (los números enteros tienen como valor hash su propio valor)

# Dividir por el tamaño de la tabla para determinar el índice
index = hash("Kim Hun") % 1000  # Índice en el rango de 0 a 999

Colisión: ¿qué ocurre cuando dos elementos llegan a la misma dirección?

Una función hash puede asignar el mismo índice a diferentes claves. Esto se denomina colisión.

"Kim Hun" → hash → 427
"Choi Young" → hash → 427  ← ¡Colisión!

La solución más común es el encadenamiento (chaining). Se crea una lista enlazada en el mismo índice para almacenar varios elementos.

table[427] → ("Kim Hun", "010-1234") → ("Choi Young", "010-5678")
table[12]  → ("Lee Su", "010-9012")

Si hay pocas colisiones, la longitud de la cadena es 1, lo que resulta en O(1); si hay muchas, la cadena se alarga y el rendimiento disminuye. Por lo tanto, es fundamental que una buena función hash distribuya los datos de manera uniforme.

Diccionario de Python = Tabla hash

El dict de Python está implementado como una tabla hash. De ahí proviene este rendimiento.

# Diccionario — Búsqueda O(1)
users = {"Kim Hun": "010-1234", "Lee Su": "010-5678"}
users["Kim Hun"]     # Cálculo de hash → acceso directo — O(1)
"Park Jin" in users   # O(1)

# Lista — Búsqueda O(n)
user_list = [("Kim Hun", "010-1234"), ("Lee Su", "010-5678")]
# Para encontrar a "Kim Hun", comparar uno por uno — O(n)

Ya sean 1 millón o 10 millones de elementos, la búsqueda en un diccionario tarda casi el mismo tiempo.

Debilidades de la tabla hash

No es una solución universal.

• Uso de memoria: Requiere reservar espacios vacíos de antemano, por lo que consume más memoria que una lista.
• Sin orden: Originalmente, las tablas hash no garantizan el orden de inserción (Python dict lo garantiza desde la versión 3.7).
• Restricciones de clave: Las claves deben ser inmutables — las cadenas, números y tuplas pueden ser claves, pero una lista no puede serlo.

# Las listas no se pueden usar como claves
d = {[1, 2]: "valor"}  # TypeError: tipo no hashable 'list'

# Las tuplas son válidas
d = {(1, 2): "valor"}  # OK — las tuplas son inmutables y, por tanto, hashables

Resumen clave

Las tablas hash logran búsquedas en O(1) mediante un principio simple: "clave → función hash → índice → acceso directo". Cada vez que usas dict en Python, una función hash se ejecuta internamente. Si necesitas buscar algo con frecuencia en tus datos, casi siempre la respuesta correcta es usar diccionarios en lugar de listas.