¿Cómo optimizan los hash maps los algoritmos?

Question

Accepted Answer

Un **hash map** (diccionario) proporciona búsquedas, inserciones y eliminaciones en **O(1) promedio**. Reemplazar búsquedas repetidas con búsquedas instantáneas convierte muchos algoritmos O(n²) en O(n) a costa de O(n) de memoria.

## La idea

En lugar de buscar una lista cada vez, almacena los valores vistos en un hash map y verifica la membresía en tiempo constante.

## Ejemplo: two-sum en O(n)

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

Sin el mapa esto es O(n²); con él, un solo paso.

## Usos comunes

- **Deduplicación / membresía** con un conjunto.
- **Conteo de frecuencias** (`Counter`).
- **Agrupación / indexación** por clave.
- **Almacenamiento en caché / memoización** de resultados.

## Complejidad

- **Promedio:** O(1) por operación. **Peor caso:** O(n) en colisiones pesadas. **Espacio:** O(n).

## Inconvenientes

Las claves deben ser **hasheables** e inmutables. Las colisiones en el peor caso degradan el rendimiento. Los hash maps no están ordenados (usa variantes ordenadas si el orden importa).

## Por qué es importante

La función hash es la optimización más común en entrevistas de codificación y sistemas reales — convierte "buscar una y otra vez" en "buscarlo una vez".

El intercambio de espacio por tiempo es una palanca de ingeniería recurrente.

El conteo de frecuencias, el almacenamiento en caché y la indexación dependen todos de esta única idea.