Lecciones · #8 de 11

Tablas Hash

hash djb2 → índice de bucket → O(1) promedio

Hash table · djb2 hash mod cap

size0

cap8

load0.00

init

key value

Pruébalo: Inserta claves; el destello naranja es la secuencia de sondeo. Alterna entre encadenamiento ↔ sondeo lineal para ver dos estrategias de colisión muy distintas. Luego redimensiona para ver cómo se recalcula el hash de cada clave.

Por qué importa

Las tablas hash logran el santo grial: búsqueda, inserción y eliminación en O(1) en el caso promedio. Están detrás de todo diccionario, conjunto, caché e índice de base de datos. Entender el hashing es esencial para algoritmos eficientes.

La idea

Imagina una biblioteca enorme donde los libros se ordenan en estantes por la primera letra del nombre del autor. Encontrar "Knuth" significa ir directo a la sección 'K' — sin buscar entre todo.

Una tabla hash funciona de la misma forma, pero de manera más inteligente. Una función hash convierte cualquier clave en un índice de arreglo:

hash("Knuth") → 42 → almacenar en el índice 42

La magia: esta conversión es O(1). Calculas el índice directamente en lugar de buscar.

El detalle: las colisiones. Dos claves diferentes podrían tener el mismo índice de hash. Soluciones:

Encadenamiento: Cada bucket es una lista enlazada de elementos que colisionan
Direccionamiento abierto: Encontrar la siguiente ranura vacía

Con una buena función hash y un factor de carga bajo, las operaciones se mantienen en O(1) en promedio.

Puntos clave

Inserción, búsqueda y eliminación O(1) en promedio
Requiere una buena función hash para una distribución uniforme
Las colisiones son inevitables — deben manejarse
El factor de carga afecta el rendimiento — redimensiona cuando está demasiado lleno

Invariantes

Invariantes de la tabla hash: Pureza de la función: la función hash es determinista — la misma clave siempre se mapea a la misma ranura. (Si no lo fuera, no podrías encontrar nada.); Integridad del bucket: toda clave almacenada k reside en una ranura alcanzable desde hash(k) mod capacity mediante la política de colisión elegida (encadenamiento: el mismo bucket; sondeo: el bucket inicial, luego la secuencia de sondeo determinista).; Cota del factor de carga: α = n / capacity se mantiene por debajo del umbral de redimensionamiento (típicamente 0.7 para sondeo, 1.0 para encadenamiento). Cuando lo cruza, la tabla recalcula el hash — la misma historia amortizada que la duplicación de arreglos.

Profundizando

Familias de funciones hash — elige según el caso de uso

Los hashes criptográficos (SHA-256, BLAKE3) son excesivos: están diseñados para ser infalsificables, no rápidos. A las tablas hash les importa la velocidad + la distribución uniforme, no la resistencia a colisiones frente a un atacante.

| Familia | Velocidad | Notas | |---|---|---| | FNV-1a | muy rápida | código diminuto, excelente para claves cortas; el djb2 de la demostración es de la misma familia | | MurmurHash3 | rápida, bien distribuida | el predeterminado en muchos runtimes de lenguajes (Java 8+, Go antiguo) | | xxHash3 | extremadamente rápida | el mejor rendimiento bruto; usado por zstd, LZ4, librerías de dataframes | | CityHash / FarmHash | rápida, de origen Google | nivel similar a MurmurHash | | SipHash | medio-rápida, con clave | predeterminado resistente a DoS en el HashMap de Rust, Python 3.4+, Perl | | SHA-256 | lenta (grado criptográfico) | criptográfica; para un HashMap, nunca; para almacenamiento direccionado por contenido, sí |

Por qué importa el factor de carga — la paradoja del cumpleaños

Con m buckets y n claves distribuidas uniformemente, la probabilidad de cualquier colisión supera el 50% en torno a n ≈ √(π·m/2) — la misma matemática que la paradoja del cumpleaños (las colisiones son sorprendentemente probables con muchos menos elementos que buckets).

Para cuando α = n/m = 0.7, incluso una función hash perfecta tiene muchas cadenas de longitud 2 o 3. El sondeo se degrada más rápido que el encadenamiento — en α = 0.9, el número esperado de sondeos del sondeo lineal es ~5.5, y en α = 1.0 diverge. El corte de 0.7 es una convención elegida para que el número de sondeos se mantenga en torno a 2 en promedio.

Ataques DoS por colisiones de hash

Si un atacante puede elegir tus entradas y predecir tu función hash, puede crear claves que caigan todas en el mismo bucket — colapsando tu O(1) a O(n). Java 7 tuvo un incidente famoso: HashMap<String, ...> explotó cuando los parámetros CGI eran adversariales. La solución en los runtimes modernos es el hashing con clave: al inicio del proceso se genera un secreto aleatorio, y la función hash (SipHash) lo mezcla en cada cálculo. El atacante no puede predecir dónde caen las claves sin el secreto.

Si estás escribiendo una librería que toma entradas no confiables como claves de hash (analizadores HTTP, deserializadores JSON, capas de consulta a bases de datos), asegúrate de que tu hashmap use hashing con clave. El HashMap por defecto de Rust lo hace; el std::unordered_map de C++ no.

Estrategias avanzadas de colisión

Más allá del encadenamiento y el sondeo lineal, dos patrones cambian complejidad por mejores garantías en el peor caso:

Hashing Robin Hood — durante el sondeo, si encuentras una ranura cuyo ocupante actual sondeó una distancia más corta que tú, intercambias con él. Distribuye las distancias de sondeo de manera uniforme y acota el peor caso.
Hashing cuco (cuckoo) — dos funciones hash; si ambas ranuras están llenas, desaloja al ocupante existente y reinsértalo en su otra posición de hash. Las búsquedas tienen garantizado O(1) en el peor caso (revisar dos ranuras y listo).
Hashing hopscotch — mantiene cada clave dentro de un vecindario acotado de su bucket de origen, de modo que la búsqueda es amigable con la caché incluso bajo colisiones.

Estos aparecen en producción: hopscotch en algunas librerías de Java, Robin Hood en el predeterminado de Rust anterior a 2018, cuco en las tablas de búsqueda de los enrutadores de red.

Detalles matemáticos

Complejidad temporal (caso promedio): Insert: O(1); Lookup: O(1); Delete: O(1)
Peor caso (muchas colisiones): O(n)
Factor de carga: α = n / capacity; Redimensiona cuando $\alpha > 0.7$ típicamente

Implementación

HashMap en Rust

use std::collections::HashMap;

let mut map = HashMap::new();
map.insert("key", 42);       // O(1) prom.
let val = map.get("key");    // O(1) prom.
map.remove("key");           // O(1) prom.

// La iteración es O(n)
for (k, v) in &map {
    println!("{}: {}", k, v);
}

Cuándo usarla

Diccionario/mapa (almacén clave-valor)
Prueba de pertenencia a un conjunto
Caché y memoización
Conteo de frecuencias

Práctica

Tres problemas que muestran por qué las tablas hash son la navaja suiza de los algoritmos:

Agrupar anagramas — medio · "canonicalizar y luego agrupar en buckets" — la plantilla para agrupar por equivalencia
Caché LRU — medio · hash + lista doblemente enlazada — el diseño canónico de dos-estructuras-juntas
Subcadena más larga sin caracteres repetidos — medio · ventana deslizante + hash de "último índice visto" — el patrón O(n) de ventana sobre cadenas

→ Explora todos los problemas de práctica

🪣 Tablas Hash