Hash Table (o hash map, dictionary) almacena pares (key, value) en un array usando una función hash para mapear keys a índices. El objetivo es acceso, inserción y eliminación en O(1) promedio.
La clave del diseño es manejar colisiones: cuando dos keys distintas mapean al mismo índice.
Hash Function
index = hash(key) % capacity
Una buena hash function:
- Distribuye uniformemente (pocas colisiones).
- Es determinística (mismo key → mismo índice).
- Es rápida de calcular.
Collision Handling
Separate Chaining
Cada bucket es una linked list (o tree). Si colisionan, encadenas en la lista.
- Pros: simple, nunca se llena (solo se degrada).
- Contras: overhead de punteros, cache-unfriendly.
Open Addressing
Todos los elementos están en el array. Si colisionan, buscas la siguiente posición libre (probing sequence).
- Linear probing:
index = (hash + i) % capacity. - Quadratic probing:
index = (hash + i²) % capacity. - Double hashing:
index = (hash1 + i × hash2) % capacity.
Clustering es el problema principal: linear probing sufre primary clustering.
Load Factor y Resizing
Load factor α = n / m donde n = elementos, m = capacidad.
Cuando α > threshold (típicamente 0.75), se hace resize:
- Crea nuevo array de tamaño
2m. - Re-hashea todos los elementos.
- Actualiza la referencia.
Resize es O(n), pero es amortizado O(1) porque ocurre raramente.
Comparación
| Método | Búsqueda | Inserción | Eliminación | Colisiones |
|---|---|---|---|---|
| Chaining | O(1+α) | O(1) | O(1+α) | Lista enlazada |
| Linear probing | O(1/(1-α)) | O(1) | O(1) | Clustering |
| Quadratic probing | O(1) | O(1) | O(1) | Secondary clustering |
Aplicaciones
- Databases — indexing, hash joins
- Caches — LRU cache usa hash map + linked list
- Compilers — symbol tables
- Cryptografía — password storage (con salt + bcrypt/Argon2)
- Conjuntos — unique element tracking
Casos Extremos
- Todos keys colisionan — O(n) degenera a array/lista.
- Resize infinito — sin threshold, el array crece sin control.
- Hash adversarial — attacker envía keys que colisionan (DoS). Usa hash aleatorizado.
- Eliminación en open addressing — requiere tombstone markers.
Trayectoria de Práctica
- Implementa hash table con chaining; prueba con 1000 elementos.
- Implementa linear probing; compara con chaining.
- Añade resizing cuando
α > 0.75. - Investiga robin hood hashing: ¿cómo reduce varianza?
- Investiga cuckoo hashing: ¿cómo garantiza O(1) worst-case?